Blog

I was recently reading another math blog on Latin Squares and it brought the concept back to the forefront of my mind. For years I have wanted to do something with Latin Squares, but nothing generated enough of my interest to follow through on a project to completion. I had done some things to create a random Latin Square, but didn’t think that in itself was worthy of publication. So I let it linger.

Then I read this post. It talks about Latin Squares with added chess-based restrictions. So the one based on a chess knight’s move would say that in addition to being a Latin Square, there would be a restriction that cells (x, y) and (x +/- 2, y +/- 1) and (x +/- 1, y +/- 2) all be different. Likewise there is a bishop based restriction saying that cells (x, y) and (x +/- i, y +/- i) all be different. Because Latin Squares already assume that cells have horizontally and vertically different characters, this is the same as a queen’s move would be. Latin Squares also already take into account the rook moves. The remaining pieces talked about were the king based Latin squares. These say that for a cell (x, y) the cells (x+/-1, y+/-1) must all be different. There is an accompanying paper that I also found interesting.

I read this blog article on the heels of having just improved my puzzle generations, so naturally I thought these would be good puzzles to attempt to generate and add to my puzzle section. So the first thing I did was complete a standard puzzle for Basic Latin Squares. These are under the standard assumptions saying that no number can appear more than once in any row or column. Then I used the max-submatrix problem to remove cells from this completed solution to create a puzzle. I played with this for a while and that was that. I attempted to add variants of the Latin Squares based on the chess pieces mentioned above, but with the exception of the trivial ones these were difficult and timely to generate. So again, that was that.

Until it wasn’t. I played around with the puzzles for a few hours (puzzles are addictive and started asking more questions. One of the first ones was simply how many clues do I need to have for a Latin Square to remain unique? I’m sure this problem has been studied, as it is a well studied problem for Sudoku puzzles, which are Latin Squares with an added restriction on the 3 by 3 subgrids. I found that the critical set of a Latin Square is the minimum number of cells from which a Latin Square can be reconstructed. Interesting.

Then I started thinking about visualizing Latin Squares. Obviously there is a way of visualizing them as a grid, possibly with colors instead of numbers or letters. That can make it more visually appealing. I was thinking about more of a graph theoretic approach though. So the first thing I did was something similar to the permutation graphs. With permutations, we had two lines, one representing the given permutation and one representing the lexicographically sorted permutation. Then lines are drawn between elements with the same value on different row. From this graph, we can construct a second graph consisting of the crossings (intersections of lines) in the first graph.

I used a similar approach to construct visualizations of Latin Squares. The first visualization is a node representing each cell in the square. Then lines are drawn between cells/nodes that have the same value. Once again, from this initial graph, we can look at the crossings and build a second graph, where we have the same node set, and an edge is present between two nodes if the two corresponding lines cross one another.

Apart from the (beautiful) visualization, the question I was asking myself is what information can be gained from these representations of Latin Squares. Could we gain anything from these crossing numbers? Would this last graphical representation always produce the original Latin Square? Or how similar must two Latin Squares be to get the same graph? Is there a graphical representation that preserves Latin Squares with less information?

A lot of my friends ask me what I do with my spare time. There are a number of ways I could answer that question, but the answer is basically this site. Its full of the thoughts that go through my mind as I’m at work, when I’m on a run, or driving my car or with my kids. Sometimes It’ll be a new idea, or a way of teaching/explaining/visualizing something, or something for my kids or a new way to relax.

A few years back, I added a section to this site called Puzzles. These were basically puzzles that I had seen in passing at some site or in a book that I thought were fun and challenging and wanted to do more of. The site started with the puzzles being offered as a part of the LEARNINGlover.com examples section, and many still are there. But as the site grew and I really enjoyed making the puzzles, I decided to offer a separate page dedicated to the puzzles.

Then we get to the fun part of it. How do we generate puzzles? There are basically two types of puzzles I’m thinking about here. One is where there is some final answer and none of the information that is needed for the answer is given. Instead, hints about the final answer are given. Some puzzles that offer this type of structure are Nonograms, Shade the Cells or the Magical Squares Puzzles. These are very fun and a bit easier to create.

The other type of puzzles I’ve been playing with are the ones where the final answer is generated according to some set of rules, then a subset of this final answer is revealed as a “hint” to direct the user towards the unique final answer. Some examples of these puzzles are Sudoku, Slitherlink, Binary Puzzles, and Corral. These puzzles have been more difficult for me to generate because the question that has puzzled (no I did not mean to have a play on words) me is how do we decide which puzzle cells to remove and still keep a unique solution?

I tried a number of techniques that all left me dissatisfied. Eventually I had left the problem alone and had a technique of removing a large number of cells (allowing for multiple solutions to exist) just added a “reveal” button to give more hints towards the solution if a user was stuck. This left me very unsatisfied as a) I was sure there was a way of doing this since I see it done on so many other sites so often and b) I would often start down a direction and press the reveal button, only to be told that I was headed towards the wrong one of the multiple solutions.

