Canonicalization and redundance reduction

j0rg3n

When generating puzzles, I suspect there might be an advantage in trying to parameterize the possible space of puzzles, at least to some degree.

One strategy of getting there (if at all possible; although NP completeness should not nescessarily prevent a neat enumeration of the space of possible puzzles), may be to find methods of canonicalization and reduction of the redundance, that is: Equivalent puzzles should have the same representation, and the representation should not contain more information than strictly required.

The fundamental observation is that the numbers 1-N are arbitrary, and that relabeling them will yield an equivalent puzzle. Thus, my first proposition is to assume that the first row (or column, or block; row is somewhat arbitrary) always consists of the numbers 1-N. If not, relabel the puzzle so that they do (this may easily be done by considering the first row as a translation lookup table indexed from 1-N).

Then the diagonals. There is no dependence between blocks which are positioned diagonally in relation to each other, and thus we have relational position information that is irrelevant to the structure of the puzzle. Is there some neat graph structure that will remove this redundance?

Finally: The soduko.com solver page works by entering the first five numbers in a puzzle. Is this sound? The first five numbers cannot possibly enumerate all valid puzzles? (If they do, there should be ample potential for reduction! Smile

j0rg3n · Posted: Fri Jun 24, 2005 10:27 am Post subject: An idea for the graph structure

The graph structure is a multigraph, same as suggested in the solution thread.

It consists of N nodes (9 in the standard case), and each row, column and block is represented as an acyclic subgraph, which must connect all the nodes (include all the numbers).

The rules for the edges, is that the first three nodes must be the same in the r1 and b11 paths, and the first three nodes in the c1 path must match the first, fourth and seventh nodes in the b11 path, and so forth for the other columns, blocks and rows (This connects them as in the regular grid.)

The image below displays a partial graph for the partial grid

Agent Allen

j0rg3n you said,