# How many Two Doku puzzles exist?

## The Mathematics of Su Doku

How many Su Doku puzzles exist? This is the biggest unknown about Su Doku now. The challenge is hard, so I will illustrate it here with one of the simplest problems of this kind: Su Doku with 4 cells and two numbers. Call it Two Doku.

## Some facts about Two Doku

### How many solutions?

The rule is to place two numbers in such a way that no number is repeated in a row or in a column. Two Doku does not have a rule about blocks. A moment's thought will convince you that as soon as you write a number into the upper left corner you can fill in the remainder of the cells. You can write one of two number into the upper left square, so you have two solutions. These are shown above. They each have the symmetry of the coloured square on the right.

### Symmetry of the grid

One obvious symmetry of the problem is that the symbols to be filled in are quite
arbitrary: Uno or due, Alice or Bob, Deep Purple or Pink Fried. In particular,
once you chose the symbols you still have the freedom of permuting them. This
is called an S_{2} symmetry group: the permutation group of two things.
Call this S_{2}^{symb}.

The grid itself has some symmetries when it is blank. You could interchange two
rows (another permutation symmetry): call this S_{2}^{row}. Or
you could interchange two columns: call this S_{2}^{col}. You
could reflect by any of the two diagonals, or you
could rotate the square by 90 degrees clockwise or anticlockwise, or by 180
degrees. This is usually called a C_{4} symmetry group. There is an
inversion symmetry which exchanges every corner with its diagonally opposite one.
For Two Doku, all these symmetries together are simply the symmetry group of the square (often
called D_{4}).

The full symmetry of the problem is the direct product S_{2}^{symb}
× D_{4}, which is just a complicated way of saying that you can do
operations on the grid and the entries separately.

Of course, once you fill up the grid, these two types of operations are not completely indepdentn. Notice that if you flip the symbols 1 and 2 in the first solution, then you get the second one. But this permutation of symbols can be undone by simply rotating the square by 90 degrees rotation (or flipping rows, or columns). The two solutions are therefore related by symmetry.

### Orbits, essentially different solutions and little groups

Solutions which are related to each other by a symmetry transformation of the problem are said to be in the same orbit of the group. Since the Two Doku solutions can be flipped into each other by symmetries of the symbols or the grid, this means that the two solutions are in the same orbit. Taking one solution from each orbit gives us all the essentially different solutions. Two Doku has essentially just one solution, since it has only one orbit of solutions. We can choose this to be the first solution.

The little group of a solution is the subgroup of the full group that keeps the solution unchanged. Here is a specification of the little group of Two Doku:

- An element from S
_{2}^{symb}followed by an element chosen from S_{2}^{row}to undo it. - An element from S
_{2}^{symb}followed by an element chosen from S_{2}^{col}to undo it. - An element from S
_{2}^{row}followed by an element chosen from S_{2}^{col}to undo it. - A rotation by 180 degrees
- Either of the two reflections about the diagonals.

## The puzzle tree

### Proper and irreducible puzzles

A proper puzzle is one which has exactly one solution. The completed grid is clearly a proper puzzle, although quite a trivial one. One can keep removing clues from a proper puzzle one by one and checking whether the remaining puzzle is still proper. Everytime you produce a new proper puzzle by this means, write it down and put an arrow pointing to this from the puzzle from which it was produced. An irreducible puzzle is one from which no further proper puzzles can be produced. The graph of all proper puzzles starting from a solution is called a puzzle tree.

One can also have inconsistent puzzles. These are puzzles which violate the rules. For example a two-clue Two Doku in which there is a 1 in both squares in the top row is inconsistent. None of the puzzles in the puzzle tree can be inconsistent, since they are obtained by removing symbols from a consistent solution.

### The Two Doku puzzle forest