That is what brings me here today. I also spend a lot of time looking at programming challenges and practice exercises to help better understand data structures and algorithms. One of those problems was the maximum submatrix sum problem. The problem asks, given an m by n matrix of integer values (positive or negative) can we find the submatrix that has the maximum sum. I solved this problem years ago and had it sitting in my library as something I was going to develop as a game to play with my kids.

Then the thought hit me of using this to help decide on which cells to remove. The idea is that in most of these puzzles the neighbors of a cell have a direct influence on the contents of a cell. So in a Sudoku puzzle, we know that a cell containing a 9 inside a 3 by 3 subgrid cannot have any more 9’s. The maximum submatrix problem wouldn’t divide the original grid into the 3 by 3 subrids as Sudoku does, but it as still performed reasonably well.

Here is an overview of what we’re doing with the algorithm. Initially I set up a matrix with all positive values. For some puzzles, this is the contents of the cells, for other puzzles like Binary Puzzles I set the matrix to all 1s. Then the generate algorithm will search for the maximum sum of this matrix, and from that submatrix will select a random location. This random location will have its value removed from the puzzle and the value in this matrix will now be a large negative number. Then we simply check to see if there is a unique solution and continue.

That’s the gist of it. I have added a small quirk where I allow for a few misfires – that is, some attempts to remove a cell that leads to multiple solutions. On a misfire we simply put the value back and try again. The problem with misfires is that they are what generally slow down this process as allowing for too many misfires just leads to the generation algorithm repeatedly solving this puzzle.

So what type of results have I seen? I was getting normally about 75% of cells visible on most of these type two puzzles. That does not make a difficult puzzle. There would be the unique time where I would have about 60% of cells visible and those puzzles would be more challenging but they would normally take time to generate. Time is of the essence though so I didn’t like sitting around and waiting. Well, now I’m getting somewhere between 40-50% visibility on a fraction of the time. Sometimes its only a second or two (it was taking minutes under the old algorithm). This is not always true as I do still get sometimes a 75% visibility, but that is by far the exception rather than the norm.

The recent conversation I had about number theory has brought it back into my awareness. In particular, the concept of beauty in numbers. I’m definitely not any kind of graphical designer or fashion expert but I do appreciate what I think of as beautiful, and there are certain areas of mathematics that are just beautiful.

But who am I to say what is beautiful? What really is beautiful? Rather than trying to talk about these things in terms of the abstract concept of beauty, I wanted to try to nail down some of the things I like about it.

In our early years we learn about shapes. Sometime later we learn about things like “regular polygons”. These are polygons where all sides have the same length. We also learn about stars, but the stars we learn to draw most often is the 5 point star that we can draw without lifting the pencil.

A natural question becomes are there other stars we can draw without lifting a pen? A 4 point star? a six point star? a seven point star?

Before we go into the ? function, lets make sure we’re on the same ground. We need to talk about common divisors.

Suppose we have two numbers, lets call them m and n. A common factor of m and n is a number that divides into both of them. For example a common divisor of 4 and 6 is 2 since 4 = 2 * 2 and 6 = 2 * 3. Two numbers are called relatively prime if their only common factor is 1. Remember that 1 is a factor of every number.

