The New Sudoku Players' Forum

[Red Ed]

I understand now that out of 2x 6^8=3359232 isomorphisms, there are only 311 408 automorphisms.
...
There are 122 classes.

311409 and 123, respectively: the identity is an automorphism too.

Does it mean that there are 1134 groups of automorphisms ?

In what sense? I can't see what you're getting at here (sorry).

[udosuk]

King Roger? Pah. Nothing but a jester in the court of King Andy!

Perhaps your "King Andy" is from the Roddick family instead of the Murray family? The latter one crashed out yesterday. But anyway the former one should also be eliminated later today by "King Novak". However, I suspect all these "Kings" at the end would all be perished under the horrific inhuman power of "Emperor Rafa"...

Back to the topic...

Here's what I would need from you:

• You give me a list of "nice" symmetries. By "nice", I mean simple stuff like rotation, transposition, band/row cycling, flipping the whole grid horizontally or vertically; that sort of thing. The list must be sufficient to generate (by combining) any possible symmetry. It doesn't matter if there are some redundant symmetries in there -- in fact, it should be expected that there'll be quite a bit of redundancy. eleven's list from the first post would be a good starting point:

• You tell me the cost of each of those "nice" symmetries. The cost is a positive integer. Really nice symmetries have cost 1. Slightly less nice ones have cost up to, oh I don't know, 5?

• You give me a combination cost. This tells me how bad it is to write a symmetry as a combination of two others.

In return, I could express each of the 122 aut groups as a list of generator symmetries such that the overall cost of the each list was minimal...

Interested? Or do you want to go ahead and do this manually yourself?

My group of "nice symmetries" should be the 13 basic ones and 13 merged ones, repeatedly specified in the last few pages. I keep saying I'll formulate them nicely later but keep struggling to find time. Now that the tennis schedule is less packed perhaps I can find more time to finally get some work done. Just give me a couple more days...

In the mean time, here is something a little bit different (but still on topic of this thread). On the last page JPF cited the Maximum Minlex grid found by you:

Code: Select all

123456789
457893612
986217354
274538196
531964827
698721435
342685971
715349268
869172543

He mentioned there are 72 automorphisms, I was deeply interested and studied this grid in details during my limited free time among work/meals/sleep/tennis. Here are the early results:

This grid has Jumping Rows and Jumping Columns (hence implied Jumping Diagonals on both directions). It also has Row Sticks, Column Sticks, Diagonal Mirrors (both directions) as well as Half Turn (which is implied by double Diagonal Mirrors):

Code: Select all

r132465897
c132465879
d123456789 -> d563819427

536891247
792645138
841237596
684123759
927456381
153789624
415378962
279564813
368912475

JR: (176)(258)(394)
JC: (138)(279)(456)
J\: (195)(263)(487)
J/: (142)(357)(698)
RS: (4)(5)(6)(17)(28)(39)
CS: (2)(5)(8)(13)(46)(79)
\M: (1)(5)(9)(24)(37)(68)
/M: (3)(5)(7)(19)(26)(48)
HT: (5)(19)(28)(37)(46)

Note there are merged symmetries too (CS+JR, \M+J\ etc) which enable us to see some additional symmetries "on the fly" (e.g. if we shift r789 to the top, then there is CS: (3)(4)(9)(18)(27)(56) ).

Anyway, after some pondering, I figure that to count the number "72" by trying to identify the "independent factors" of the symmetry groups and then multiplying their orders together is a pretty naive approach, as demonstrated by eleven and me on several posts on the last 2 pages.

Here is a more sensible approach to verify the number "72" here:

Firstly, fix the centre cell r5c5. Now how many isomorphs can we generate?

Obviously, the grid as it is (identity) is the very 1st one.
\M (transpose) gives us another.
/M (anti-transpose) gives us the 3rd.
Applying both simutaneously gives us a 4th, which is essentially the same one obtained by HT (180 rotation).

