## Canonical Puzzle Form

Everything about Sudoku that doesn't fit in one of the other sections
What if we consider only solved (and valid) puzzles, i.e. those with all 81 spots filled in?

I think it's reasonable to define two such puzzles to be equivalent if, and only if, one can be obtained from the other by one of the following:

1. interchanging two "minor" columns in the same "major" column, e.g. interchanging columns 1 and 2, or 1 and 3, or 2 and 3. (A "major" column consists of three columns, either 1-2-3 or 4-5-6 or 7-8-9.)

2. interchanging two major columns, e.g. 1-2-3 and 4-5-6.

3. same as 1. but with rows instead of columns.

4. same as 2. but with rows instead of columns.

5. rotating the entire puzzle 90 degrees.

6. replacing each digit in the puzzle with its image under some 1-to-1 mapping of the set {1,2,3,4,5,6,7,8,9} onto itself.

7. combining and/or repeating any of the above.

Note that reflections (horizontal, vertical, or diagonal) can be constructed from sequences of the above.

It is certain (I hope) that the above definition of equivalence is, indeed, an equivalence relation.

Is it known how many equivalence classes there are?

Bill Smythe
Smythe Dakota

Posts: 536
Joined: 11 February 2006

Smythe Dakota wrote:Is it known how many equivalence classes there are?
Yes: 5472730538.
Red Ed

Posts: 633
Joined: 06 June 2005

Smythe Dakota wrote:What if we consider only solved (and valid) puzzles, i.e. those with all 81 spots filled in?

I think it's reasonable to define two such puzzles to be equivalent if, and only if, one can be obtained from the other by one of the following:

the lexicographic canonicalization routine I posted takes this into account
however, instead of attempting to find a map from A=>B to show equivalence
it compares canon(A) vs. canon(B), which is more efficient for puzzle cataloging
i.e., the heavy computations are done up front once for each puzzle
then a simple 81 byte comparison (or less if per puzzle compression is used)
determines equivalence
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Suggestion to everyone:

Instead of the word "canonicalize", let's just use "canonize", one of the better made-up words I've ever made up.

Bill Smythe
Smythe Dakota

Posts: 536
Joined: 11 February 2006

Smythe Dakota wrote:Suggestion to everyone:
Instead of the word "canonicalize", let's just use "canonize", one of the better made-up words I've ever made up.

canonicalize already defined and it fits in this discussion
canonize already coined by the vatican
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

gsf wrote:.... canonize already coined by the vatican

That's another reason I like it.

Bill Smythe
Smythe Dakota

Posts: 536
Joined: 11 February 2006

jeez:
123
456
789

||||
Code: Select all
`1123123434251236`
EhEm?
deam3r

Posts: 10
Joined: 12 February 2006

Previous