I have a little progress to report on the enumeration of puzzles. For RXC Su Doku, each puzzle tree has upto 2^(M^2) nodes, where M=RC. Clearly this grows too fast to allow quick scanning. In order to reduce the problem, over the last few days I've been playing with the notion of a
skeleton. A worked out example for an utterly trivial case is given in
http://theory.tifr.res.in/~sgupta/sudoku/clues.html.
Start with a solution, then delete some entries, keeping the rest as clues. The skeleton of this puzzle is obtained by replacing each deleted entry by 0 and everything else as 1.
Choose a numbering of the M^2 cells. The bits of the skeleton written out in order of the numbering is the binary representation of a number which I call the value of the skeleton. The canonical numbering starts with 0 for the r1c1, increases along the row, is M for r2c1, and so on upto M^2-1. The value of the skeleton in the canonical ordering can be called the canonical value of the skeleton. Values of skeletons always lie between 0 and 2^(M^2)-1 (these are the only two values which are invariant under relabelling of the cells).
The ordered bits of the skeleton can also be interpreted as the vertices of an unit hypercube in M^2 dimensions. A subgroup of the symmetries of the hypercube acts on the skeletons.
Pruning Strategy 1: Since the geometric Su Doku group, GSD(R,C), acts on the skeletons, it can be used to enumerate the essentially different (ED) skeletons. More pertinently, the little group of a solution can be used to enumerate the ED skeletons. One needs to examine only the ED skeletons in order to generate full information about the whole game tree.
Note 1: This approach was implicitly taken by Red Ed in the enumeration of the Shi Doku solutions.
Note 2: As Kjell points out somewhere, the little group of
most solutions is trivial so there is no reduction in the work required in
most cases. However, in special cases of high symmetry, this can reduce the work enormously.
Note 3: Since the orbits of skeletons 0 and 2^(M^2)-1 are just themselves, the subgroup of the symmetries of the hypercube which act on the skeletons cannot be bigger than the subgroup of rotations of the hypercube around this body diagonal (the diagonal line which joins these two points).
Pruning Strategy 2: If one enumerates impossible skeletons, then these can be eliminated from the enumeration of all trees. Some impossible skeletons are those which have only 1's in two rows in the same block, since that would leave two rows without clues. In order to push this strategy, one needs a classification theorem about which little groups are not allowed.
Note 4: This was the structure behind the two questions in my previous post.
Pruning Strategy 3: Of course, once a puzzle has been proven to be improper, the whole subgraph below this node is automatically improper. Proof: note that the puzzle tree contains no inconsistent puzzle (ie, puzzle with zero solutions). Hence every improper puzzle in the graph has more than one solution. The removal of clues cannot decrease the number of solutions. Therefore, the result.
Note 5: Subgraphs are most easily identified by their skeletons. Once a subgraph is ruled out, one should mark these skeletons as unusable (since parts of them can be reached from other parts of the game tree).
Note 6: Skeletons are also useful enumeration tools in various proofs. For example, the best proof(s) that I have for the fact that M-1 clues are not sufficient for M>3 depend on the enumeration of equivalence classes of skeletons with M-1 clues.