Now, applying CS (column sticks) on each of these 4 can give us 4 more isomorphs. (For the unfamiliar, the CS transformation is essentially swapping each mini-column to the opposite one in the local stack, e.g. r123c1 is swapped with r789c3, r789c4 is swapped with r123c6).

Note that we don't need RS (row sticks) now since \M+CS is essentially the identical transformation.

Hence with r5c5 fixed, we get 8 isomorphs.

The next step would be using JR & JC, we can freely move each centre of the 3x3 blocks to r5c5 via whole band/whole stack shifting. And we can be sure each time we'll get new isomorphs because each of r258c258 has a different unique value.

From each of these 9 centres at r5c5 we will get 8 isomorphs. So the total number of isomorphs is 9x8=72. Voila!

From there we can freely select the independent factors:

\M (2), /M (2), CS (2), JR (3), JC (3)
or
HT (2), \M (2), CS (2), JR (3), J\ (3)

The fact that \M+JR implies JC etc should not be bothered too much. Apparently it's much easier to analyse if we seperate the order-2 & order-3 (and possibly order-9) operations and don't mix them together.

I think with some effort all 122 groups can be analysed like that. But as always it requires substantial time and effort! (I'll work hard at your request to give you a nice specification of each symmetries, and hope that the help of your program can speed up things considerably.)

In the mean time, I'm also very interested in the problem of working out this (Max Minlex) grid manually, which I think I have a very nice fully logical solution that doesn't need any machine help. But it probably belong to another thread when I finally get to write it up nicely.

[Edited: some minor corrections]

[Red Ed]

(I'll work hard at your request to give you a nice specification of each symmetries, and hope that the help of your program can speed up things considerably.)

My request was actually simpler -- just to give a list of nice symmetries; not a nice list of all symmetries. But leave it be for now: it'll take a while to get the code working, and I don't need "nice" symmetries during testing.

btw, it was Andy Murray. But I'm English, so what the hell do I care if I jinxed a Scot?

[eleven]

Thanks for the explanations, JPF (dont understand the 1134 either) and Red Ed, so finally i understand the numbers in the 2 columns (i only had noticed that the number of invariants had some relation to the commonness of the symmetry). And many thanks for updating the list with the numbers of essentially different grids.

Nice analysis, udosuk.

If you look at the list, you can see, that the max. minlex grid has QT symmetry (86) also. But of course it cannot be normalised together with DM.
This is an equivalent:

Code: Select all

 +-------+-------+-------+
 | 8 1 4 | 2 3 7 | 9 5 6 |
 | 5 6 3 | 8 9 1 | 4 2 7 |
 | 7 2 9 | 6 4 5 | 3 1 8 |
 +-------+-------+-------+
 | 1 3 5 | 7 8 9 | 2 6 4 |
 | 9 7 2 | 4 5 6 | 8 3 1 |
 | 6 4 8 | 1 2 3 | 5 7 9 |
 +-------+-------+-------+
 | 2 9 7 | 5 6 4 | 1 8 3 |
 | 3 8 6 | 9 1 2 | 7 4 5 |
 | 4 5 1 | 3 7 8 | 6 9 2 |
 +-------+-------+-------+

[Added:] You also can see in the list, that QT+DM+JD already span the 72 automorphisms (only the MC grid also has them).

[udosuk]

Perhaps your "King Andy" is from the Roddick family instead of the Murray family? The latter one crashed out yesterday. But anyway the former one should also be eliminated later today by "King Novak".

I was about to say that "I'm Aussie, so what the hell do I care if I jinxed a Serb", but then another favourite Aussie-Serb crashed out tonight, and I lost most of my enthusiasm to follow the tournament now.

If you look at the list, you can see, that the max. minlex grid has QT symmetry (86) also. But of course it cannot be normalised together with DM.

Thanks, so that's the same property with the MC grid. So we can have either CS+D\+HT or CS+D\+D/ to provide a factor of 8 in one representation or CS+QT in another.

Can someone post the full 648 different automorphed grids of the MC grid? I keep trying and could only come up with 72. Starting from the following representation:

Code: Select all

123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645

Using whole band/stack shifting I can morph each 3x3 block to the centre, giving me 9 different values for r5c5. And for each of them I can use D\, D/, HT and CS to generate 8 different grids. So a total of 9x8=72. But where are the other 576 grids? I could use MR, MC or MD to shift different values to r5c5 but most of the time I find I'm just generating duplicates to the 72 grids above. Anything I've missed?

(Added later: just saw the last remark of eleven. Will study it.)

[gsf]

Ed, can you give an example or a pointer to a method for normalizing sets of permutations
so they can be compared for equivalence

[JPF]

Can someone post the full 648 different automorphed grids of the MC grid? I keep trying and could only come up with 72. Starting from the following representation:

Code: Select all

123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645

Let x be the MC grid.
There are 648 isomorphisms (automorphisms) f such that f(x)=x.
Each automorphism f can be uniquely written as f=p.h
where :
p is a permutation of the digits (relabelling).
h is a permutation of the cells

In the subgroup of the 648 automorphisms, (f=p.h ; g=qk ; ...) let f~g be the equivalence relation :
f~g if hx=kx

It turns out that there are 72 classes.
Each class has 9 isomorphims.
By definition, in each class hx=kx

Example :
Here is one class and the cells permutation h of each :

01 03 02 07 09 08 04 06 05 19 21 20 25 27 26 22 24 23 10 12 11 16 18 17 13 15 14 55 57 56 61 63 62 58 60 59 73 75 74 79 81 80 76 78 77 64 66 65 70 72 71 67 69 68 28 30 29 34 36 35 31 33 32 46 48 47 52 54 53 49 51 50 37 39 38 43 45 44 40 42 41
22 24 23 19 21 20 25 27 26 13 15 14 10 12 11 16 18 17 04 06 05 01 03 02 07 09 08 76 78 77 73 75 74 79 81 80 67 69 68 64 66 65 70 72 71 58 60 59 55 57 56 61 63 62 49 51 50 46 48 47 52 54 53 40 42 41 37 39 38 43 45 44 31 33 32 28 30 29 34 36 35
16 18 17 13 15 14 10 12 11 07 09 08 04 06 05 01 03 02 25 27 26 22 24 23 19 21 20 70 72 71 67 69 68 64 66 65 61 63 62 58 60 59 55 57 56 79 81 80 76 78 77 73 75 74 43 45 44 40 42 41 37 39 38 34 36 35 31 33 32 28 30 29 52 54 53 49 51 50 46 48 47
30 29 28 36 35 34 33 32 31 48 47 46 54 53 52 51 50 49 39 38 37 45 44 43 42 41 40 03 02 01 09 08 07 06 05 04 21 20 19 27 26 25 24 23 22 12 11 10 18 17 16 15 14 13 57 56 55 63 62 61 60 59 58 75 74 73 81 80 79 78 77 76 66 65 64 72 71 70 69 68 67
51 50 49 48 47 46 54 53 52 42 41 40 39 38 37 45 44 43 33 32 31 30 29 28 36 35 34 24 23 22 21 20 19 27 26 25 15 14 13 12 11 10 18 17 16 06 05 04 03 02 01 09 08 07 78 77 76 75 74 73 81 80 79 69 68 67 66 65 64 72 71 70 60 59 58 57 56 55 63 62 61
45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 54 53 52 51 50 49 48 47 46 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 27 26 25 24 23 22 21 20 19 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 81 80 79 78 77 76 75 74 73
56 55 57 62 61 63 59 58 60 74 73 75 80 79 81 77 76 78 65 64 66 71 70 72 68 67 69 29 28 30 35 34 36 32 31 33 47 46 48 53 52 54 50 49 51 38 37 39 44 43 45 41 40 42 02 01 03 08 07 09 05 04 06 20 19 21 26 25 27 23 22 24 11 10 12 17 16 18 14 13 15
77 76 78 74 73 75 80 79 81 68 67 69 65 64 66 71 70 72 59 58 60 56 55 57 62 61 63 50 49 51 47 46 48 53 52 54 41 40 42 38 37 39 44 43 45 32 31 33 29 28 30 35 34 36 23 22 24 20 19 21 26 25 27 14 13 15 11 10 12 17 16 18 05 04 06 02 01 03 08 07 09
71 70 72 68 67 69 65 64 66 62 61 63 59 58 60 56 55 57 80 79 81 77 76 78 74 73 75 44 43 45 41 40 42 38 37 39 35 34 36 32 31 33 29 28 30 53 52 54 50 49 51 47 46 48 17 16 18 14 13 15 11 10 12 08 07 09 05 04 06 02 01 03 26 25 27 23 22 24 20 19 21


giving the same grid :

Code: Select all

132798465
798465132
465132798
321987654
987654321
654321987
213879546
879546213
546213879

p=q=(132798465)

JPF

[eleven]

So i neither understood the question nor the answer

How do you identify the classes ? With the number cycles (digit relabelling) ?

E.g. MD+DM (classes 10, 37) has 6 automorphisms, so this would be 3 classes of DM-equivalent cell permutations ? Or 2 classes of MD-equivalent ones ?

[udosuk]

Thanks for the attempted explanations, JPF.

So I take it there are only 72 different grids produced by automorphing the MC grid, instead of 648?

(My definition of automorphed grids: starting with the initial grid, applying transpose and/or row/column/band/stack permutations; if the grid is then transformed into a state where it can be morphed back to the initial grid via a digit remapping different to the trivial one (d123456789 -> d123456789), then it'll be counted as an automorphed grid.

I suspect Red Ed and others are counting the ones where transposing and/or row/column/band/stack permutations transform the grid back to the initial grid without any digit remapping in the figure of 648? )

As an example: with the initial grid:

Code: Select all

123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645

If we apply the following transformation:

Code: Select all

r456789123
c312645978

The grid is transformed back to the original state without any digit remapping. Do we count this as one the 648?

If you look at the list, you can see, that the max. minlex grid has QT symmetry (86) also. But of course it cannot be normalised together with DM.
This is an equivalent:

Code: Select all

 +-------+-------+-------+
 | 8 1 4 | 2 3 7 | 9 5 6 |
 | 5 6 3 | 8 9 1 | 4 2 7 |
 | 7 2 9 | 6 4 5 | 3 1 8 |
 +-------+-------+-------+
 | 1 3 5 | 7 8 9 | 2 6 4 |
 | 9 7 2 | 4 5 6 | 8 3 1 |
 | 6 4 8 | 1 2 3 | 5 7 9 |
 +-------+-------+-------+
 | 2 9 7 | 5 6 4 | 1 8 3 |
 | 3 8 6 | 9 1 2 | 7 4 5 |
 | 4 5 1 | 3 7 8 | 6 9 2 |
 +-------+-------+-------+

I think a better equivalent grid is this:

Code: Select all

415378962
279564813
368912475
684123759
927456381
153789624
536891247
792645138
841237596

... where we have QT+CS+RS+JC+JR+J\+J/.

I have a conjecture that CS+\M implies the factor of 8 (CS+RS+\M+/M+HT or CS+RS+QT) and am trying to prove it rigidly.

[JPF]

I suspect Red Ed and others are counting the ones where transposing and/or row/column/band/stack permutations transform the grid back to the initial grid without any digit remapping in the figure of 648? )

They are counting the number of automorphisms, not the number of any kind of grids.
They are 648 automorphisms of the MC grid.

As an example: with the initial grid:

Code: Select all

123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645

If we apply the following transformation:

Code: Select all

r456789123
c312645978

The grid is transformed back to the original state without any digit remapping.

Yes, and including the identity automorphism, there are 9 automorphisms having this property.

Do we count this as one the 648?

Yes, but again, don't mix up automorphims and grids

JPF

[udosuk]

They are counting the number of automorphisms, not the number of any kind of grids.
...
Yes, but again, don't mix up automorphims and grids

Thanks for clarifying. I was just dumbfounded that I couldn't find 648 "automorphed grids" for the MC grid.

Turns out there are only 72, all of which I've found.

I think I can handle the different concepts of "automorphism" and "automorphed grid" from now on.

Is there a statistical count of how many different "automorphed grids" for each of the 122 classes?

(I think we can divide automorphisms into 2 groups. Those with cell permutation only but no digit remapping and those involving both cell permutation and digit remapping. It'd be nice if we can have statistical counts of both groups for each of the 122 classes. )

[udosuk]

Another old question i had, is answered by the new list:

DBS is equivalent to a combination of D and BS (equivalence in the sense, that if a puzzle has DBS symmetry, it also has both D and BS symmetry and vice versa). I dont have a proof for the "vice versa" part.

There cant be a proof for the other direction, because there is a group, which has D (or DM, class 37) and BS (class 22, now called JD) symmetry, but not DBS (class 43, which we called DM+JD). So the naming DM+JD is all but perfect.

The reason is the same i mentioned above. If a grid has the 2 symmetries and there is an equivalent grid, where both are in normalized form, it also has the symmetry with a number 6-cycle. If there is no equivalent grid, where both are in normalized form, there is no other symmetry forced.

Here are examples for the combinations of Sticks and Jumping-Row symmetries:

Both in normalized form:

Code: Select all

 +-------+-------+-------+
 | 1 9 6 | 2 7 4 | 3 8 5 |
 | 2 7 5 | 3 8 6 | 1 9 4 |
 | 3 8 4 | 1 9 5 | 2 7 6 |
 +-------+-------+-------+
 | 5 1 8 | 6 2 9 | 4 3 7 |
 | 6 3 9 | 4 1 7 | 5 2 8 |
 | 4 2 7 | 5 3 8 | 6 1 9 |
 +-------+-------+-------+
 | 9 6 1 | 7 4 2 | 8 5 3 |
 | 8 4 2 | 9 5 3 | 7 6 1 |
 | 7 5 3 | 8 6 1 | 9 4 2 |
 +-------+-------+-------+
Sticks (1)(2)(3)(47)(58)(69)
JR (123)(456)(789)
Sticks-JR (132)(495768)

Cant be both in normalized form:

Code: Select all

                                  after DM, c56           
 +-------+-------+-------+    +-------+-------+-------+
 | 6 2 8 | 1 9 4 | 5 7 3 |    | 6 1 3 | 9 4 7 | 8 2 5 |
 | 1 9 4 | 3 7 5 | 6 2 8 |    | 2 9 7 | 1 8 5 | 4 6 3 |
 | 3 7 5 | 6 2 8 | 1 9 4 |    | 8 4 5 | 6 2 3 | 9 1 7 |
 +-------+-------+-------+    +-------+-------+-------+
 | 9 1 6 | 4 8 2 | 3 5 7 |    | 1 3 6 | 4 7 9 | 2 5 8 |
 | 7 5 3 | 9 1 6 | 4 8 2 |    | 9 7 2 | 8 5 1 | 6 3 4 |
 | 4 8 2 | 7 5 3 | 9 1 6 |    | 4 5 8 | 2 3 6 | 1 7 9 |
 +-------+-------+-------+    +-------+-------+-------+
 | 8 4 9 | 2 6 1 | 7 3 5 |    | 5 6 1 | 3 9 4 | 7 8 2 |
 | 2 6 1 | 5 3 7 | 8 4 9 |    | 7 2 9 | 5 1 8 | 3 4 6 |
 | 5 3 7 | 8 4 9 | 2 6 1 |    | 3 8 4 | 7 6 2 | 5 9 1 |
 +-------+-------+-------+    +-------+-------+-------+
Sticks (1)(24)(37)(5)(69)(8)      JR (142)(375)(698)       

I think this is not a very good example - these 2 symmetries are both shown in the grid on the right hand side:

Code: Select all

Row Sticks (1)(24)(37)(5)(69)(8)
Jumping Rows (142)(375)(698)

Note this is essentially different to the first example which is CS+JR (Column Sticks + Jumping Rows), with a different orientation of the Sticks Symmetry.

It'd be appreciated if you could construct a concrete example for the "DM & JD but no DM+JD" scenario.

(Added later: after some thinking I suspect that is also due to different orientations, e.g. \M & J/ can't be blended together, unlike \M & J\ which should always imply \M+J\. )

[Red Ed]

(I think we can divide automorphisms into 2 groups. Those with cell permutation only but no digit remapping and those involving both cell permutation and digit remapping. It'd be nice if we can have statistical counts of both groups for each of the 122 classes. )

That's barely worth bothering with. For a given solution grid, G, let CellAut(G) be the group of automorphisms that leave the digits fixed. Most of the time, CellAut(G) = {e}, the identity, so each automorphism, bar the identity, must relabel the digits.

Recall that, up to isomorphism, there are 560151 solution grids that have any non-trivial automorphisms. Call the set of those 560151 grids (arbitrary representatives of their isomorphism classes) "A". Then:

• for all bar 1507 special grids in A, CellAut(G) = {e};
• for 1504 grids in A, CellAut(G) is (isomorphic to) the group of order 3 generated by the operation "FOO": shift rows 123456789 to 231564798 and (simultaneously) stacks 123 to 231;
• for 2 grids in A, CellAut(G) is (isomorphic to) the group of order 3 generated by the operation "BAR": shift bands 123 to 231 and (simultaneously) stacks 123 to 231;
• for 1 grid in A, equivalent to the MC grid, CellAut(G) is (isomorphic to) the group of order 9 generated by operations "FOO" and "BAR" together (independently).

Clear as mud?

EDIT: typo: s/3/9/

[eleven]

I have a conjecture that CS+\M implies the factor of 8 (CS+RS+\M+/M+HT or CS+RS+QT) and am trying to prove it rigidly.

No more proof needed, you can directly read it from the list (you cant find 134 and 37 without 79 and 86), same for QT+ \M. [Added:] Please dont misunderstand me - i would appreciate a more intuitive proof very much

I think this is not a very good example - these 2 symmetries are both shown in the grid on the right hand side
...
(Added later: after some thinking I suspect that is also due to different orientations, e.g. \M & J/ can't be blended together, unlike \M & J\ which should always imply \M+J\. )

I did not spot the RS symmetry, thanks for pointing that out. You are probably right, that if JR and CS cannot be normalized in the same grid, then there is an equivalent, where JR and RS are both normalized. Cant work that out now.

[udosuk]

Recall that, up to isomorphism, there are 560151 solution grids that have any non-trivial automorphisms. Call the set of those 560151 grids (arbitrary representatives of their isomorphism classes) "A". Then:

• for all bar 1507 special grids in A, CellAut(G) = {e};
• for 1504 grids in A, CellAut(G) is (isomorphic to) the group of order 3 generated by the operation "FOO": shift rows 123456789 to 231564798 and (simultaneously) stacks 123 to 231;
• for 2 grids in A, CellAut(G) is (isomorphic to) the group of order 3 generated by the operation "BAR": shift bands 123 to 231 and (simultaneously) stacks 123 to 231;
• for 1 grid in A, equivalent to the MC grid, CellAut(G) is (isomorphic to) the group of order 9 generated by operations "FOO" and "BAR" together (independently).

Clear as mud?

Thanks, that's pretty clear.

Obviously "FOO" is equivalent to Gliding Rows and "BAR" is equivalent to Jumping Diagonals, both with 9 1-digit cycles. And the MC grid happens to be the only grid possible to have both symmetries with 9 1-digit cycles.

Should have seen that, to get a grid to transform to itself with non-trivial cell permutations, the involving symmetries must have 9 1-digit cycles. There are only 2 such symmetries among the 26 basic or merged symmetries: GR (or GC) & JD.