increpare games

I was thinking about Sudoku yesterday, and was thinking about the basic transformations that you can do that will produce a solution from another solution (like rotating the board, or swapping certain rows/columns), when I came across a different way of looking at it. I’ll describe what I mean for the simpler case of a 4×4 game of Sudoku.

Label the rows as 1 2 3 4 from top to bottom, the columns as 5 6 7 8 from left to right, and the four squares 9 10 11 12 clockwise starting from the top left. Call these lines, for want of a better word.

Now, make a graph with vertices labelled 1 to 12, where there is an edge between two vertices whenever the lines they represent intersect.

You get the graph

Call this graph G.

Now, looking at the automorphisms of this graph, you get all the transformations corresponding to swapping rows/columns, isometries etc., that leave solutions unchanged. Of course, there are many more ways of generating solutions (like permuting the letters), but they can all (I think) be captured as follows:

Lets say we have a solution of the 4×4 grid S. We’ll define the covering space to consist of all subsets of S that contain the numbers 1 to 4 exactly once (you get 4^4 different elements in that space). Call the elements of the covering space lines.

Now, if you construct the graph of intersections of this space (with lines as vertices, and two vertices connected whenever the lines intersect), and call it C.

You have full embedding (f say) of G into C (I don’t know if “full” is a proper term, but I mean that two vertices in the image are connected by an edge only when they are connected by an edge in G).

I think that it’s a little obvious (if unclear) that every other full embedding of G into C will also give a solution. So I’m guessing that if you enumerate all embeddings and divide out by the solution-isomorphisms that you should get the total number of solutions; I’m not totally convinced about that yet though.

(you can reformulate this and talk instead of morphisms of the comma category (G|C). If you so desire. I think. )

Info about the automorphism group of G:

It’s generated by the following transformations

(5 6), (1 2), (3 4), (7 8)

which correspond to swapping rows/columns

(1 5)(2 6)(3 7)(4 8)(10 11)

which corresponds to flipping about a diagonal axis (notice that 9 and 12 are fixed, even though their contents are permuted).

(12 9)(1 7)(2 8)(3 5)(4 6)

which is something similar but about the other diagonal axis…well…not really…look at it yourself if you wanna know.

(12 10)(1 3)(2 4)(9 11)

Almost corresponds to swapping the top two rows with the bottom two rows.

I calculated this with nauty, which is just a fantastic program, in that I could get it to work with almost no effort :)

There are a lot of other things that can be done with sudoku mathematically, just see wikipedia’s Sudoku entry for a sample. The graph colouring version probably encapsulates mine at some level, but I don’t know enough about colouring to be able to figure it out.