## Sudoku Symmetry Group (minimal spec)

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

### Sudoku Symmetry Group (minimal spec)

.
This is probably nothing new, but the standard Sudoku symmetry group (275 conjugacy classes, 3359232 members) can be generated from just 3 permutations, which is cool!

• rotate 90
• swap rows 1,2
• swap bands 1,2

GAP specification:
Code: Select all
`SudokuSG := Group(   # Minimal specification (3 permutations) (1,9,81,73)   (2,18,80,64) (3,27,79,55) (4,36,78,46) (5,45,77,37)  (6,54,76,28) (7,63,75,19) (8,72,74,10) (11,17,71,65)(12,26,70,56)(13,35,69,47)(14,44,68,38) (15,53,67,29)(16,62,66,20)(21,25,61,57)(22,34,60,48) (23,43,59,39)(24,52,58,30)(31,33,51,49)(32,42,50,40), (1,10)(2,11)(3,12)(4,13)(5,14)(6,15)(7,16)(8,17)(9,18), (1,28) (2,29) (3,30) (4,31) (5,32) (6,33) (7,34) (8,35) (9,36)(10,37)(11,38)(12,39)(13,40)(14,41)(15,42)(16,43)(17,44)(18,45)(19,46)(20,47)(21,48)(22,49)(23,50)(24,51)(25,52)(26,53)(27,54) );`

Mathimagics
2017 Supporter

Posts: 1275
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku Symmetry Group (minimal spec)

Hi Mathimagics,

Very cool
It doesn't take a lot of work to see that they generate the complete group.

This is probably nothing new, but

Red Ed mentions it here, but your generators are much nicer than the ones listed there (from GAP).

Cheers,
Blue.
blue

Posts: 840
Joined: 11 March 2013

### Re: Sudoku Symmetry Group (minimal spec)

Oh, nice, that's surprising for me.
Hard to imagine, how i could make a sticks symmetry swap with them.

At second thought, it's probably not that hard as i thought.
E.g. switching bands 1 and 3 can be done with a combination of switching bands 1,2 and 180 degree rotation.
Also the rows in the bands can be brought to where you need them, by switching the bands combined with 180 degree rotation, and switching rows 1,2 then.
And for the colums you make a 90 degree rotation first.

But i can't see it for the diagonal reflection. Any idea ?
Last edited by eleven on Sun Dec 16, 2018 12:59 am, edited 1 time in total.
eleven

Posts: 2077
Joined: 10 February 2008

### Re: Sudoku Symmetry Group (minimal spec)

blue wrote:Very cool
Red Ed mentions it here, but your generators are much nicer than the ones listed there (from GAP).

Cheers! I finally built a Transformation-Map to Permutation generator, which makes testing these things easier.

Ok, a question for all of you. Look at Russell/Jarvis info on number of ED Sudoku 6x6 grids (2x3 boxes):

http://www.afjarvis.staff.shef.ac.uk/sudoku/sud23gp.html

Now sadly they don't give their GAP setup code, so I can't verify this, but I immediately wonder about the indicated inclusion of "rotation" transformations. Surely rotating a 6x6 grid a quarter-turn will clobber the box properties?

I'm trying to replicate their figure of 3456 transformations over 90 conjugacy classes.

Mathimagics
2017 Supporter

Posts: 1275
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku Symmetry Group (minimal spec)

Reflection too. I don't understand that either.
eleven

Posts: 2077
Joined: 10 February 2008

### Re: Sudoku Symmetry Group (minimal spec)

.
OK, I began with explicit specification of all legal geometric operations (ie. full redundancy). I assume boxes are 2rows x 3cols.

• swap R1,R2 (rows in bands)
• swap R3,R4
• swap R5,R6
• swap C1,C2 (cols in stack 1)
• swap C1,C3
• swap C2,C3
• swap C4,C5 (cols in stack 2)
• swap C4,C6
• swap C5,C6
• swap B1,B2 (bands)
• swap B1,B3
• swap B2,B3
• swap S1,S2 (stacks)

Rotations/Reflections are either illegal, or covered by the above list.

