About Red Ed's Sudoku symmetry group

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

About Red Ed's Sudoku symmetry group

Postby eleven » Thu Dec 25, 2008 9:07 am

Frazer Jarvis' and Red Ed's Sudoku symmetry group has answered a couple of questions about symmetrical sudoku grids, before they even had been asked by the players. But it is hard to read and the given representatives often are not the simplest for players. So i did this interesting work to denote them in better readable form and categorize them in 6 groups.

[Update 3]
Link to udosuks collection of deciphered sample grids.
Link to a summary of symmetrical solution techniques.
[Added:] Link to Red Ed's list of all 122 symmetries (also combined, now with generating sets in sample grids).

The columns have the following meaning:
Name
M..representative mapping for the symmetry
C..class number in Red Ed's class table
N..number of invariant sudoku grids with this symmetry, given by Red Ed
L..Length of the (longest) cell cycles of this symmetry
F..number of fixed cells
S..special techniques for solving puzzles with this symmetry known: Y..yes, N..no, U..Unnecessary
Comment

Code: Select all
                         M         C         N        L  F  S
1. Fixed boxes
Mini-Rows (MR)         C           8    107.495.424   3  0  N equivalent to Mini-Columns (MC)
2 MR, 1 MD             CR1         7     21.233.664   3  0  Y 
1 MR, 2 MD             CR1R2       9      4.204.224   3  0  Y 
Mini-Diagonals(MD)     CR         10      2.508.084   3  0  Y

2. Boxes move in bands
Jumping-Rows (JR)      S          25     14.837.760   3  0  N 
2 JR, 1 GR             SR1        28      2.085.120   3  0  Y 
1 JR, 2 GR             SR1R2      30        294.912   3  0  Y 
Gliding-Rows (GR)      SR         32      6.342.480   3  0  Y 
Full-Rows (FR)         SC1        27          5.184   9  0  U 
2 FR, 1 WR             SR1C1      26          2.592   9  0  U
1 FR, 2 WR             SR1R2C1    29          1.296   9  0  U
Waving-Rows (WR)       SRC1       31            648   9  0  U

3. Boxes move triangular (B 159, 267, 368)
Jumping-Diagonals (JD) BS         22        323.928   3  0  Y  also "Block symmetry"
Broken-Columns (BC)    BSR1       24            288   9  0  U 
Full-Diagonals(FD)     BSR1C1     23            162   9  0  U 

4. Rotational symmetries
Half-Turn (HT)         DD2        79    155.492.352   2  1  Y  also "180° rotational symmetry"
Quarter-Turn (QT)      DBxRx      86         13.056   4  1  Y  also "90° rotational symmetry", has HT symmetry too

5. Diagonal symmetries
Diagonal-Mirror (DM)   D          37     30.258.432   2  9  Y  also "diagonal symmetry"
DM+JD                  DBS        43            288   6  0  Y
DM+MD                  DRC        40          1.854   6  0  Y

6. Sticks symmetries
Column-Sticks (CS)     BxCx      134    449.445.888   2  9  Y  also "sticks symmetry"
CS+MC                  BxCxR     135         27.648   6  0  U
CS+JR                  BxCxS     145         13.824   6  0  U
CS+ GR/Band2,JR/B13    BxCxSR2   144          3.456   6  0  U
CS+GR                  BxCxSR    142          6.480   6  0  U
CS+ JR/B2,GR/B13       BxCxSR1R3 143          1.728   6  0  U

Meaning of the shortcuts of the equivalence operations (to be read from left to right, eg DBS means S after B after D)

B..cyclically move the bands downwards (B123->B231)
S..cyclically move the stacks rightwards (S123->S231)
Bx..exchange B1 and B3 (B123->B321)
Sx..exchange S1 and S3 (S123->S321)
R1 (R2, R3)..cyclically move the rows in band 1(2,3) downwards (r123->r231)
C1 (C2, C3)..cyclically move the columns in stack 1 (2.3) rightwards (c123->c231)
R..cyclically move the rows in all bands downwards (R1R2R3 or r123456789->r231564897)
C..cyclically move the colums in all stacks rightwards (C1C2C3 or r123456789->r231564897)
Rx..invert the order (exchange the first and 3rd) of the rows in all bands (r123456789->r321654987)
Sx..invert the order (exchange the first and 3rd) of the colums in all stacks (c123456789->c321654987)
D..mirror at the main diagonal from r1c1 to r9c9 (r123456789<->c123456789)
D2..mirror at the subdiagonal from r1c9 to r9c1 (r123456789<->c987654321)
Last edited by eleven on Fri Feb 06, 2009 9:47 pm, edited 6 times in total.
eleven
 
