Canonical Puzzle Form

Everything about Sudoku that doesn't fit in one of the other sections

Postby Smythe Dakota » Sun Feb 12, 2006 7:25 am

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: 534
Joined: 11 February 2006

Postby Red Ed » Sun Feb 12, 2006 12:35 pm

Smythe Dakota wrote:Is it known how many equivalence classes there are?
Yes: 5472730538.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby gsf » Sun Feb 12, 2006 4:26 pm

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

Postby Smythe Dakota » Mon Feb 13, 2006 3:48 am

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: 534
Joined: 11 February 2006

Postby gsf » Mon Feb 13, 2006 3:58 am

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

Postby Smythe Dakota » Mon Feb 13, 2006 4:57 am

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

That's another reason I like it.

Bill Smythe
Smythe Dakota
 
Posts: 534
Joined: 11 February 2006

Postby deam3r » Mon Feb 13, 2006 5:13 am

jeez:
123
456
789

||||
Code: Select all
1123
1234
3425
1236
EhEm?
deam3r
 
Posts: 10
Joined: 12 February 2006

Previous

Return to General