This set produces a group with 34,560 members (valid transformations) in 110 conjugacy classes.

It also satisfyingly reduces to 3 permutations (from GAP SmallGeneratingSet function):
Code: Select all
`  (1,4)(2,3)(5,6)(7,10)(8,9)(11,12)(13,28)(14,27)(15,26)(16,25)(17,30)(18,29)(19,34)(20,33)(21,32)(22,31)(23,36)(24,35),  (1,21,5,20,4,24)(2,22,6,19,3,23)(7,15,11,14,10,18)(8,16,12,13,9,17)(25,33,29,32,28,36)(26,34,30,31,27,35),  (1,32,7,26)(2,31,8,25)(3,34,11,30)(4,35,12,27)(5,36,9,28)(6,33,10,29)(13,14)(15,16,17,18)(19,20)(21,22,23,24) `

I will try and find a "nicer" 3-permutation generator.

Also, I will test whether adding the illegal rotation/reflection transforms replicates Red ED's reported counts (3456 members, 90 classes).

Mathimagics
2017 Supporter

Posts: 1275
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku Symmetry Group (minimal spec)

.
OK, all is good, it was my bad!!

I had stuffed up the permutation tester and it was generating a bum version of the "swap stacks 1,2" permutation and claiming it was valid ....

The result of fixing this blunder was a group with 3456 members, 90 classes! Oh dear ...

They obviously just copied that list of operations from elsewhere and forgot to remove the reflections and rotation entries ...

Concordance is bliss, though getting there is a pain in the bum ... especially with my dodgy code (sigh)

The correct reported SmallGeneratingSet has 4 entries:
Code: Select all
` (2,3)(8,9)(14,15)(20,21)(26,27)(32,33),  (1,7)(2,8)(3,9)(4,10)(5,11)(6,12)(13,19)(14,20)(15,21)(16,22)(17,23)(18,24)(25,31)(26,32)(27,33)(28, 34)(29,35)(30,36),  (1,34,13,4,31,16)(2,35,14,5,32,17)(3,36,15,6,33,18)(7,28,19,10,25,22)(8,29,20,11,26,23)(9,30,21,12,27,24), (1,2,3)(4,6,5)(7,8,9)(10,12,11)(13,26,15,25,14,27)(16,30,17,28,18,29)(19,32,21,31,20,33)(22,36,23,34,24,35) `
Last edited by Mathimagics on Sun Dec 16, 2018 5:02 am, edited 1 time in total.

Mathimagics
2017 Supporter

Posts: 1275
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku Symmetry Group (minimal spec)

.
On the subject of transformations, I have a question for blue.

For SudokuP (9x9) we had 2592 transformations, to which E and F expanded this by factor of 4 to 10,368.

My naive solution canonicalisation approach (which generally has to work with much smaller transformation sets, eg PX, PWX, etc) simply applies all transformations and chooses the "smallest" representation. But in that original SudokuP canonicalisation function you gave me, you only test 16, I think, all combinations of your E,D,F,G.

I'm curious as to why this actually works, ie how the SudokuP grids can be ED distinguished by so many fewer transformations than we notionally have??? It seems both suspect, and yet at the same time miraculous!

I guess it's just me failing to grasp something elementary - after all, I'm sure that with standard Sudoku nobody actually checks all 3.35 million different transformations, or do they?

Cheers
MM

Mathimagics
2017 Supporter

Posts: 1275
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku Symmetry Group (minimal spec)

.
The reason I am recalculating these figures, by the way, is because I want not just to count the ED Sudoku6x6 grids (presumably there are just 49), but to get the actual grids.

The Burnside (Invariant counting) method counts, but does not enumerate! Ah, the magic of Group Theory!
Last edited by Mathimagics on Mon Dec 17, 2018 9:50 am, edited 1 time in total.

Mathimagics
2017 Supporter

Posts: 1275
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku Symmetry Group (minimal spec)

eleven wrote:But i can't see it for the diagonal reflection. Any idea ?

Use band & row permutations to reverse the order of the rows (r1 <-> r9, etc.), then rotate a quarter turn clockwise.
blue

