Challenges
Exploring the Mathematics of Su Doku
Is there always an M×M Su Doku?
A Su Doku grid is possible for every M which is non-prime. For M=pq, tile the M×M grid by p×q rectangular cells. The next step is to prove that there is at least one arrangement of M symbols such that each row, column and cell contains one and only one occurrence of each symbol. But this is easy.
When M is prime one can try to tile the grid with any tile made of M squares (these are called polyominos). You will need exactly M of these (some shapes may be used more than once).
Challenge 1: Count the number of distinct tilings of the grid for any prime Su Doku. Two tilings are to be counted as distinct if they are not related by rotations, reflections, or any other symmetry of the grid.
Challenge 2: Is there a Sudoku for all tilings of the grid for prime M? Is there a Sudoku for at least one tiling of the grid for prime M?
Number of Su Doku solutions
The number of filled in Su Doku grids is the number of distinct solved puzzles. The total number of puzzles is, of course, much larger, because two puzzles may have the same solution. (A partially solved puzzle can be considered to be an independent puzzle.)
Challenge 3: How many solutions exist for an M×M Su Doku? The number is known for some M (see the results page), essentially by a complete enumeration f all possibilities using a computer program. Can one do the counting in general?
Challenge 4: Instead of taking rectangular cells for composite (non-prime) M, one could take arbitrary polyomino tilings for all M. One possible tile is a 1×M rectangle. If you use this then the cells are just rows (or columns). This is the problem of Latin Squares. The counting of Latin Squares is a well-known (but not completely solved) problem. Any other tiling reduces the number of solutions. What is the minimum number of solutions for any M×M Su Doku?
The placing of clues
Challenge 5: What is the maximum number of independent clues possible? In Shi Doku the maximum number of independent clues possible is 7. In 9×9 Su Doku the current best is 33. What is it for a general Super Doku?
Challenge 6: Prove an upper bound on the minimum number of clues for any Su Doku. (In Shi Doku 4 clues are enough. In Roku Doku grids, 9 clues seems to suffice. For 9×9, standard sudoku, it is claimed that 17 clues are enough.)
Challenge 7: Count the number of different puzzles for Su Doku. Two puzzles should be counted as different if the clues are different, even if they lead to the same solution. However, this is not enough, since a partial filled in solution is also a new puzzle. So count the number of different puzzles with independent clues.
Satisfactory puzzles
In the literature on Su Doku one finds references to bifurcation; also called Ariadne's thread, but more commonly known as trial and error. A solution by this means leaves me feeling a little unsatisfied: I am carrying out a set of instructions that any computer can be programmed to execute (the algorithms is known in computer science as depth-first search). So where is the fun which I expected out of solving a puzzle?
Challenge 8: Define "satisfactory" precisely in a sense that a large fraction of Su Doku addicts would agree to. Count the number of satisfactory puzzles. The London Times puzzle claims not to need trial and error: if so the definition of "satisfactory" should encompass all possible puzzles that could be published in this newspaper; ie, the program that generates these puzzles should be provably in the class that you define.
Challenge 9: Clearly, restricting attention to satisfactory puzzles would change all the counting that involves clues. So do these bits of counting all over again for satisfactory puzzles.
© 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 09 October, 2005.