Posts: 1534
Joined: 10 February 2008

Postby champagne » Sat Dec 27, 2008 6:03 am

Hi eleven,

I had a look to your post and some questions came.

I do not see in your classification the double diagonal symmetry offering 17 cells fixed:?:

your "sticks symmetry" seems to be somehow a downgraded view of that "double diagonal symmetry" but I am so sure.

Do you have an example of that class supposed to be one of the easiest to find:?:


Regarding "Gludo", I know where I can find examples, so I have to dig in the appropriate thread
:D


Happy new year to you and all of us

champagne
champagne
2017 Supporter
 
Posts: 5614
Joined: 02 August 2007
Location: France Brittany

Postby udosuk » Sun Dec 28, 2008 12:12 am

champagne wrote:I do not see in your classification the double diagonal symmetry offering 17 cells fixed:?:

DDS offers you immediate eliminations on 17 cells, but it doesn't necessary fix them. The only cells definitely getting fixed should be r5c5 (from the ensuring 180 symmetry - I'll leave you or others to prove explicitly that all DDS grids must also have 180 symmetry:idea: ). All other 16 cells on the 2 diagonals, you can immediately eliminate 6 candidates from each of them - but they are by no means "fixed".

(Added later: just realised what is the extra meaning of "fixed" here. It can also mean a group of cells forming as a fixed axis. In that case for DDS each diagonal symmetry has its own group of 9 cells (i.e. diagonal) as the fixed axis, and it seems weird to consider the 17 cells as a "joint fixed axis" here.:idea: )

champagne wrote:your "sticks symmetry" seems to be somehow a downgraded view of that "double diagonal symmetry" but I am so sure.

I think you need to study/research more. Sticks symmetry and double diagonal symmetry are very different things. Please refer to the "Down Under Upside Down" thread where I cited some links for you in one of the posts.:idea:

champagne wrote:Happy new year to you and all of us

Ditto!:D
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby champagne » Sun Dec 28, 2008 1:08 am

cancelled
Last edited by champagne on Sun Dec 28, 2008 4:20 pm, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 5614
Joined: 02 August 2007
Location: France Brittany

Postby eleven » Sun Dec 28, 2008 1:33 am

First here are the links to threads about symmetrical puzzles:

Gurths Puzzles
Mauricio's Automorphic sudokus
Udosuk's Down Under Upside Down - a Sudoku puzzle


champagne wrote:I do not see in your classification the double diagonal symmetry offering 17 cells fixed:?:

Double diagonal symmetry is no own symmetry, but a combination of 2 diagonal symmetries (normally with different number cycles).
A puzzle with 2 diagonal symmetries does not necessarily have the symmetries in the main and subdiagonal (where rotation by 90° shows the other symmetry on the same place), but i dont have a sample now.

your "sticks symmetry" seems to be somehow a downgraded view of that "double diagonal symmetry" but I am so sure.

Do you have an example of that class supposed to be one of the easiest to find:?:

Surprisingly for me Red Ed had calculated, that sticks symmetry is the most common of all, with 3 times more grids than the 180° symmetry.

On the last page of Gurth's thread you can find 4 samples. I chose my representative mapping CxBx in that way, that the fixed sticks are in the middle band. E.g. the 3rd puzzle would have to be transformed by changing the first 2 bands and rotating all columns in the stacks to reflect that:

Code: Select all
Mauricio, ER 9.2

9 . .|. . 3|. . 6    b a c|. . .|. . .
. 6 .|. . 1|. 5 .    b a c|. . .|. . .
. . 4|6 . .|2 . .    b a c|. . .|. . .
-----+-----+-----    -----+-----+-----
. 7 .|. 1 .|9 . 8    d X d|. X .|. X .
. . .|. . .|. . .    d X d|. X .|. X .
3 . 2|. . .|. 7 .    d X d|. X .|. X .
-----+-----+-----    -----+-----+-----
. . 8|2 . .|5 . .    c a b|. . .|. . .
. 5 .|1 . .|. 6 .    c a b|. . .|. . .
4 . .|. . 5|. . 3    c a b|. . .|. . .

BxCx (exchange bands 13 and Columns 13,46,79)
(1)(4)(7)(23)(56)(89)

The cells X map to themselves (like the diagonal cells with diagonal symmetry) and the minicolumns with a,b,c,and d to one another (same in each stack).
Since X only can be 147, the puzzle solves with singles.

