Sudoku Symmetry - Formalized

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

Postby JPF » Fri Jan 19, 2007 8:46 am

Thanks for the links.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby Red Ed » Fri Jan 19, 2007 9:02 am

Further to your question: 180-degree rotation is in class nr 79.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby ravel » Fri Jan 19, 2007 1:57 pm

Red Ed wrote:ravel, why don't you try clarifying your question before I run out of patience with your dismissive attitude?
Calm down dear, it's only a commercial (as you say in your country):)
I just wanted to express, that your answer does not give me directly, what i wanted to know, but needs to study your paper.
I never was good in group theory, i am not familiar with the definitions you use, i was not even able to see the relationship between the title and the content of the paper immediately, not the relationship between your sample transformation plus the number of conjugates and the existence of "real" grids with this symmetry.

So i would have had to let you wait for an answer for some weeks, when i might have clarified all this.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Red Ed » Fri Jan 19, 2007 4:05 pm

ravel wrote:Calm down dear, it's only a commercial (as you say in your country):)
Touché!

OK, here's a simpler way of putting it. Remember that we regard a pair of isomorphic grids as "essentially" the same, even if one looks nice and symmetric and the other is all messed up? The same goes for the symmetry itself: two symmetries (ops 2-6 from that list) are "essentially" the same if one is the conjugate of the other. So in fact there are "essentially" only 26 different symmetries that have any fixed grids, representatives of which are shown on that web page.

It would be a nice public service to replace each of those 26 symmetries with a simpler essentially-the-same conjugate. For example, we noted earlier that class 79 is (essentially the same as) 180-degree rotation, but it certainly doesn't look like it from the entry on the web page.

Clearer?
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby ravel » Fri Jan 19, 2007 9:18 pm

Thanks for simplifying it for me. Though i assumed what you explained now, i was not sure.
If i understood it now, then 180 degree rotational symmetry is represented in class 79, diagonal symmetry in 37, chunk symmetry in 7, box symmetry in 28 and 90 degree symmetry in 86.

Your table also answered an earlier question by me: all possible automorphisms transform either 0, 1 (90 and 180 degree rotation) or 9 cells (diagonal symmetry) to the same place.
Also class 134 seems to preserve 9 cells, but if i did not make a mistake, it is equivalent to just exchange bands 2 and 3 (?).
[Added:]That would mean, that Mauricio and gurth already have found all kinds of symmetrical puzzles, that allow special (uniqueness based) symmetrical techniques to solve them (and they have found specials with combined symmetries).
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ravel » Sat Jan 20, 2007 10:32 am

ravel wrote:Also class 134 seems to preserve 9 cells, but if i did not make a mistake, it is equivalent to just exchange bands 2 and 3 (?).
This cant be true. It should be equivalent to exchanging 2 bands and 2 columns in each stack. So, can someone find a puzzle and relabeling, so that the puzzle is mapped to itself with these operations ?
[Added:]
Code: Select all
+-------+-------+-------+
| 1 2 3 | 7 5 6 | 4 8 9 |
| 4 5 6 | 1 8 9 | 7 2 3 |
| 7 8 9 | 4 2 3 | 1 5 6 |
+-------+-------+-------+
| 3 1 2 | 6 7 8 | 9 4 5 |
| 6 4 5 | 9 1 2 | 3 7 8 |
| 9 7 8 | 3 4 5 | 6 1 2 |
+-------+-------+-------+
| 2 3 1 | 5 9 7 | 8 6 4 |
| 5 6 4 | 8 3 1 | 2 9 7 |
| 8 9 7 | 2 6 4 | 5 3 1 |
+-------+-------+-------+
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ravel » Mon Jan 22, 2007 5:05 pm

Class 41 has an interesting transformation with 5 fixed cells. But there cannot be a grid with this symmetry, because in one unit (box 8) there are 3 fixed cells and 3 pairs of cells. So max. 3 numbers remain for the 4-cycles (inside a box) in the transformation.
btw, the class should be equivalent to: swap rows 2 and 3, mirror at \-diagonal, swap rows 2 and 3, 5 and 6 and columns 8 and 9.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Mauricio » Sat Jan 27, 2007 12:49 am

Sorry if this was said before.

From this post by Red Ed that replies the previous post by coloin, it can be shown that there are at most 648 different automorphism for each sudoku solution grid.

This grid (MC grid) has the 648 possible automorphisms:
Code: Select all
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby gsf » Sat Jan 27, 2007 3:23 am

Mauricio wrote:This grid (MC grid) has the 648 possible automorphisms:
Code: Select all
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5

automorphisms of the resultant canonical grid are a byproduct of my row-order canonicalization algorithm implementation
in my solver -f%#aC prints the number of non-trivial automorphisms of the row-order canonical grid (printed by -f%C)
for the MC grid it finds 647 non-trivial automorphisms, which corroborates 648 = 1:trivial + 647:nontrivial

thanks for making the connection tying all this together
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Previous

Return to General