The collection of puzzle trees starting from each essentially different solution is called a puzzle forest. The Two Doku puzzle forest is a little sparse: it contains only one tree. That one is shown above. Note that every puzzle is proper except the completely empty grid. The irreducible puzzles (outlined in red) are those with exactly one clue. Note that they have no arrows going out of them. They are leaves on the tree.

There are 15 puzzles in all, 4 of which are irreducible. The little group of the solution could have been used to simplify the counting. Puzzles with different numbers of clues cannot be in the same orbit of the little group of the solution. Thus there are is one essentially different puzzle with 4, 3 and 1 clues, and two with 2 clues (two clues in a column or along a diagonal, say).

Note the subtly changed meaning of "essentially different" when applied
to puzzles. Applied to solutions, it meant taking one representative solution
from each orbit obtained by the action of the full group of symmetries of Two Doku,
ie, S_{2}^{symb}×D_{4}. When applied to puzzles,
we still mean to take one representative puzzle from each orbit, but the orbit can
be constructed by examining only the action of the little group of the solution on
the puzzles.

### The puzzle hypercube

Here is a representation of the puzzle tree which is very useful for programming
its enumeration. Number every square sequentially, first travelling along the top
row, then the second and so on. There are M^{2} squares (here 4). While
enumerating the tree we ask every square of the solution whether its value remains
in the set of clues or not. If the answer is yes, write down a zero for that
square, otherwise a one. Call this the skeleton of the puzzle. Then treat the
skeleton as a binary number by multiplying the value in the cell by 2^{c}
where c was the numbering of the square, and summing over all squares. The skeleton
and its representation as a number is shown in green in the picture of the tree
above.

Now, the ordered set of zeroes and ones which comprise the skeleton of the puzzle
can be thought of as the coordinates of the corners of a hypercube in M^{2}
dimension. For Two Doku this is the usual 4-dimensional hypercube, the tesseract.
The identification of puzzles with corners of the cube is shown by the numerical
values of the skeleton attached to each corner.

Note that the skeleton 15 is not part of the puzzle tree, since it does not give a proper puzzle. We have indicated this by putting a cross on each link that joins it to another skeleton. On all other links note the direction of the arrow: this always leads from the skeleton with smaller value to that with the larger. If you want to know why, just examine the definition of the value of the skeleton and the reason why it can't be the opposite will become as clear as acid rain.

#### Symmetries of skeletons and hypercubes

Since the vertices of the hypercube are identified with the skeletons of puzzles,
it is clear that the symmetries of the skeletons are subgroups of the symmetries
of the hypercube. Why a subgroup? The symmetries of the hypercube obviously
consist of any operations which permutes the vertices. However, the symmetries of
skeletons do not change the number of ones and zeroes, and therefore keep two of
them unchanged— the ones numbered 0 and 2^{M2}. Therefore,
the number of allowed operations on skeletons is smaller, and hence the group
must be a subgroup of the symmetries of the hypercube.

The largest such subgroup contains all rotational symmetries about the "body diagonal" which joins the two fixed points of the hypercube, and reflection symmetries in hyperplanes orthogonal to this line. For Two Doku, the allowed rotations interchange (1,2,8,4) cyclically. This allows cyclic interchanges of (7,11,14,13) and (3,10,12,5), but only flips of (6,9) between themselves. Even smaller subgroups of allowed rotations about body diagonals of hypercubes may be allowed for larger Su Dokus.

## Maximum and minimum number of clues

Complicated questions about the puzzles, for example the maximum and minimum number of clues among the irreducible puzzles, now reduce to inspecting the puzzle forest. For Two Doku the answer is 1 for each. The total number of proper puzzles is 30, the total number of irreducible puzzles is 8. The number of essentially different proper puzzles is 5, of which one is irreducible. All puzzles are satisfactory.

© Sourendu Gupta. Mail me if you want to reproduce any part of this page. My mailing address is a simple (satisfactory) puzzle for you to solve. Created on 04 March, 2006. Last updated on 10 March, 2006.