Posts: 840
Joined: 11 March 2013

### Re: Sudoku Symmetry Group (minimal spec)

Mathimagics wrote:.
On the subject of transformations, I have a question for blue.

For SudokuP (9x9) we had 2592 transformations, to which E and F expanded this by factor of 4 to 10,368.

My naive solution canonicalisation approach (which generally has to work with much smaller transformation sets, eg PX, PWX, etc) simply applies all transformations and chooses the "smallest" representation. But in that original SudokuP canonicalisation function you gave me, you only test 16, I think, all combinations of your E,D,F,G.
(...)
It seems both suspect, and yet at the same time miraculous!

It was more complicated than you remember.
There was an outer loop over the 8 transformations generated by {D,F}.
Inside that, there were loops over 9 rows that can map to the row 1 position, and 6*6 ways to permute stacks & columns.
A speedup factor of ~4, was in the works ... 4 * (8*9*6*6) = 10368.

I guess it's just me failing to grasp something elementary - after all, I'm sure that with standard Sudoku nobody actually checks all 3.35 million different transformations, or do they?

It's very slow on a long list of grids -- even on a short list.

If the SudokuP code was modified for vanilla Sudoku, the number of inner loop itterations would be 2*9*6^4 = 23328, with a speedup factor of ~144 in the works.

There are other canonical forms (for full grids), where the inner loop needs only 648 itterations -- "Anchor 5" and "box-minlex", for example.

For "Anchor 5", the 648 comes from
• a transpose option (2)
• 6 * 6 ways to permute bands & stacks
• 9 choices for a cell from box 5, to be mapped to r5c5
Alternatively, it comes from
• 9 digit templates to choose from
• 2 * 6 * 6 ways to map the choice to a fixed template
For "box-minlex", the 648 comes from
• a transpose option (2)
• 9 boxes to choose from, to be mapped to the box 1 position
• 6 * 6 ways to permute rows & columns in band 1 & stack 1

Cheers.
blue

Posts: 840
Joined: 11 March 2013

### Re: Sudoku Symmetry Group (minimal spec)

blue wrote:
eleven wrote:But i can't see it for the diagonal reflection. Any idea ?

Use band & row permutations to reverse the order of the rows (r1 <-> r9, etc.), then rotate a quarter turn clockwise.

Ah, thank you. So simple, after you spelled it out ...
eleven

Posts: 2077
Joined: 10 February 2008

### Re: Sudoku Symmetry Group (minimal spec)

.
Same here! Thanks blue, for the clear, and useful, CF function exposition.

Mathimagics
2017 Supporter

Posts: 1275
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku Symmetry Group (minimal spec)

.
OK, I converted the GAP permutation list (3456 items) to transformations, plugged these into my simple CF function, and can confirm there are just 49 ED Sudoku 6x6 grids.

All is well!

Mathimagics
2017 Supporter

Posts: 1275
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku Symmetry Group (minimal spec)

How does this make sense?

The symmetry group can be seen as a quotient group of free product of a,b,c,d and e,where
a -- swapping rows 12
b -- swapping rows 13
c -- swapping bands 12
d -- swapping bands 13
e -- flipping along main diagonal

with a^2=b^2=c^2=d^2=e^2=1,
ababab=cdcdcd=1
exey=yexe(x is one of abcd, y is one of abcd)
cxcy=ycxc(x is one of abd, y is one of ab)
dxdy=ydxd(x is one of abc, y is one of ab)

Then x can be extended to strings of any length, just like
e123e4=e1ee2ee3e4=e1e e2e 4 e3e = 4e1ee2ee3e=4e123e
Finally we can get to the form
(abab)c(ab)cd(ababa)d(cdc)e(ab)c(a)cd(abab)d(cdcd)(e),
where each bracket represents
swap of rows in 1st/2nd/3rd band, swap of bands, swap of cols in 1st/2nd/3rd/tower, swap of towers, whether rows and cols are switched.
qiuyanzhe

Posts: 78
Joined: 21 August 2017
Location: China

Next