udosuk wrote:I'll leave you or others to prove explicitly that all DDS grids must also have 180 symmetry:idea: ).

This is clear, because you can get to the opposite cell/number of the 180° symmetry by applying the 2 diagonal symmetries one after the other. So a number n always has to map to the same number n' (number cycle1+cycle2) in the opposite cell.
eleven
 
Posts: 1534
Joined: 10 February 2008

Postby champagne » Sun Dec 28, 2008 2:05 am

Hi eleven,

Thank you for that clear view. I'll work on it.

champagne

BTW if you have such a clear representation of Gludo pattern, I will save time getting it.
Last edited by champagne on Sun Dec 28, 2008 4:19 pm, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 5614
Joined: 02 August 2007
Location: France Brittany

Postby udosuk » Sun Dec 28, 2008 2:53 am

[Reply erased due to irrelevance.]
Last edited by udosuk on Sun Dec 28, 2008 10:01 pm, edited 3 times in total.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby eleven » Sun Dec 28, 2008 2:55 am

champagne wrote:
eleven wrote:Double diagonal symmetry is no own symmetry, but a combination of 2 diagonal symmetries (normally with different number cycles).
I am ok on that. Just one remark, it must be different number cycles due to the constraints in box 5.

You are right, when i wanted to delete "normally", i saw that you already noticed that:)
eleven wrote:A puzzle with 2 diagonal symmetries does not necessarily have the symmetries in the main and subdiagonal (where rotation by 90° shows the other symmetry on the same place), but i dont have a sample now.

Here I am lost:!: What do you mean exactly:?:

What i mean is, that for DDS you can apply 90° rotation to have the one or other diagonal symmetry in the main diagonal.
Why shouldn't it be possible, that e.g. you get from one diagonal symmetry to the other by another equivalence operation like rotating the bands ? I will try to find an example in the next days.

BTW if you have such a clear representation of Gludo pattern, I will save time getting it.

Puzzles, where you can apply Gludo, have a band (or 2 or 3) with a mapping like this:
Code: Select all
a a a |. . .|. . .
. . . |b b b|. . .
. . . |. . .|c c c

Each minirow maps to the next minirow downwards (cyclically) in the next box, a->b->c->a. So the cell cycles - like (r1c1,r2c4,r3c7) - have length 3 and the number cycles must have length 1 or 3, e.g. (1)(2)(3)(456)(789).
Now Gludo says, that the numbers in one minirow either are all from the same 3-number cycle - where i also call (1)(2)(3) a 3-number cycle - or all from different ones.
[Edit 2: my 124 sample was not correct]
Suppose for the example cycles the minirow aaa would be mixed like 145. Then the 6 in box 1 would be in row 2 or row 3, which by the symmetry would force another 5 in the first minirow of box 3 or another 4 in the first minirow of box 2.
You see, that you only can apply this, when you have 2 or 3 number cycles of length 3.

[Added:]In the class representations above BC1, BC1C2 and BC you have the Gludo property in the stacks instead of bands, but of course these are equivalent.
Last edited by eleven on Sat Dec 27, 2008 11:32 pm, edited 2 times in total.
eleven
 
Posts: 1534
Joined: 10 February 2008

Postby champagne » Sun Dec 28, 2008 8:18 pm

Hi eleven,

The stick symmetry is clearly as simple as diagonal and rotationnal ones.

I am not really surprised that it should be more frequent than others. The constraints seem lower.

I will for sure add it to the list of patterns the program looks for.

I have doubt for the gludo one. It has a planned very low frequency and I can not look for all patterns.

I am wondering whether a player without a preliminary warning would find such patterns, specially if the puzle is scrambled. The solver will do it easily, although this is requiring a little more coding that already handed patterns.


I'll follow that summary if you keep it updated. You made a very good job.

I cancel all posts polluting that summary view.

champagne
champagne
2017 Supporter
 
Posts: 5614
Joined: 02 August 2007
Location: France Brittany

Postby eleven » Sun Dec 28, 2008 10:33 pm

eleven wrote:A puzzle with 2 diagonal symmetries does not necessarily have the symmetries in the main and subdiagonal (where rotation by 90° shows the other symmetry on the same place), but i dont have a sample now.

