The New Sudoku Players' Forum

by **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.

by **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?

by **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

by **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. :?:

by **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.

by **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

by **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.

by **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.

by **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.

by **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...

by **eleven** » Tue Jan 20, 2009 11:49 pm

Thanks, udosuk,

i had edited my post at the same time

by **udosuk** » Tue Jan 20, 2009 11:50 pm

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

by **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

by **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.

by **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.

The New Sudoku Players' Forum

About Red Ed's Sudoku symmetry group