The New Sudoku Players' Forum

[eleven]

so the only thing that matters for grid counts is arangments of the groups

Looks nice, can you show it for the other grid with 162 automorphisms also ?

[StrmCkr]

removed.

[Red Ed]

if column/row/band swaping can replicate digit swaping and vice versa.

why not fix the grid, then sum the digit arangments rather then trying to sum the diffrent ways of fixing the cells on a grid?

We're discussing automorphisms of solution grids. An automorphism has two parts: a cells permutation (e.g. quarter turn, swap rows 4 and 5) and digit relabelling. Suppose I show you a grid and tell you that I'm thinking of one of its automorphisms, but I'm not going to tell you which one. Then: (a) if I tell you the cells permutation, you can always tell me the digit relabelling; but (b) if I tell you the digit relabelling then you cannot necessarily tell me the cells permutation. The awkward cases are, up to isomorphism, the 1507 special grids described earlier.

So it's not always a case of "vice versa", to use your words.

[Red Ed]

This is the grid with 9 symmetries, but only 18 automorphisms. I needed 3 morphs to show them all normalized, but i guess, this can be done better.

An isomorph of that grid has aut group equal to <C,RxSx,C2B>; in other words, generated by the three elements C, RxSx and C2B. My program couldn't find any nicer way of describing it using eleven's operations listed in the first post.

PS: I'm writing maps on the left, so C2B means B followed by C2.

[eleven]

StrmCkr, you are doing arbitrary things to get to the right number of automorhisms.
This grid has exactly the same properties you used to show the 162 automorphisms. So, how much has it and why ?

Code: Select all

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


[Red Ed]

Here's the grid morphed to have aut group as described previously:

Code: Select all

825746193931825674674931258467319825193258467582467319258674931319582746746193582

Code: Select all

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

I am now able to produce nicely-morphed forms of all 122 sample grids

Before running the program on the whole lot, I'm welcome requests for particular grids to be morphed, to make sure that my code is producing what the solvers around here would regard as "nice" results. eleven and udosuk -- any special requests?

[udosuk]

This is a form of the grid with 162 automorphisms and the symmetry classes
8 9 22 25 30 32 134 135 142 145

Code: Select all

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

MC (8 mirrored): (123)(456)(789)
JD (22): (194)(275)(386)
JR (25): (123)(456)(789), JC (185)(296)(374)
GR (32): (132)(465)(587), GR- (1)(2)(3)(4)(5)(6)(7)(8)(9)
CS (134): (1)(2)(3)(47)(58)(69)
CS°MC (135): (123)(486759)
CS°GR (142): (132)(495768)
CS°JR (145): (123)(486759)

After swapping rows 8 and 9:

Code: Select all

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

MR Band 2, MD B13 (9): (147)(258)(369)

Where is symmetry class 30 (1 JR, 2 GR) ?
[Added: ah, got it now, with column changes you get 9 and 30 in one grid]

Just for the sake of completeness, here is an isomorph of the last grid to show both merged symmetries (9 & 30):

Code: Select all

r456123789
c132654879

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

MR B2, MD B13: (186)(294)(375)
JR B2, GR B13: (195)(276)(384)

I don't think one can normalise all 10 automorphisms in one grid, mainly because of the imcompatibility among "JR", "GR" and "1JR2GR".

Before running the program on the whole lot, I'm welcome requests for particular grids to be morphed, to make sure that my code is producing what the solvers around here would regard as "nice" results. eleven and udosuk -- any special requests?

Just a couple randomly shuffled grids for you to test on:

Code: Select all

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

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

Good luck!

[StrmCkr]

deleted...

[Red Ed]

udosuk, a very simple morph of the first one gives:

Code: Select all

487219536915634728623857914341965287792481365568723149134578692856192473279346851

    4 7 8 2 9 1 3 6 5
    9 5 1 6 4 3 2 8 7
    6 3 2 8 7 5 1 4 9
    3 1 4 9 5 6 8 7 2
    5 8 6 7 3 2 4 9 1
    7 2 9 4 1 8 6 5 3
    8 6 5 1 2 9 7 3 4
    2 9 7 3 6 4 5 1 8
    1 4 3 5 8 7 9 2 6

That's got aut group <H,R1C1BS>, where H is half turn and the second one means: do S, then B, then C1, then R1.

The missus will kill me if I spend any more time copying/pasting grids this morning, so the second grid will have to wait.

[eleven]

Red Ed, its great, that you do this work for us, and it seems, that its pretty fine for me, how you show the grids.

I understood, that the symmetries you list, are generators of the aut group, which means, that we get all possible automorphisms by combining them in some way. Will this size of the group always be the product of the sizes of the single symmetry groups ? I called that "independant" symmetries above, again a bad name, because R1C1BS (Full Diagonals) implies the "independant" H (Half Turn).

I will try to keep better to existing mathematical terms and conventions. I also did not know, that applying B after A here is written BA. Any suggestions are welcome.

I don't think one can normalise all 10 automorphisms in one grid, mainly because of the imcompatibility among "JR", "GR" and "1JR2GR".

This is another thing i'd like to have, a table showing, which pairs of the 26 symmetries can
- Always be normalized, like DM+CS
- Sometimes be normalized, sometimes not, like MR+MD
- Never be normalized like DM+QT
- Never exist in a grid like DM+FD

[Red Ed]

I also did not know, that applying B after A here is written BA.

That's just the usual convention, which I'll stick to. By all means do it the other way round if you like -- just be clear about which you've chosen.

