Prime Su Doku
Counting possible tilings
A Super Doku grid is possible for every M which is non-prime. For M=pq, tile the M×M grid by p×q rectangular cells. When M is prime, then this construction fails. We can still divide up a prime board into M cells, each containing M squares. We do not allow cells which are in multiple pieces, or where one or more squares is joined to the remainder only by corners. The allowed cells are generalizations of dominos, called polyominos.
Sub Doku of order 3
How many tilings?
Only two triominos exist: the L-shaped blue piece shown in the picture on the left, and the long I-shaped red piece. One way to put them together into a 3×3 square is to use the "I" thrice. That would give a Sub Doku which is no different from a Latin Squares, so we do not consider it further. A more interesting way to put these together into a 3×3 square as shown. All other interesting Sub Dokus of order 3 are obtained by rotations of this figure. So there are only two tilings, one of which is no different from a Latin Square.
How many solutions?
Once numbers filled are into the cell coloured yellow in the example shown on the right, the remaining numbers are immediately fixed uniquely. There are 3!=6 ways of filling these initial numbers. This is the number of solutions.
Maximum and Minimum Sub Doku
In the figure above, all three starting numbers are not needed, since the third can be derived once the remaining two are given. Hence the minimum number of clues is 2. This is also the maximum number of independent clues possible.
Go Doku: Sub Doku of order 5
How many tilings?
Creating all possible tilings for Go Doku (which is 5×5 Sub Doku; "go" is Japanese for the number five) involves a game of pentominos. The twelve pentominos are illustrated in the pentomino home page. Using these shapes, one can build a 5×5 square in many possible ways. Three of these are shown above.
Open questions
- How many distinct tilings?
- How many tilings can one have which are not just a Latin Squares and are not related by the symmetries of a square? The three shown above are not exhaustive by any means.
- Do all the tilings admit Su Doku?
- A Su Doku is shown in the figure above. Do all the other tilings also admit Su Doku? Are there tilings which do not admit Su Doku?
- How many Su Doku solutions?
- This question clearly needs refining. There are 12 3×3 Latin Squares but only 6 3×3 Su Dokus with the tiling shown above. So one question to ask is the minimum number of Su Dokus among all possible tilings of a given grid. Another is to enumerate all Su Doku counts for all tilings.
Counting the number of solutions
We develop the counting for the first Go Doku tiling shown above. But first some notation is required to specify a square: the square on the i-th column and j-th row (counting from top left) will be called the square (ij). We can begin by filling the first column in any of the 5! possible ways. The counting is the same for all of these, so for the remainder we assume that the square (1k) has value k.
The remainder of the enumeration is performed by a depth first search, where all branches are taken whenever a choice is available, and the number of times the search hits a completed grid is totalled. The method has been used for counting Shi Dokus. The search tree is shown in the figure below. Each yellow oval is a point of branching: labelled by the square where the branch occurs. We find that the search produces a binary tree. 14 branches lead to completed grids. As a result, this tiling allows solutions.
Maximum Go Doku on this tiling
The following reasoning shows that the counting of the previous section also gives the maximum Go Doku. First note, that the four symbols placed in the first column are all independent clues. Next, each branch point in the counting tree give another independent clue, except in the specific cases where one of the branches yields no completed solution. In this last case, the final choice may be eliminated from the tree. In this pruned tree the deepest path must give the maximum Go Doku. The only remaining check to be performed is that no other placement of the first four clues can yield a deeper tree. The result is that the maximum Go Doku for this tiling has 10 clues. One of these is shown in the figure alongside. The other can be obtained by replacing the 2 in position (43) by 5.
Minimum Go Doku on this grid
The example shown at the right is one of the several minimum Su Doku on this grid. Interestingly, the solution can be reached without trial and error. Which means that for this particular tiling the minimum Go Doku is also the minimum satisfactory Go Doku.
© 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 26 September, 2005. Last updated on 07 October, 2005.