Some terminology first:

- Code: Select all
`<-triplet-> <-triplet-> <-triplet->`

1 2 3 4 5 6 7 8 9 <row>

4 5 6 7 8 9 1 2 3

7 8 9 1 2 3 4 5 6

2 3 4 5 6 7 8 9 1

5 6 7 8 9 1 2 3 4

8 9 1 2 3 4 5 6 7

3 4 5 6 7 8 9 1 2

6 7 8 9 1 2 3 4 5

9 1 2 3 4 5 6 7 8

This is the very simple and valid base SUDOKU from which we can create ALL other sudoku puzzles. (hunch, but no proof at this moment)

Insight 2: Allowed transformations that keep it valid:

1) any two columns within a vertical triplet may be exchanged

2) any two rows within a horizontal triplet may be exchanged

3) any two vertical triplets may be exchanged

4) any two horizontal triplets may be exchanged

5) at any time the whole 9x9 thing can be rotated 90 degrees left or right

(Though I think this operation can be made up from a sequence the above)

6) at anytime the whole 9x9 thing can be mirrored along vertical, diagonal, or horizontal center line

(Though I think this operation too can be made up from a sequence the above)

7) as mentioned above, as the numbers are nominal (unlike in magic squares) any two numbers can be exchanged throughout the grid

(Though I think this operation yet again can be made up from a sequence the above)

Applying these transformations leads to a large, but not infinite number of SUDOKU.

Insight 3: Hiding = Compression

The next step after randomizing the layout is to HIDE certain numbers without making the thing insolvable. This is where I need to brush up on my information theory, but I think you can reduce it to a minimum number of digits which is determined by Huffman's theory...

Basically the SUDOKU validity rules allow compressing the total grid.

So HIDING numbers is like compressing the information in the completed SUDOKU. To have a SUDOKU with a single solution, you need lossless compression, so limited by huffman's theory. In layman's terms: the minimum possible number of digits to be shown depends entirely on their position as this is part of the compression scheme.

Insight 4: multiple solutions = lossy compression

If you remove more digits than the limit, you get multiple solutions. This follows also from logic: if you hide all numbers you can fill in any valid sudoku!

Insight 5: compression and transformation are commutative

Just another hunch: if you find the maximum numbers you can hide in the MOAS, applying all the transformations still leaves you with a solvable SUDOKU. This is useful for SUDOKU generator writers: you can have base: easy, medium, hard and generate from there.

So all have a nice weekend!

Maarten Meijer