Mike Barker wrote:At first I was under the impression that the canonical form of a puzzle is when it is transformed to have the smallest row order lexicographic value. Now I'm finding that there is an additional constraint that box 1 be of the form:

- Code: Select all
`1 2 3`

4 5 6

7 8 9

Does anyone know why there is this additional constraint? I would think it would make more sense to simply allow row 1 to be:

- Code: Select all
`1 2 3 4 5 6 7 8 9`

This makes sense since most solvers process data by rows or columns, not boxes, and is consistent with the minimum lexicographic value (which must start 123456789...).

the two forms, lets's call them box-normal and row-normal, are both valid

row-normal is easier to specify: the the minimum lexicographic row order value

box-order adds: with the top left box of the form ...

as with many data formats there can be space-time tradeoffs

e.g., given a solution, what is the complexity of determining the row-normal form vs. box-normal form

for row-normal

9 rows could be the first row: 9 choices

the 3 chute portions of the first row can be permuted 6 ways: 6

each column in each chute can be permuted 6 ways: 6*6*6

the puzzle can be rotated 90 deg to make cols rows: 2

for a total of 9*6*6*6*6*2 = 23328 choices

for box-normal

9 boxes could be the first box: 9

the cols in the box can be permuted 6 ways: 6

the rows in the box can be permuted 6 ways: 6

the puzzle can be rotated 90 deg to transpose the boxes: 2

for a total of 9*6*6*2 = 648

each "choice" sets the labeling of all cells for the lexicographic value

for row-normal the remaining rows within the bands are swapped to form the minimal value

for box-normal the columns within the middle and right chutes and rows within the middle and bottom bands

are swapped to form the minimum value

box-normal form is much easier easier to calculate

gordon's catalog canonicalizes (to box-normal form) at ~2800 puzzles/sec/Ghz

I haven't verified the timing difference because I didn't bother coding the row-normal form

but it would probably come in at ~100 puzzles/sec/Ghz