## About Red Ed's Sudoku symmetry group

Everything about Sudoku that doesn't fit in one of the other sections
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: 1907
Joined: 10 February 2008

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

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
`897231564231564897564897231789123456123456789456789123978312645312645978645978312`

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

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

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)123456789456789123789123456231564897564897231897231564312645978645978312978312645`

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?

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?

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

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

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: 1738
Joined: 05 May 2005

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

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

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

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) grid123456789456789123789123456231564897564897231897231564312645978645978312978312645897231564231564897564897231789123456123456789456789123978312645312645978645978312`

... 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)123456789456789123789123456234567891567891234891234567345678912678912345912345678`

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

Code: Select all
`Minlex grid123456789456789123789123456214365897365897214897214365531642978642978531978531642`

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

Thanks, udosuk,

i had edited my post at the same time
eleven

Posts: 1907
Joined: 10 February 2008

Hmm... a problem that we're simutaneously reading and (re)editing our posts...
udosuk

Posts: 2698
Joined: 17 July 2005

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

Code: Select all
`Minlex grid123456789456789123789123456214365897365897214897214365531642978642978531978531642`

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

While ago, Red Ed gave the maximum minlex :

Code: Select all
`123456789457893612986217354274538196531964827698721435342685971715349268869172543`
72 automorphisms

JPF
JPF
2017 Supporter

Posts: 3754
Joined: 06 December 2005
Location: Paris, France

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)123456789456789123789123456231564897564897231897231564312645978645978312978312645MR (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: 1907
Joined: 10 February 2008

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
`123789456456123789789456123312978645645312978978645312231897564564231897897564231123789456456123789789456123312978564645312897978645231231897645564231978897564312123789456456123789789456123312978564645312897978645231231564978564897312897231645`

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

PreviousNext