This should be one. The puzzle has 2 diagonal symmetries, but is not double diagonal symmetric (as far i can see).
Code: Select all
 +-------+-------+-------+    +-------+-------+-------+
 | . . . | 2 4 . | 8 7 . |    | 5 6 . | . 9 2 | . . . |
 | . . . | . . 5 | 4 . 9 |    | 9 . 4 | 8 . . | . . . |
 | . . . | . 1 . | . 6 . |    | . 7 . | . 3 . | . . . |
 +-------+-------+-------+    +-------+-------+-------+
 | 2 . . | . . . | . 5 . |    | . 8 . | . . . | 2 . . |
 | 6 . 1 | . . . | 7 . 3 |    | 6 . 1 | . . . | 7 . 3 |
 | . 8 . | . . . | 2 . . |    | 2 . . | . . . | . 5 . |
 +-------+-------+-------+    +-------+-------+-------+
 | 5 6 . | . 9 2 | . . . |    | . . . | 2 4 . | 8 7 . |
 | 9 . 4 | 8 . . | . . . |    | . . . | . . 5 | 4 . 9 |
 | . 7 . | . 3 . | . . . |    | . . . | . 1 . | . 6 . |
 +-------+-------+-------+    +-------+-------+-------+
(1)(2)(3)(46)(58)(79)         (2)(5)(8)(13)(47)(69)     

After changing bands 1 and 3 and rows 4 and 6 you get the puzzle on the right side with the other D-symmetry.

Two more with the same symmetries:
Code: Select all
 +-------+-------+-------+
 | 3 . 5 | 6 8 . | . . . |
 | . 2 4 | . . . | . 8 . |
 | 8 6 1 | . . 3 | . . . |
 +-------+-------+-------+
 | 4 . . | . 7 . | . . 1 |
 | 5 . . | 9 . 4 | 8 . . |
 | . . 3 | . 6 . | 9 . . |
 +-------+-------+-------+
 | . . . | . 5 7 | 1 . 8 |
 | . 5 . | . . . | . 2 9 |
 | . . . | 1 . . | 5 7 3 |
 +-------+-------+-------+

 +-------+-------+-------+
 | . . 6 | . 5 2 | 8 . . |
 | . 2 . | 3 . . | . . . |
 | 4 . . | . . 9 | . . . |
 +-------+-------+-------+
 | . 3 . | . . . | 2 . 6 |
 | 8 . . | . . . | 5 . . |
 | 2 . 7 | . . . | . 1 . |
 +-------+-------+-------+
 | 5 . . | 2 8 . | . . 7 |
 | . . . | . . 1 | . 2 . |
 | . . . | 4 . . | 9 . . |
 +-------+-------+-------+
eleven
 
Posts: 1534
Joined: 10 February 2008

Postby champagne » Sun Dec 28, 2008 11:59 pm

cancelled
Last edited by champagne on Sun Dec 28, 2008 10:18 pm, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 5614
Joined: 02 August 2007
Location: France Brittany

Postby ronk » Mon Dec 29, 2008 12:40 am

eleven wrote:The puzzle has 2 diagonal symmetries, but is not double diagonal symmetric (as far i can see).
Code: Select all
 +-------+-------+-------+    +-------+-------+-------+
 | . . . | 2 4 . | 8 7 . |    | 5 6 . | . 9 2 | . . . |
 | . . . | . . 5 | 4 . 9 |    | 9 . 4 | 8 . . | . . . |
 | . . . | . 1 . | . 6 . |    | . 7 . | . 3 . | . . . |
 +-------+-------+-------+    +-------+-------+-------+
 | 2 . . | . . . | . 5 . |    | . 8 . | . . . | 2 . . |
 | 6 . 1 | . . . | 7 . 3 |    | 6 . 1 | . . . | 7 . 3 |
 | . 8 . | . . . | 2 . . |    | 2 . . | . . . | . 5 . |
 +-------+-------+-------+    +-------+-------+-------+
 | 5 6 . | . 9 2 | . . . |    | . . . | 2 4 . | 8 7 . |
 | 9 . 4 | 8 . . | . . . |    | . . . | . . 5 | 4 . 9 |
 | . 7 . | . 3 . | . . . |    | . . . | . 1 . | . 6 . |
 +-------+-------+-------+    +-------+-------+-------+
(1)(2)(3)(46)(58)(79)         (2)(5)(8)(13)(47)(69)

After changing bands 1 and 3 and rows 4 and 6 you get the puzzle on the right side with the other D-symmetry.

These two puzzles can be respectively morphed to ...
Code: Select all
 . . . | . . 5 | 4 9 .      . . . | . . 8 | 9 4 .
 . . . | . 1 . | . . 6      . . . | . 3 . | . . 7
 . . . | 2 4 . | 8 . 7      . . . | 2 9 . | 5 . 6