[Red Ed]

Just a couple randomly shuffled grids for you to test on:

(#1 elided)

+-------+-------+-------+
| 3 4 1 | 2 5 9 | 8 6 7 |
| 5 7 6 | 1 8 4 | 3 9 2 |
| 8 9 2 | 7 3 6 | 5 1 4 |
+-------+-------+-------+
| 2 8 7 | 3 6 1 | 4 5 9 |
| 6 5 9 | 8 4 7 | 2 3 1 |
| 4 1 3 | 9 2 5 | 6 7 8 |
+-------+-------+-------+
| 1 3 4 | 5 9 2 | 7 8 6 |
| 7 2 5 | 6 1 8 | 9 4 3 |
| 9 6 8 | 4 7 3 | 1 2 5 |
+-------+-------+-------+[/code]
Good luck!

Well that second one is a little more interesting.

The following morph of it has aut group <D2,S,RxSx>.

Code: Select all

756184932431259687982736154827361549143925768569847321698473215314592876275618493

Code: Select all

    7 5 6 1 8 4 9 3 2
    4 3 1 2 5 9 6 8 7
    9 8 2 7 3 6 1 5 4
    8 2 7 3 6 1 5 4 9
    1 4 3 9 2 5 7 6 8
    5 6 9 8 4 7 3 2 1
    6 9 8 4 7 3 2 1 5
    3 1 4 5 9 2 8 7 6
    2 7 5 6 1 8 4 9 3

Maybe it's time to run the code on all grids from the list of 122.

[udosuk]

udosuk, a very simple morph of the first one gives:

Code: Select all

487219536915634728623857914341965287792481365568723149134578692856192473279346851

    4 7 8 2 9 1 3 6 5
    9 5 1 6 4 3 2 8 7
    6 3 2 8 7 5 1 4 9
    3 1 4 9 5 6 8 7 2
    5 8 6 7 3 2 4 9 1
    7 2 9 4 1 8 6 5 3
    8 6 5 1 2 9 7 3 4
    2 9 7 3 6 4 5 1 8
    1 4 3 5 8 7 9 2 6

That's got aut group <H,R1C1BS>, where H is half turn and the second one means: do S, then B, then C1, then R1.

If that's what your program finds then I'm afraid there still exists some little glitches. It should have also spotted the automatically implied Mini-Diagonal (RC) group. Here are the 3 groups involved in your isomorph:

Code: Select all

FD: (128649753)
MD: (167)(245)(389)
HT: (3)(15)(27)(46)(89)

Note the major group here is of course Full-Diagonal and the ensuring Mini-Diagonal is not hard to see, but I'm still working on why Half-Turn must also be implied generally. Definitely quite hard to give a constructive proof.

I understood, that the symmetries you list, are generators of the aut group, which means, that we get all possible automorphisms by combining them in some way. Will this size of the group always be the product of the sizes of the single symmetry groups ? I called that "independant" symmetries above, again a bad name, because R1C1BS (Full Diagonals) implies the "independant" H (Half Turn).

Like I said it's a mistake to try to calculate the number of automorphisms by multiplying group orders. Take the FD grid as an example, the total 18 is given by HT (2) & FD (9), but the other group MD (3) doesn't factor at all.

I like your idea of the table of group compatibility but sorry can't afford to contribute much on that.

[udosuk]

Well that second one is a little more interesting.

The following morph of it has aut group <D2,S,RxSx>.

Code: Select all

756184932431259687982736154827361549143925768569847321698473215314592876275618493

Code: Select all

    7 5 6 1 8 4 9 3 2
    4 3 1 2 5 9 6 8 7
    9 8 2 7 3 6 1 5 4
    8 2 7 3 6 1 5 4 9
    1 4 3 9 2 5 7 6 8
    5 6 9 8 4 7 3 2 1
    6 9 8 4 7 3 2 1 5
    3 1 4 5 9 2 8 7 6
    2 7 5 6 1 8 4 9 3

That grid is in fact the "Maximum Minlex Grid", with a total of 72 automorphisms. The basic symmetry groups include:

JR: (197)(264)(358)
JD: (134)(295)(678)
J\: (156)(273)(498)
J/: (182)(369)(475)
CS: (2)(4)(6)(13)(59)(78)
RS: (2)(5)(9)(17)(38)(46)
\M: (2)(3)(7)(18)(45)(69)
/M: (1)(2)(8)(37)(49)(56)
HT: (2)(18)(37)(46)(59)

Also if you swap top & bottom band:

QT: (2)(1783)(4965)

Maybe it's time to run the code on all grids from the list of 122.

Only if you're sure the program works fine...

[Red Ed]

If that's what your program finds then I'm afraid there still exists some little glitches. It should have also spotted the automatically implied Mini-Diagonal (RC) group.

You're misunderstanding what the program does. It doesn't try to find all types of symmetry: that was done a while back in my annotated list of 122 example grids. Instead, it finds a "nice" morph of the grid whose automorphism group can be described concisely -- as promised earlier. In this case, the most concise description the program could find was <H,R1C1BS>, which is one heck of a lot shorter than your description. And the corresponding morph of the grid is as shown (in 9x9 form; I mistakenly didn't also morph the one-liner in that case).

Remember that <A,B,C,...> means the group generated by A,B,C,... -- for example, including transformations like AABBCABBCAB. <H,R1C1BS> is a complete description of the aut group for the morphed grid.