# 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.