brainwagon

My last post dealt with a solver for KenKen puzzles. Once you have one of those, then the obvious thing to work on next (in your copious spare time) is a generator for KenKen puzzles. It didn’t seem too hard. You’d begin by generating a random Latin square, then divide it up into “cages”, assign an operator to them, and then see if that has a unique solution. If it doesn’t, well, try again.

But it turns out that each of these steps hides inner difficulties, as well as a certain amount of mathematical beauty. Tom and I were discussing the first bit (generating random Latin square) over lunch, and I thought I’d summarize some of our discussion.

First of all, consider the following “canonical” Latin square of order 4:

1 2 3 4
4 1 2 3
3 4 1 2 
2 3 4 1

It’s pretty easy to generate this Latin square, and it’s pretty easy to generate other Latin squares by swapping either rows or columns. But the question is, can I generate all other Latin squares from this one by doing row and column swap operations?

Tom assured me that the answer was no, which wasn’t at all apparent to me until he presented an interesting example, so I thought I would summarize some of the ideas here. My presentation will take a slightly different path than our discussion, but it ends in the same place.

Let’s consider each square to have a canonical form, where the first row and first column are in sorted order. It should be relatively obvious that you can place any matrix into this form by a series of row and column operations. For example, the matrix above can be placed in canonical form by swapping the second and fourth row.

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3 

But let’s consider a different matrix in canonical form formed by swapping 1 and 3 in rows 2 and 4.

1 2 3 4
2 1 4 3
3 4 1 2 
4 3 2 1 

We can’t convert this matrix into the previous one by only swapping rows and columns. Thus, if we try to generate a random Latin square by just beginning with a canonical one, there are possible Latin squares which can never be generated by just swapping row and column operations. Too bad, since this is really easy to implement.

Another easy thing to implement would be to just generate all possible Latin squares, store them in a table, and select one at random. That doesn’t seem too bad, until you consider that there are 812,851,200 possible Latin Squares to consider. Sure, disks are big, but that seems excessive.

It turns out that the algorithm that most people seem to use is the from 1996 by Jacobson and Matthews, which is hard to find online as a full paper. It uses a similar idea, but instead of swapping full rows and columns, it applies a different operator that mutates a given Latin square, and in the limit produces a distribution which is the same as the random distribution. It’s a little tricky to understand, but I am going to try to have an implementation in Python later tonight.

Here’s a report that provides some details and the skeleton of an implementation in Java.