Euler’s ? function (called the totient function) of a number n is defined as the count of numbers less than n that are relatively prime to n.

n	1	2	3	4	5	6	7	8	9	10	11	12	13
?(n)	1	1	2	2	4	2	6	4	6	4	10	4	12

To understand what’s going on in that table above, lets look at a number like 10 and ask what are the numbers relatively prime to 10?

n	1	2	3	4	5	6	7	8	9
Factor 10	1*10	2*5	1*10	2*5	2*5	2*5	1*10	2*5	1_9
Factor n	1*1	1*2	1*3	2*2	1*5	2*3	1*7	2*4	1*10
GCF	1	2	1	2	5	2	1	2	1

So from this example we see that the numbers relatively prime to 10 are 1, 3, 7, and 9, so ?(10) = 4.

A nice property of Euler’s phi function is that for any n > 3, if ?(n) is 3 or greater, then we can draw a star with that many (n) points without lifting the pencil.

To do this, we first need to talk about modular arithmetic. If we have two numbers, a and b and want to add them modulo some number, written
(a + b) mod n
We take the remainder of (a + b) when this number is divided by n.

For example, if we wanted to calculate (3 + 5) mod 7 we would first compute (3 + 5) to get 8 and then realize that 8 = 7 * 1 + 1. This gives a remainder of 1, so (3 + 5) mod 7 would be congruent to 1.

If we are considering drawing an n pointed star, we can start with a number that is not 1 and is relatively prime to n and continually add that number to itself. What will happen is that because this number is relatively prime to n, it will visit every other number before returning to the number 0.

What is more is that there may be more than one n pointed star that we can draw. The number of stars is (?(n) – 2) / 2. So for 10, it will be (4 – 2) / 2 = 1. This can be seen below.

I wanted to allow users to begin to see more of this beauty, so I wrote a script showcasing it.

I had a recent conversation with a friend who asked me “what makes number theory interesting?”. I loved the question, mainly because it gave me an opportunity to talk about math in a positive manner. More importantly though, it was an opportunity to talk about one of my favorite courses in mathematics (along with discrete mathematics and set theory). As much as the current day seems to focus on joining Number Theory with Cryptography, when I answered this question I wanted to make sure I didn’t go that route. Numbers are beautiful in their own right, and one of the things about Number Theory that was so interesting was simply the ability to look at all the different questions and patterns and properties of numbers discovered.

To answer this question, I started listing numbers to see if she noticed a pattern, but I did it with a “picture”.

.
..
…
….
…..
……

and I asked two questions

• How many dots will go on the next line
  and
• After each line how many dots have been drawn in total?

Lets answer these questions:

Dots	# on this line	# in total
.	1	1
..	2	3
…	3	6
….	4	10
…..	5	15

There were a lot of directions I could have taken this conversation next, but I decided to stay in the realm of triangles and discuss Pascal’s triangle. This is a triangle that begins with a 1 on the first row and each number on the rows beneath is the sum of the two cells above it, assuming that cells not present have a value of zero.

So the first five rows of this triangle are

1
11
121
1331
14641

This is an interesting and beautiful triangle because of just the number of patterns you can see in it.

• Obviously there are ones on the outside cells of the triangle.
• One layer in, we get what are called the Natural or Counting numbers (1, 2, 3, 4, 5, …) .
• One layer in, we can start to see the list of numbers that I was showing my friend (1, 3, 6, 10, 15, …).

There are several other properties of this triangle and I wanted to allow users to begin to see them, so I wrote a script highlighting some of these patterns.

This is my first post of 2019 and my first post in a while. There was one posted a few months ago, but not really geared towards the algorithms and learning focus of the site. I have been doing a lot of coding in my spare time, but honestly life has just gotten in the way. Its not a bad thing, but life is life and sometimes I have to prioritize the things. In particular, I have been having ideas and actually coding things up but the time it takes to clean up code, write a blog entry and finding a nice way to visualize these things has been something that I haven’t been able to really focus on as much as I’ve wanted to.