-------+-------+-------    -------+-------+-------
 . . 2 | . . . | . . 5      . . 2 | . . . | . . 8
 . 1 6 | . . . | 7 3 .      . 3 7 | . . . | 6 1 .
 8 . . | . . . | 2 . .      5 . . | . . . | 2 . .
-------+-------+-------    -------+-------+-------
 6 . 5 | . 9 2 | . . .      7 . 8 | . 4 2 | . . .
 7 . . | . 3 . | . . .      6 . . | . 1 . | . . .
 . 4 9 | 8 . . | . . .      . 9 4 | 5 . . | . . .

The puzzle on the right is merely a relabeled version of the left (1-3, 4-9, 5-8, 6-7), so are there really two diagonal symmetries:?:

Hmm, I'm probably not understanding the meaning of double-diagonal symmetric here. Does it mean that reflections about the diagonal and the anti-diagonal are both automorphic to the original:?:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby eleven » Mon Dec 29, 2008 1:37 am

Thanks ronk,

so you did find an equivalent puzzle with DDS (diagonal symmetry both at the main and subdiagonal).
I dont have a program to check that, is there a public one ?

Now to a new, exotic symmetry, DBS (it also has diagonal symmetry like 90° has 180°).

It needs a bit to see, where the cells go to. The box cycles are B159 and B287463. Each time a cell goes to the next box, it is mirrored at the mini-diagonal.
So we have 3-cycles for the cells in the main diagonal and 6-cycles else.
Code: Select all
 +-------+-------+-------+
 | 2 . 4 | . . . | . . 7 |
 | . . . | . 7 2 | . 6 . |
 | 7 . . | 8 . . | . 1 . |
 +-------+-------+-------+
 | . . 5 | 3 . 8 | . . . |
 | . 4 . | . . . | . 5 3 |
 | . 2 . | 5 . . | 6 . . |
 +-------+-------+-------+
 | . . . | . . 9 | 1 . 6 |
 | . 9 1 | . 8 . | . . . |
 | 4 . . | . 3 . | 9 . . |
 +-------+-------+-------+
 DBS (123)(456789)

Thus we know, that the main diagonal only can have 123 and this puzzles is solved.

This one needs a bit more.
Code: Select all
 +-------+-------+-------+
 | 3 . . | 2 . . | 1 . 4 |
 | . . . | . 1 7 | . 3 . |
 | . . . | 5 . . | . 6 . |
 +-------+-------+-------+
 | 2 . 8 | 1 . . | 3 . . |
 | . 1 . | . . . | . 2 5 |
 | . 4 . | . . . | 9 . . |
 +-------+-------+-------+
 | 1 . . | 3 . 6 | 2 . . |
 | . 3 9 | . 2 . | . . . |
 | 7 . . | . 8 . | . . . |
 +-------+-------+-------+
 DBS (123)(456789)

Maybe someone can find a nice symmetry move to finally solve it.

I dont think, that there are much more interesting puzzles with this symmetry, because its extremely rare.
eleven
 
Posts: 1534
Joined: 10 February 2008

Postby ronk » Mon Dec 29, 2008 2:45 am

eleven wrote:so you did find an equivalent puzzle with DDS (diagonal symmetry both at the main and subdiagonal).
I dont have a program to check that, is there a public one ?

I used gsf's sudoku.exe to find the "best symmetry", for example ...
Code: Select all
command line
sudoku -qFN -f"%#dc # %#D#sc" file.dat

where file.dat contains
...24.87......54.9....1..6.2......5.6.1...7.3.8....2..56..92...9.48......7..3....

... and it yielded the above morphs with both diagonal and antidiagonal symmetry.

I speak of clue position symmetry here. I know of no publicly available program that checks clue value symmetry. Given positional symmetry, however, it would be a simple program.

[edit: 1) added command line example; 2) removed invalid permutation output from command line]
Last edited by ronk on Wed Dec 31, 2008 8:16 pm, edited 2 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby champagne » Mon Dec 29, 2008 2:59 am

Hi,

I finally found that I had a problem in the copy paste.

Unhappily, I did not design the program to remorph the puzzle after the first symmetry had been found, so starting from orginal puzzle, the solver finds only one diagonal symmetry and tagging was necessary to solve the puzzle.

Using the Ronk's morphed form, the double diagonal symmetry appeared and the puzzle was solved by singles.

champagne
champagne
2017 Supporter
 
Posts: 5614
Joined: 02 August 2007
Location: France Brittany

Next

Return to General

cron