Starting from any complete solution grow the complete game tree in the following recursive fashion. Note that the root of the tree, ie the complete solution, is a proper puzzle. Starting from any proper puzzle, remove entries one at a time and check whether the new puzzle is proper. If it is, then (and only then) it is a node in the graph. Draw an arrow from the starting proper puzzle to the new proper puzzle (an arrow points into every node other than the root; more than one arrow may point into a node). This directed graph I call a puzzle tree (strictly speaking this is a misnomer).

If a node on the puzzle tree has no arrow going out from it, then it is a leaf node. All leaf nodes are irreducible (in the sense that if we remove any clue from such a puzzle it is no longer a proper puzzle).

Now, all complete Su Doku solutions can be broken into disjoint orbits by the symmetry group (see Frazer for more). Taking one representative from each orbit, since they cannot be connected by a symmetry, the set is called a set of essentially different solutions. These have been counted.

The puzzle forest is the collection of puzzle trees for each member of the set of essentially different solutions. Since each node in the forest is a proper puzzle, a node belongs to only one tree (ie, different trees do not share nodes).

More details and the beginning of a formal document are available.

Various questions about the puzzle forest are interesting. A sampler:

- What is the minimum number of clues in the forest?
- What is the maximum number of clues in the leaves of the forest?
- Do different trees in the forest have different maxima and minima?

I report results from the complete enumeration of the puzzle forest for Shi Doku (2X2 Su Doku). I'll give details of the programs later. In order to set out the results let me recall that there are 2 orbits of solutions: 1234341221434321 and 1234342121434312. The first row is in order, as is the first block. Since the two are distinguished by the value in the [4,4] place, I call them configurations 1 and 2 respectively. I grow the puzzle trees from these roots and find

- the minimum number of clues in the forest is 4
- the maximum number of clues in the leaves of the forest is 7
- on configuration 1 the minimum has 5 and the maximum leaf has 7 clues, on configuration 2 the minimum has 4 and the maximum lead has 6 clues.
- the total number of essentially different proper puzzles (including the two trivial: fully filled puzzles) is 84370
- the total number of essentially different irreducible puzzles is 1312.
- the total number of puzzles can be obtained from the breakup below, since one knows the structure of the orbits for this problem.

Full statistics are:

- Code: Select all
`Clues All nodes Leaves only`

conf_1 conf_2 conf_1 conf_2

16 1 1 0 0

15 16 16 0 0

14 120 120 0 0

13 560 560 0 0

12 1808 1816 0 0

11 4224 4320 0 0

10 7216 7744 0 0

9 8848 10560 0 0

8 7380 10884 0 0

7 3760 8224 48 0

6 960 4144 432 128

5 96 960 96 576

4 0 32 0 32

Total 34989 49381 576 736