That said, I want to talk to you about the Set Partition Problem today. You can go to Wikipedia to get more information about this problem, but I will give you a brief introduction to it and then talk about two different approaches to it. The problem assumes that we are given as input a (multi)-set S. The reason we say it is a multi-set and not a simple set is because we can have the same element appear multiple times in the set. So if S₁ = {2} and S₂ = {2, 2}, then although as sets they are both equal to the set {2} = S₁, as multi-sets allow for multiple instances of an element. The elements of S are assumed to be positive integers.

So given this multi-set S, we ask the question of can the elements of S be divided into two smaller multi-sets, C₁ and C₂ where

• C₁ [union] C₂ = S
• C₁ [intersect] C₂ = [empty set]
• [Sigma]_[x in C₁] = [Sigma]_[x in C₂].C₁ [union] C₂ = S, C₁ [intersect] C₂ = [empty set], and [Sigma]_[x in C₁] = [Sigma]_[x in C₂]

The first two bullets above say that the sets C₁ and C₂ form a partition of S. The third bullet says that the sums of the elements in the two children multi-sets are equal.

This problem is known to be NP Complete. This means that it is one of the more difficult decision problems. Because of this finding an algorithm that solves this problem exactly will generally take a long running time. And finding an algorithm that runs quickly will more than likely be incorrect in some instances.

I will show you two approaches to this problem. One is based on Dynamic Programming (DP) and one is based on Greedy Algorithms. The DP version solves the problem exactly but has a slow running time. The greedy algorithm is fast but is not guaranteed to always give the correct answer.

Dynamic Programming is based on the principle of optimality. This says that in order to have a correct solution to the overall problem, we need optimal solutions to all subproblems of this problem. This is done by keeping track of a table which can be used for looking up these subproblems and the optimal solutions to these subproblems.

For this problem, we will build a table where the rows represent the final sums and columns represent subsets of the given multi-set (containing the first 0…n elements). The question we are repeatedly asking is “can we find a subset of the set in this column whose sum is exactly the given rowsum?” Here is an example of the DP algorithm on the multi-set {5, 6, 5, 6, 7}.

Greedy Algorithms are generally based on sorting the elements based on some principle and using that to try to answer the underlying question. The main problem with this approach is that it is very short sided because they do not look at the overall picture. Such algorithms are known for finding local optima that are not always globally optimal. The benefit to these problems though is that they are generally easier to code and easier to understand.

For the Set Partition Problem , the Greedy approach is to sort elements in descending order. Once this is done, the goal is to keep two subsets while iterating through the array, adding the element to the smaller of the two sets whenever possible.

For more examples, check out Set Partition Problems

As you can probably tell, I’m a big fan of puzzles. On one hand you can say that a good puzzle is nothing but particular instance of a complex problem that we’re being asked to solve. What exactly makes a problem complex though?

To a large extent that depends on the person playing the puzzles. Different puzzles are based on different concepts and meant to highlight different concepts. Some puzzles really focus on dynamic programming like the Triangle Sum Puzzles or the Unidirectional TSP Puzzles.

Other puzzles are based on more complicated problems, in many cases instances of NP-complete problems. Unlike the puzzles mentioned above, there is generally no known optimal strategy for solving these puzzles quickly. Some basic examples of these are ones like Independent Set Puzzles, which just give a random (small) instance of the problem and ask users to solve it. Most approaches involve simply using logical deduction to reduce the number of possible choices until a “guess” must be made and then implementing some form of backtracking solution (which is not guessing since you can form a logical conclusion that if the guess you made were true, you reach either (a) a violation of the rules or (b) a completed puzzle).

One day a few months back i was driving home from work and traffic was so bad that i decided to stop at the store. While browsing the books, I noticed a puzzle collection. Among the puzzles I found in that book were the Range Puzzles I posted about earlier. However I also found binary puzzles.

Filled Binary puzzles are based on three simple rules
1. No the adjacent cells in any row or column can contain the same value (so no 000 or 111 in any row or column).
2. Every row must have the same number of zeros and ones.
3. Each row and column must be unique.

