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.