About Red Ed's Sudoku symmetry group

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

Postby eleven » Mon Jan 19, 2009 3:43 am

udosuk wrote:And I'd be interested in how many of these 26 symmetries the Most Canonical grid (with 648 automorphisms) possess.:?:

Grrr, again i cant find the MC grid in its originally posted form. Maybe someone can post it (or a link).
But it has diagonal, column and row sticks (see above), MR, MD, GR and JD symmetries. Multiplies to 648 automorphisms.
eleven
 
Posts: 1662
Joined: 10 February 2008

Postby udosuk » Mon Jan 19, 2009 4:29 am

eleven wrote:To complete the symmetries with 2^n automorphisms, Diagonal + Column Sticks + Row Sticks symmetries give the one with the 8 automorphisms (and 25 fixed cells).
Sample puzzle:
Code: Select all
 +-------+-------+-------+
 | . 5 . | 1 . 7 | . . 8 |
 | 3 . . | 4 . . | 1 . . |
 | . . 6 | 3 . 9 | . 5 . |
 +-------+-------+-------+
 | 4 1 5 | . . . | 6 . 7 |
 | . . . | . . . | . . . |
 | 8 . 9 | . . . | 4 3 5 |
 +-------+-------+-------+
 | . 4 . | 6 . 1 | 9 . . |
 | . . 3 | . . 5 | . . 1 |
 | 7 . . | 8 . 3 | . 4 . |
 +-------+-------+-------+

\M: (14)(2)(35)(6)(78)(9)
CS: (1)(2)(3)(45)(67)(89)
RS: (13)(2)(4)(5)(68)(79)

I really need to get a grip on these concepts. If only that it's as simple as 8=2x2x2. But I found 2 more "order 2" symmetries:

/M: (15)(2)(34)(69)(7)(8)
HT: (13)(2)(45)(69)(78)

So how does it hold up? If 2^5=32 then where did the other 24 automorphisms disappear?:?:

(Perhaps the 3 essentially independent order-2 symmetries here are: HT+DM+LS.:idea: )

eleven wrote:Grrr, again i cant find the MC grid in its originally posted form. Maybe someone can post it (or a link).
But it has diagonal, column and row sticks (see above), MR, MD, GR and JD symmetries. Multiplies to 648 automorphisms.

This is one of the forms:

Code: Select all
897231564
231564897
564897231
789123456
123456789
456789123
978312645
312645978
645978312

From there I see most of the order-2,3 basic groups existing (in both orientations too)::!:

HT: (19)(28)(37)(46)(5)
QT: (1397)(2684)(5)
RS: (17)(28)(39)(4)(5)(6)
CS: (13)(2)(46)(5)(79)(8)
MR: (123)(456)(789)
MC: (147)(258)(369)
M\: (159)(267)(348)
M/: (168)(249)(357)
JR: (147)(258)(369)
JC: (132)(465)(798)
GR: (174)(285)(396) or (1)(2)(3)(4)(5)(6)(7)(8)(9)
GC: (123)(456)(789) or (1)(2)(3)(4)(5)(6)(7)(8)(9)
J\: (168)(249)(357)
J/: (195)(276)(384)

The only one I didn't see clearly is Diagonal Mirror. Are you sure it's there?

Anyway, my guess of the independent factors here are:
QT (4), LS (2), ML (3), MD (3), JL (3), JD (3)
(GL could be an incidential product of ML+JL)
So what is 4x2x3x3x3x3?:)
Last edited by udosuk on Mon Jan 19, 2009 12:37 am, edited 1 time in total.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby ronk » Mon Jan 19, 2009 4:33 am

eleven wrote:i cant find the MC grid in its originally posted form. Maybe someone can post it (or a link).

From a July 2005 dukuso post ...
Code: Select all
123456789
456789123
789123456
234567891
567891234
891234567
345678912
678912345
912345678
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby udosuk » Mon Jan 19, 2009 4:39 am

ronk wrote:From a July 2005 dukuso post ...
Code: Select all
123456789
456789123
789123456
234567891
567891234
891234567
345678912
678912345
912345678

I don't think that is the Most Canonical grid... Most Intuitive grid perhaps...

Code: Select all
Most Canonical grid (normalised form)

123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645

Oh crap! I just saw Diagonal Mirrors in this form too!

\M: (1)(24)(37)(5)(68)(9)
/M: (15)(2)(38)(4)(67)(9)

So how do we calculate the figure 648 from all these symmetries?:?:

Added later:

I get it. QT is subsumed by HT+DM. So HT+DM+LS gives us the factor of 2x2x2=8. The factor of 3x3x3x3=81 might be generated by ML+MD+JL+JD but I'm not so sure. Note MR+DM yields MC and MR+MC yields MD. So MR+DM should make both MC & MD dependent. Perhaps it's ML+JL and then one of the order-9 groups?

Also from your earlier post:

eleven wrote:I found it now, a puzzle can have both Column Sticks and Row Sticks symmetry. This gives 17 fixed cells like for DDS (9 for each symmetry, the one in the center is common).
Here is a sample:
Code: Select all
 +-------+-------+-------+
 | 3 . . | . . 7 | . 8 5 |
 | . . . | 5 . . | . . . |
 | . 6 5 | . . 9 | 1 . . |
 +-------+-------+-------+
 | . 1 . | . . . | 7 . 6 |
 | 7 . 6 | . . . | 9 . 8 |
 | 9 . 8 | . . . | . 3 . |
 +-------+-------+-------+
 | . . 3 | 6 . . | 4 9 . |
 | . . . | . . 4 | . . . |
 | 4 7 . | 8 . . | . . 1 |
 +-------+-------+-------+

CS: (1)(2)(3)(45)(67)(89)
RS: (2)(4)(5)(13)(68)(79)

HT: (13)(2)(45)(69)(78)

I suspect the independent factors here are in fact HT+LS. But I can't see why HT+CS yields RS etc.:?:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby eleven » Mon Jan 19, 2009 6:56 am

Thanks ronk for the MC puzzle. I think i searched and cerfed for it for half an hour without success.

Wow, i was not aware, that so much combinations of symmetries are equivalent !
Every time i think, i am finished with this topic, there are new aspects:)

Hope to have time soon to think about it again, but this week is full now.
eleven
 
Posts: 1662
Joined: 10 February 2008

Postby coloin » Mon Jan 19, 2009 10:56 pm

The MC grid gets around.

It turned up as one the 3 e.d. stormdoku grids
Code: Select all
+---+---+---+
|123|...|.4.|
|456|231|.7.|
|789|...|.1.|
+---+---+---+
|.4.|123|...|
|.7.|456|231|
|.1.|789|...|
+---+---+---+
|...|.4.|123|
|231|.7.|456|
|...|.1.|789|
+---+---+---+  puzzle completes to a morph of the MC grid


C
coloin
 
Posts: 1662
Joined: 05 May 2005

Postby ronk » Tue Jan 20, 2009 2:13 am

udosuk wrote:
ronk wrote:From a July 2005 dukuso post ...
Code: Select all
123456789
456789123
789123456
234567891
567891234
891234567
345678912
678912345
912345678

I don't think that is the Most Canonical grid... Most Intuitive grid perhaps...

My excuse ... I was mesmerized:) by dukuso's "grid fill equation" ... A(i,j)=1+(3*((i-1)%3)+(i-1)/3+j)%9 ... where i,j are (base 1) row,col numbers.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby eleven » Tue Jan 20, 2009 4:28 am

Nice formula:)

Just some remarks to yesterday's posts.

udosuk wrote:
eleven wrote:I found it now, a puzzle can have both Column Sticks and Row Sticks symmetry.

HT: (13)(2)(45)(69)(78)
I suspect the independent factors here are in fact HT+LS. But I can't see why HT+CS yields RS etc.:?:

Also CS and RS are "independant" and imply HT. So its a matter of taste, which 2 you take to define the symmetry.

For the symmetry with 8 automorphisms its enough to have DM and CS (because this combination already has 8-cycles). This means that DM+CS implies RS, HT, DDS and QT, though i cant see, how (especially for QT).

udosuk wrote:So how do we calculate the figure 648 from all these symmetries?:?:
...
I get it. QT is subsumed by HT+DM. So HT+DM+LS gives us the factor of 2x2x2=8. The factor of 3x3x3x3=81 might be generated by ML+MD+JL+JD but I'm not so sure. Note MR+DM yields MC and MR+MC yields MD. So MR+DM should make both MC & MD dependent. Perhaps it's ML+JL and then one of the order-9 groups?

I dont think, that QT is subsumed by HT+DM, but DDS should follow from them.
So for the 8 i am rather sure, you can take DM+RS.
For the 81 i guess you can take any two out of (MR,MC,MD), one out of (JR,GR,JD) and (another) one out of (JC,GC,JD).
Then there could not be a basic 9-cycle in MC.
eleven
 
Posts: 1662
Joined: 10 February 2008

Postby eleven » Tue Jan 20, 2009 7:27 pm

Hm, after looking at dukuso's formula again, i think, that 3 symmetries should be enough to force all the 648 automorphisms, e.g. MR, MD and JR.

[Added:] And (thanks to StrmCkr) the MC grid has all the 26 symmetries - its just a matter of finding them.

[Edit2:]Two mistakes: I thought, dukuso's grid and the MC grid would be isomorphic, but this is not the case:(
Nevertheless it might be possible, that 3 symmetries already lead to the 648 automorphisms (?) Cant verify that now.
It is not true, what StrmCkr claimed, that the MC grid has all 26 symmetries. There is no basic 9-cycle symmetry in it, as i assumed earlier.
eleven
 
Posts: 1662
Joined: 10 February 2008

Postby udosuk » Tue Jan 20, 2009 11:45 pm

eleven wrote:Hm, after looking at dukuso's formula again, i think, that 3 symmetries should be enough to force all the 648 automorphisms, e.g. MR, MD and JR.

[Added:] And (thanks to StrmCkr) the MC grid has all the 26 symmetries - its just a matter of finding them.

Interesting... but I need some time to investigate and verify...

Are you sure dukuso's formula is describing the correct Most Canonical grid, which is any isomorph of the following 2 forms:

Code: Select all
Most Canonical (MC) grid

123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645

897231564
231564897
564897231
789123456
123456789
456789123
978312645
312645978
645978312


... instead of the Most Intuitive grid, mistakenly quoted by ronk last time:

Code: Select all
Most Intuitive grid (note: this is NOT the MC grid)

123456789
456789123
789123456
234567891
567891234
891234567
345678912
678912345
912345678


... or the Minlex grid, the 3rd of the trio of most recognised basic solution grids for beginners:

Code: Select all
Minlex grid

123456789
456789123
789123456
214365897
365897214
897214365
531642978
642978531
978531642

:?:

Added later:

Just saw that you've realised your mistakes...
Last edited by udosuk on Tue Jan 20, 2009 7:49 pm, edited 1 time in total.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby eleven » Tue Jan 20, 2009 11:49 pm

Thanks, udosuk,

i had edited my post at the same time:)
eleven
 
Posts: 1662
Joined: 10 February 2008

Postby udosuk » Tue Jan 20, 2009 11:50 pm

Hmm... a problem that we're simutaneously reading and (re)editing our posts...:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby JPF » Wed Jan 21, 2009 4:30 am

udosuk wrote: Minlex grid, the 3rd of the trio of most recognised basic solution grids for beginners:

Code: Select all
Minlex grid

123456789
456789123
789123456
214365897
365897214
897214365
531642978
642978531
978531642

Actually, it's the minimum minlex with 3 automorphisms.

While ago, Red Ed gave the maximum minlex :

Code: Select all
123456789
457893612
986217354
274538196
531964827
698721435
342685971
715349268
869172543
72 automorphisms

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

Postby eleven » Wed Jan 21, 2009 6:11 am

eleven wrote:Nevertheless it might be possible, that 3 symmetries already lead to the 648 automorphisms (?) Cant verify that now.
At least i can say, that the 3 symmetries in this grid

Code: Select all
Most Canonical grid (normalised form)

123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645

MR (123)(456)(789)
MD (159)(267)(348)
JR (147)(258)(369)


(and those you get by a common renumbering) only can be in equivalent grids (morphs of MC) and thus always imply all the other symmetries of MC.

This follows from
- 1 number in a band fixes the whole band (MR+MD the box, JR the other boxes)
- switching 2 bands preserves the 3 symmetries
- cycling the rows in a band preserves the 3 symmetries
- cycling the columns in all stacks the same way preserves the 3 symmetries

Then you always can transform a grid with these symmetries so, that you bring the 2 in the column of the 1 in box 1 (whereever it is) to the same minirow and -column in box 4 and same for the 3 in box 7 (23 cant be in the same minicolumn). Then cycle all rows in the bands and all columns in the stacks to move 1 to r1c1 and you must have the MC grid above.

But is it possible, that other grids have the 3 symmetries with other number cycles ? The numbers of one cycle in MR always have to be in different cycles of MD. Same must hold for MR/JR and MD/JR. This should mean, that (with given number cycles for MR/MD) only cycles for JR are possible, which correspond to changing the columns in 2 stacks - and maybe switching the stacks (giving equivalents to MC again).

So if i made no mistake, it is shown that the symmetries MR+MD+JR imply the symmetries
MC, JC, GR, GC, JD, HT, QT, DM, DDS, DM+JD, DM+MD, CS, RS, CS+MC, RS+MR, CS+JR, RS+JC, CS+GR, RS+GC:)

[Edit:] This is not correct, see next page.
Last edited by eleven on Sun Jan 25, 2009 2:31 am, edited 1 time in total.
eleven
 
Posts: 1662
Joined: 10 February 2008

Postby eleven » Thu Jan 22, 2009 9:34 pm

MR+MD imply HT+RS+CS (and trivially MC):

Since each number in a box fixes the whole box, you can bring every MR+MD grid to this form, where the x are the remaining possible cells for 1.

Code: Select all
 1 2 3 | 7 8 9 | 4 5 6
 4 5 6 | 1 2 3 | 7 8 9
 7 8 9 | 4 5 6 | 1 2 3
-----------------------
 3 1 2 | . . . | . . .
 6 4 5 | . x x | . x x
 9 7 8 | . x x | . x x
-----------------------
 2 3 1 | . . . | . . .
 5 6 4 | . x x | . . .
 8 9 7 | . x x | . . .


So we have maximum 16 grids and it turned out, that only those 3 are not equivalent:
Code: Select all
123789456456123789789456123312978645645312978978645312231897564564231897897564231
123789456456123789789456123312978564645312897978645231231897645564231978897564312
123789456456123789789456123312978564645312897978645231231564978564897312897231645

The first one is the MC grid, the 2nd has 108 (27*4) automorphisms and the 3rd one 72 (9*8).
Since i saw two CS sticks symmetries in the second (with fixed numbers 147 and 369 resp.), it must have the HT+CS+RS symmetry.

[Edit:] This is not correct, see next page.
Last edited by eleven on Sun Jan 25, 2009 2:31 am, edited 1 time in total.
eleven
 
Posts: 1662
Joined: 10 February 2008

PreviousNext

Return to General