There is a paper from 2013 stating that Binary Puzzles are NP Complete. There is another paper that discusses strategies involved in Solving a Binary Puzzle. 

Once I finished the puzzles in that book the question quickly became (as it always does) where can I get more. I began writing a generator for these puzzles and finished it earlier this year. Now i want to share it with you. You can visit the examples section to play those games at Binary Puzzles.

Below I will go over a sample puzzle and how I go about solving it. First lets look at a 6 by 6 puzzle with some hints given:

	0	1
0		1	0
1	1		0
	1			0
			0
1			1		0

We look at this table and can first look for locations where we have a “forced move”. An obvious choice for these moves wold be three adjacent cells in the same row or column where two have the same value. A second choice is that when we see that a row or column has the correct number of zeros or ones, the remaining cells in that row or column must have the opposite value.

So in the above puzzle, we can see that the value in cells (2, 2) and (2, 5) must also be a 0 because cells (2, 3) and (2, 4) are both 1. Now we see that column 2 has 5 of its 6 necessary values, and three 0’s. So the last value in this column (2, 6) must be a 1 in order for there to be an equal number of 0s and 1s.

For some easier puzzles these first two move types will get you far enough to completely fill in all the cells. For more advanced puzzles though, this may require a little more thorough analysis. 

As always, check it out and let me know what you think. 

Range Puzzles

I have always liked puzzles. I really enjoy discovering a new puzzle. Sometimes when I have discovered a new puzzle, I enjoy it so much that I can’t seem to do enough of them. In such cases, I quickly run out of these puzzles to do and find myself looking for either a new puzzle or a way to generate them on my own.

Such was the case when I discovered the “Range Puzzles”. The rules are simple:

Every cell is marked either blue or gray
No two gray cells can be next to one another
The grid must be a connected (i.e. there is always a path from every cell to every other cell using horizontal and vertical connections.
Some cells have a number inside. This indicates the number of cells that can be viewed (horizontally and vertically in both directions) by this cell, including the cell itself.

To try out these puzzles, visit Range Puzzles at LEARNINGlover.com

The Floyd Warshall algorithm is an all pairs shortest paths algorithm. This can be contrasted with algorithms like Dijkstra’s which give the shortest paths from a single node to all other nodes in the graph.

Floyd Warshall’s algorithm works by considering first the edge set of the graph. This is the set of all paths of the graph through one edge. Node pairs that are connected to one another through an edge will have their shortest path set to the length of that edge, while all other node pairs will have their shortest path set to infinity. The program then runs through every triplet of nodes (i, j, k) and checks if the path from i to k and the path from k to j is shorter than the current path from i to j. If so, then the distance and the path is updated.

So lets consider an example on the graph in the image above. The edge set of this graph is E = {(0, 1), (0, 2), (0, 3), (1, 3), (3, 4)}. So our initial table is:

	0	1	2	3	4
0	inf	(0, 1)	(0, 2)	(0, 3)	inf
1	(0, 1)	inf	inf	(1, 3)	inf
2	(0, 2)	inf	inf	inf	inf
3	(0, 3)	(1, 3)	inf	inf	(3, 4)
4	inf	inf	inf	(3, 4)	inf

As we look to update the paths, we first look for routes that go through node 0:

Because node 0 connects to both node 1 and node 2, but node 1 does not connect to node 2, we have the following truth holding in the matrix above:
cost(0, 1) + cost(0, 2) < cost(1, 2), so we can update the shortest path from node 1 to node 2 to be (1, 0, 2).

Because node 0 connects to both node 2 and node 3, but node 2 does not connect to node 3, we have the following truth holding in the matrix above:
cost(0, 2) + cost(0, 3) < cost(2, 3), so we can update the shortest path from node 2 to node 3 to be (2, 0, 3).

Because node 3 connects to both node 0 and node 4, but node 0 does not connect to node 4, we have the following truth holding in the matrix above:
cost(0, 3) + cost(3, 4) < cost(0, 4), so we can update the shortest path from node 0 to node 4 to be (0, 3, 4).

Because node 3 connects to both node 1 and node 4, but node 1 does not connect to node 4, we have the following truth holding in the matrix above:
cost(1, 3) + cost(3, 4) < cost(1, 4), so we can update the shortest path from node 1 to node 4 to be (1, 3, 4).

Because node 3 connects to both node 2 and node 4, but node 2 does not connect to node 4, we have the following truth now holding:
cost(2, 3) + cost(3, 4) < cost(2, 4), so we can update the shortest path from node 2 to node 4 to be (2, 0, 3, 4).

The final table giving the list of shortest paths from every node to every other node is given below.

	0	1	2	3	4
0	inf	(0, 1)	(0, 2)	(0, 3)	(0, 3, 4)
1	(0, 1)	inf	(1, 0, 2)	(1, 3)	(1, 3, 4)
2	(0, 2)	(1, 0, 2)	inf	(2, 0, 3)	(2, 0, 3, 4)
3	(0, 3)	(1, 3)	(2, 0, 3)	inf	(3, 4)
4	(0, 3, 4)	(1, 3, 4)	(2, 0, 3, 4)	(3, 4)	inf

To see more examples and to help answer questions, check out the script in my examples section on the Floyd-Warshall algorithm

I wanted to spend some time on centrality measures of a graph. These are measurements of how important each node (or edge) is to the overall graph. But how do we define, or determine, importance? There is no unique way to answer this question, so there are varying metrics for measuring centrality. Which one you choose depends on several factors including how many other nodes of the graph are included, as well as the run time of the metrics you’re considering.

I have just published a script focusing on the degree centrality metric. The degree centrality metric is called a “walk metric” because it determines how important a node is by how many other nodes that can be reached by walks of up to a certain length. Lets look at the definition of the degree of a node to see if we can understand why it is called a walk metric.

In an undirected graph G = (V, E), the degree of a node u [in] V is the |{v | (u, v) [in] E}|. This is the size of the set of nodes that are connected to node u via a single edge. Another way of describing a single edge is a walk of length one. So the degree metric measures the importance of a node by the number of unique walks of length one.

The normalized degree centrality of a node v in a graph G = (V,E) measures how many nodes are connected to the node v, compared to the maximum possible number of edges that can be connected to this node. Because we are dealing with simple undirected graphs (at most a single edge between any two distinct vertices), this maximum possible number will always be |V – 1|. So the normalized degree can be calculated by dividing the degree of the node (the number of nodes it is connected to) by |V – 1|.

So for the example above, the node 0 has degree 6 because it is connected to nodes 2, 5, 9, 10, 11, and 12. There are 15 total nodes in this graph, so to calculate the normalized degree centrality of the node 0, it will be 6 / 14, which rounds to 0.428571.

To see more examples and to help answer questions, check out the script in my examples section on degree centrality

I just added a program that finds the strongly connected components of a graph using Tarjan’s Algorithm.

A strongly connected component of a graph is a subgraph S of G where every pair of nodes, u and v in S there is a path from u to v and a path from v to u.

To find these strongly connected components we implement Tarjan’s algorithm. The idea behind Tarjan’s algorithm is to begin by running a depth first search from an arbitrary node in the graph, labeling nodes reachable from this start node in the order they are reached. The algorithm is also interested in the “oldest” node that could be reached by a given node. This is indicated by the keeping track of the lowest label that can be reached from that node. We will call the first property label(v) and the second lowlink(v).

When the algorithm starts label(v) is the same as lowlink(v) whenever a node is discovered. As the algorithm is executed, the DFS is being run on each discovered node, which in turn updates the lowlink(v) property telling of (older) nodes that can be reached. If an older node can be reached, then we update lowlink. If we reach a node that cannot connect to any older nodes after the DFS call, i.e if label(v) is the same a lowlink(v), then this means that this node does not have a path to any node with a lower label. So this node will be the first node of a new strongly connected component.

Feel free to check it out an let me know what you think in the comments below.