Sudoku Symmetry Group (minimal spec)

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

Sudoku Symmetry Group (minimal spec)

Postby Mathimagics » Sat Dec 15, 2018 9:14 pm

.
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! 8-)

  • 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)
 );
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Sudoku Symmetry Group (minimal spec)

Postby blue » Sat Dec 15, 2018 11:23 pm

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: 975
Joined: 11 March 2013

Re: Sudoku Symmetry Group (minimal spec)

Postby eleven » Sat Dec 15, 2018 11:42 pm

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: 3082
Joined: 10 February 2008

Re: Sudoku Symmetry Group (minimal spec)

Postby Mathimagics » Sun Dec 16, 2018 12:59 am

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Sudoku Symmetry Group (minimal spec)

Postby eleven » Sun Dec 16, 2018 1:12 am

Reflection too. I don't understand that either.
eleven
 
Posts: 3082
Joined: 10 February 2008

Re: Sudoku Symmetry Group (minimal spec)

Postby Mathimagics » Sun Dec 16, 2018 3:31 am

.
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).
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Sudoku Symmetry Group (minimal spec)

Postby Mathimagics » Sun Dec 16, 2018 4:07 am

.
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 .... :shock:

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

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Sudoku Symmetry Group (minimal spec)

Postby Mathimagics » Sun Dec 16, 2018 5:00 am

.
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
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Sudoku Symmetry Group (minimal spec)

Postby Mathimagics » Sun Dec 16, 2018 5:16 am

.
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! 8-)
Last edited by Mathimagics on Mon Dec 17, 2018 9:50 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Sudoku Symmetry Group (minimal spec)

Postby blue » Sun Dec 16, 2018 6:40 am

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: 975
Joined: 11 March 2013

Re: Sudoku Symmetry Group (minimal spec)

Postby blue » Sun Dec 16, 2018 8:56 am

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: 975
Joined: 11 March 2013

Re: Sudoku Symmetry Group (minimal spec)

Postby eleven » Sun Dec 16, 2018 10:34 am

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: 3082
Joined: 10 February 2008

Re: Sudoku Symmetry Group (minimal spec)

Postby Mathimagics » Mon Dec 17, 2018 2:04 am

.
Same here! Thanks blue, for the clear, and useful, CF function exposition.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Sudoku Symmetry Group (minimal spec)

Postby Mathimagics » Mon Dec 17, 2018 6:09 am

.
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! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Sudoku Symmetry Group (minimal spec)

Postby qiuyanzhe » Mon Dec 17, 2018 8:30 am

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: 94
Joined: 21 August 2017
Location: China

Next

Return to General