The New Sudoku Players' Forum

[udosuk]

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

Well, in that case I wonder why you include the "H" at all because "R1C1BS" should automatically imply "H", like it automatically imply "MD" (in the 122 groups you generated, only one group contains FD (23) and it also contains MD (10) & HT (79)). Of course that would show us how the total 18 is generated (2x9) but I'm still confused about the criteria for which groups are "critical" and which are not.

[Red Ed]

Re criteria - I edited my previous post but it disappeared when your post started a new page! See here.

[Red Ed]

I wonder why you include the "H" at all because "R1C1BS" should automatically imply "H"

If you left out "H", you'd get <R1C1BS> which is a smaller group. The aim is to be able to show the <...foo...> description of an aut group and have the reader be able to deduce all the symmetries without having to know anything special about what is/isn't possible in real sudokus.

For example, you shouldn't have to cross-check against this list in order to understand the group.

[udosuk]

Re criteria - I edited my previous post but it disappeared when your post started a new page! See here.

Okay, I guess I understand about the criteria now. Thanks for the reference.

And I'm sure the product of the listed groups is not always the total of automorphisms, as demonstrated in my 2nd grid - <D2,S,RxSx> gives us D2(4), S(3), RxSx(2), which only multiply to 24 instead of the correct answer 72, since it didn't count the ensuring B(3) given by D+S.

But I'd still like to see 2 more things in the next report:

1. all involved symmetry groups - including the orientations. For example, we need to distinguish JR+CS & JC+CS, as simply "25+134" is not good enough. Also in cases like my 2nd grid it need to specify both JR & JC instead of just "25". Note \ & / also need to be distinguished in case of diagonals.

2. The absolute minimum set of groups which characterise the specific case. For example, regarding my 1st grid, the group FD (R1C1BS) is enough to represent the whole case among the 122 without ambiguity. That way we can easily see what interesting cases to study where some groups implicitly imply other groups e.g. why FD implies HT.

Thanks!

[Red Ed]

1. all involved symmetry groups - including the orientations. For example, we need to distinguish JR+CS & JC+CS, as simply "25+134" is not good enough.

I agree that "25+134" doesn't tell you the relative orientations of the 25 and 134 parts; nor was it intended to. I think that listing aut groups will get you closer to what you're looking for. Let me do that before making any other modifications.

2. The absolute minimum set of groups which characterise the specific case. For example, regarding my 1st grid, the group FD (R1C1BS) is enough to represent the whole case among the 122 without ambiguity.

Can you be more precise? Let G be a group. Call G "definitive" if only one of the 122 aut groups contains (something isomorphic to) G. Some of the 122 aut groups will be definitive, others not (e.g. the MC grid's group is definitive, but the group <D> is not). Are you looking for a list of the definitive aut groups and, for each, a smallest definitive subgroup? Or something else?

[udosuk]

Are you looking for a list of the definitive aut groups and, for each, a smallest definitive subgroup?

Something like that I guess. But I probably don't need the whole list of all possible definitive aut groups.

If the smallest subgroup consists of a single basic symmetry group, then it's easy (e.g. my 1st grid which is FD or "R1C1BS" or 23). You just need to check if a single group uniquely exists in that class among the 122 classes. But there are at most 13 of these only (or 26 if you also count the merged symmetry groups).

However, in most of the cases, the "smallest subgroup" we're looking at consists of 2 or 3 or more of the basic symmetries. In that case it might take longer to find (for example, if the "definitive group" consists of 6 basic symmetries, then you need to run C(6,2)=15 times to check all the groups of 2, then C(6,3)=20 times to check all the groups of 3. And I believe most of the cases the answer is not unique - there could be several different "smallest subgroup" enough to define the whole class.

Look, if it's too difficult, don't bother too much. It's not too important.

[Red Ed]

I'm not sure I see the point right now, so let's put that aside for a bit.

I'll be back in a couple of days when I've tweaked the code to attack all 122 aut groups, giving nice presentations of each. (There's nothing big in the tweaking: it's just about doing the i/o cleanly.)

[udosuk]

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.

8 28 30 32 134 135 142 143 144

Code: Select all

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

MC (8 mirrored): (132)(468)(579)
CS (134): (1)(2)(3)(47)(58)(69)
CSMC (135): (132)(498765)
CSGR (142): (132)(498765) [Edited: this line should be under the 2nd isomorph instead]
CSJR/B2GR/B13 (143): (123)(456789) [Edited: this line should be under the 3rd isomorph instead]

r23, r78:

Code: Select all

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

GR (32): (1)(2)(3)(4)(5)(6)(7)(8)(9)

r46:

Code: Select all

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

2 JR, 1 GR (28): (132)(468)(579)
1 JR/B2, 2 GR/B13 (30): (231)(486)(597)
CSGR/B2JR/B13 (144): (132)(498765)

Note this class (with 18 automorphisms and 9 different symmetries) is not hard to analyse, with only 5 basic symmetries to consider:

Column-Sticks (order-2)
Mini-Columns (order-3)
Gliding-Rows (order-3)
1 Jumping-Rows 2 Gliding-Rows (order-3)
1 Gliding-Rows 2 Jumping-Rows (order-3)

The 4 remaining symmetries are merged-symmetries between CS and each of the order-3 symmetries. I tend to ignore these in my analysis, since they're giving me nothing interesting except increasing the total number of existing symmetry groups.

Note, for a pair of trained eyes, one can "see" all 5 basic symmetries in the following isomorph:

Code: Select all

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

CS: (1)(2)(3)(47)(58)(69)
MC: (132)(468)(579)
JR @ r456, GR\ @ r123789: (123)(486)(597)
GR/ @ r456, JR @ r123789: (132)(468)(579)
GR\ @ r456, GR/ @ r123789: (1)(2)(3)(4)(5)(6)(7)(8)(9)

Obviously "1 GR\ 2 GR/" is equivalent to (global) GR. But if one insists on displaying all GRs in the orientation of GR\ then I guess we do need 3 different isomorphs to normalise all 5 basic symmetries.

As for the matter of counting the 18 automorphisms, I found a new method to count:

Note the (trivial) identity transformation gives us 1 automorphism to start with.

For each of the 4 order-3 symmetries, we can generate 2 extra automorphisms. So now we have a total of (1+2*4)=9.

For each of these 9 automorphisms, using CS we can generate 1 extra, i.e. CS doubles the above total.

Therefore the total number of automorphism is (1+2*4)*2=18.

I suspect we can adopt this approach to count the number of automorphisms in other grids, but need more work to formulate it nicely.

[Red Ed]

udosuk, I'd be interested to know whether the isomorph below is, to "trained eyes", better or worse than the one you gave - and why.

Code: Select all

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

The automorphism group is <C,RxSx,C2B>.

[Red Ed]

udosuk, upon re-reading some of the posts above, it seems that your criteria for a nice morph differ from mine: you want to see as many symmetries as possible in their natural form; I want to specify the aut group in as concise a form as possible.

If I understood that correctly, your requirements are much easier to fulfil than mine. I would suggest doing so as follows. You give me a list of every symmetry that you would like to see in the morphed grid, and a score for each. E.g. "D" might be worth 10 points, "D2" just 5. Probably the best score is 1 point for every symmetry in its natural form - whatever you want that to mean - and 0 for everything else. Make sure the symmetries are described precisely! Then it's a simple job to write a program to find a morph with maximum score.

[udosuk]

udosuk, I'd be interested to know whether the isomorph below is, to "trained eyes", better or worse than the one you gave - and why.

Code: Select all

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

The automorphism group is <C,RxSx,C2B>.

Almost the same, but I think eleven and I are more used to see Column Sticks than Row Sticks, so a transpose of the grid could be more comfortable to the eyes.

These are the 5 basic symmetry groups I can directly "see" from it:

RS: (1)(2)(3)(47)(58)(69)
MR: (123)(486)(597)
JC @ c456, GC/ @ c123789: (123)(486)(597)
GC\ @ c456, JC @ c123789: (132)(468)(579)
GC/ @ c456, GC\ @ c123789: (1)(2)(3)(4)(5)(6)(7)(8)(9)

udosuk, upon re-reading some of the posts above, it seems that your criteria for a nice morph differ from mine: you want to see as many symmetries as possible in their natural form; I want to specify the aut group in as concise a form as possible.

Just do what you like for the next report. Because in most cases I think we can't display all symmetries in one isomorph (e.g. \M+/M & QT) anyway. If we can't do the best for this criteria, then might as well set it to suit another criteria better.

If I understood that correctly, your requirements are much easier to fulfil than mine. I would suggest doing so as follows. You give me a list of every symmetry that you would like to see in the morphed grid, and a score for each. E.g. "D" might be worth 10 points, "D2" just 5. Probably the best score is 1 point for every symmetry in its natural form - whatever you want that to mean - and 0 for everything else. Make sure the symmetries are described precisely! Then it's a simple job to write a program to find a morph with maximum score.

I'm not sure that's easy - anyway, here is a try:

(Just a note - I'm more comfortable using my own 2-letter codes for symmetries then your/eleven's "D", "RxSx" etc, so pardon for not using them.)

Each of HT (order-2) & the order-9 groups (FR/FC, WR/WC, BR/BC, FD) gets 30 pts, because they're the hardest to see from a shuffled grid. Note the order-9 groups implicitly imply HT anyway, so both should be displayed.

The mixed order-9 groups (e.g. 1FR2WR, 1WR2FR) gets 24 pts, 80% of the pure ones.

If we have DDS (\M + /M), it's worth 20 pts, as I think it gives us a better view than QT (in case it also exists) for other groups.

Also same for DSS (Double Sticks Symmetries) (CS+RS), 20 pts.

Each of individual \M, /M, CS, RS gets 10 pts.

QT gets 8 pts.

Each of the order-3 groups (MR/MC, MD, JR/JC, JD, GR/GC in any orientation) gets 5 pts (they're the easiest to see from a shuffled grid).

Each of the mixed order-3 groups (e.g. 1MR2MD, 1JR2GR) gets 4 pts, again 80% of the pure forms.

(Note: in case of double orientations (e.g. JR+JC), make sure both are displayed and scores counted.)

(Note 2: for the mixed groups (1AA2BB) make sure the 1-group (AA) is always displayed in the middle band/stack and the 2-group (BB) on the sides.)

That's about it, let's see if it works well.

[Red Ed]

What time is it in Sydney?! Surely you should be asleep!

[udosuk]

What time is it in Sydney?! Surely you should be asleep!

That's a comment I don't appreciate.

In the case of personal lifestyle/work pattern probing/stereotyping you're more than welcomed to suss me as a Vampire.

[Red Ed]

So let's check I've understood the requirement.

Take a look at the list below, which expands eleven's by (a) adding transposed symmetries e.g. MC in addition to the existing MR, and (b) including a score.

Code: Select all

1. Fixed boxes
 5   Mini-Rows (MR)         C           8    107.495.424   3  0  N equivalent to Mini-Columns (MC)
 5   MC                     R           ----------------------------------------------------------
 4   2 MR, 1 MD             CR1         7     21.233.664   3  0  Y
 4   1 MR, 2 MD             CR1R2       9      4.204.224   3  0  Y
 5   Mini-Diagonals(MD)     CR         10      2.508.084   3  0  Y

2. Boxes move in bands
 5   Jumping-Rows (JR)      S          25     14.837.760   3  0  N
 5   JC                     B          ---------------------------
 4   2 JR, 1 GR             SR1        28      2.085.120   3  0  Y
 4   1 JR, 2 GR             SR1R2      30        294.912   3  0  Y
 5   Gliding-Rows (GR)      SR         32      6.342.480   3  0  Y
 5   GC                     BC         ---------------------------
30   Full-Rows (FR)         SC1        27          5.184   9  0  U
30   FC                     BR1        ---------------------------
24   2 FR, 1 WR             SR1C1      26          2.592   9  0  U
24   1 FR, 2 WR             SR1R2C1    29          1.296   9  0  U
30   Waving-Rows (WR)       SRC1       31            648   9  0  U
30   WC                     BCR2       ---------------------------

3. Boxes move triangular (B 159, 267, 368)
 5   Jumping-Diagonals (JD) BS         22        323.928   3  0  Y  also "Block symmetry"
30   Broken-Columns (BC)    BSR1       24            288   9  0  U
30   BR                     SBC1       ---------------------------
30   Full-Diagonals(FD)     BSR1C1     23            162   9  0  U

4. Rotational symmetries
30   Half-Turn (HT)         DD2        79    155.492.352   2  1  Y  also "180° rotational symmetry"
 8   Quarter-Turn (QT)      DBxRx      86         13.056   4  1  Y  also "90° rotational symmetry", has HT symmetry too

5. Diagonal symmetries
10   Diagonal-Mirror (DM)   D          37     30.258.432   2  9  Y  also "diagonal symmetry"
10   M/                     D2         -----------------------------------------------------
 0   DM+JD                  DBS        43            288   6  0  Y
 0   DM+MD                  DRC        40          1.854   6  0  Y

6. Sticks symmetries
10   Column-Sticks (CS)     BxCx      134    449.445.888   2  9  Y  also "sticks symmetry"
10   RS                     SxRx      ----------------------------------------------------
 0   CS+MC                  BxCxR     135         27.648   6  0  U
 0   CS+JR                  BxCxS     145         13.824   6  0  U
 0   CS+ GR/Band2,JR/B13    BxCxSR2   144          3.456   6  0  U
 0   CS+GR                  BxCxSR    142          6.480   6  0  U
 0   CS+ JR/B2,GR/B13       BxCxSR1R3 143          1.728   6  0  U

The program will loop over all 3359232 morphs of the grid and, for each morph, will check each operation listed in the third column of the table. If the operation turns out to be an automorphism, the score will be increased by the value in the first column. The highest total score (of the 3359232 candidates) is the winner.

The list seems incomplete to me. For example, I've got:

Code: Select all

24   1 FR, 2 WR             SR1R2C1    29          1.296   9  0  U

Do you also want me to add 24 points for each of:

Code: Select all

SR1R2C1
SR1R2C2
SR1R2C3

SR1R3C1
SR1R3C2
SR1R3C3

SR2R3C1
SR2R3C2
SR2R3C3

... and the BC1C2R1 transposed instances, too?

(I must have operations using this notation, not yours.)

[udosuk]

The list seems incomplete to me. For example, I've got:

Code: Select all

24   1 FR, 2 WR             SR1R2C1    29          1.296   9  0  U

Do you also want me to add 24 points for each of:

Code: Select all

SR1R2C1
SR1R2C2
SR1R2C3

SR1R3C1
SR1R3C2
SR1R3C3

SR2R3C1
SR2R3C2
SR2R3C3

... and the BC1C2R1 transposed instances, too?

I think "SC1" is the standard operation for order-9 symmetries, so not sure what "SC2" & "SC3" means. I also requested the singular symmetry to be displayed in the middle, so "SR1R3C1" is the standard operation in the normalised form. I don't know if multiple instances of this symmetry group can co-exist in a grid, if they do then just add 24 pts for each instance. But I don't think so.

Here is a brief description of what all the normalised form of each order-9 symmetry group should look like:

Code: Select all

FC (Full-Columns)
 a1 b1 c1 | d1 e1 f1 | g1 h1 j1
 a4 b4 c4 | d4 e4 f4 | g4 h4 j4
 a7 b7 c7 | d7 e7 f7 | g7 h7 j7
----------+----------+----------
 a2 b2 c2 | d2 e2 f2 | g2 h2 j2
 a5 b5 c5 | d5 e5 f5 | g5 h5 j5
 a8 b8 c8 | d8 e8 f8 | g8 h8 j8
----------+----------+----------
 a3 b3 c3 | d3 e3 f3 | g3 h3 j3
 a6 b6 c6 | d6 e6 f6 | g6 h6 j6
 a9 b9 c9 | d9 e9 f9 | g9 h9 j9

WC (Waving-Columns)
 a1 b1 c1 | d1 e1 f1 | g1 h1 j1
 a4 b4 c4 | d4 e4 f4 | g4 h4 j4
 a7 b7 c7 | d7 e7 f7 | g7 h7 j7
----------+----------+----------
 c2 a2 b2 | f2 d2 e2 | j2 g2 h2
 c5 a5 b5 | f5 d5 e5 | j5 g5 h5
 c8 a8 b8 | f8 d8 e8 | j8 g8 h8
----------+----------+----------
 b3 c3 a3 | e3 f3 d3 | h3 j3 g3
 b6 c6 a6 | e6 f6 d6 | h6 j6 g6
 b9 c9 a9 | e9 f9 d9 | h9 j9 g9

BC (Broken-Columns)
 a1 b1 c1 | d1 e1 f1 | g1 h1 j1
 a4 b4 c4 | d4 e4 f4 | g4 h4 j4
 a7 b7 c7 | d7 e7 f7 | g7 h7 j7
----------+----------+----------
 g2 h2 j2 | a2 b2 c2 | d2 e2 f2
 g5 h5 j5 | a5 b5 c5 | d5 e5 f5
 g8 h8 j8 | a8 b8 c8 | d8 e8 f8
----------+----------+----------
 d3 e3 f3 | g3 h3 j3 | a3 b3 c3
 d6 e6 f6 | g6 h6 j6 | a6 b6 c6
 d9 e9 f9 | g9 h9 j9 | a9 b9 c9

FD (Full-Diagonals)
 a1 b1 c1 | d1 e1 f1 | g1 h1 j1
 c4 a4 b4 | f4 d4 e4 | j4 g4 h4
 b7 c7 a7 | e7 f7 d7 | h7 j7 g7
----------+----------+----------
 j2 g2 h2 | a2 b2 c2 | d2 e2 f2
 h5 j5 g5 | c5 a5 b5 | f5 d5 e5
 g8 h8 j8 | b8 c8 a8 | e8 f8 d8
----------+----------+----------
 f3 d3 e3 | j3 g3 h3 | a3 b3 c3
 e6 f6 d6 | h6 j6 g6 | c6 a6 b6
 d9 e9 f9 | g9 h9 j9 | b9 c9 a9

1FC+2WC
 a1 b1 c1 | d1 e1 f1 | g1 h1 j1
 a4 b4 c4 | d4 e4 f4 | g4 h4 j4
 a7 b7 c7 | d7 e7 f7 | g7 h7 j7
----------+----------+----------
 c2 a2 b2 | d2 e2 f2 | j2 g2 h2
 c5 a5 b5 | d5 e5 f5 | j5 g5 h5
 c8 a8 b8 | d8 e8 f8 | j8 g8 h8
----------+----------+----------
 b3 c3 a3 | d3 e3 f3 | h3 j3 g3
 b6 c6 a6 | d6 e6 f6 | h6 j6 g6
 b9 c9 a9 | d9 e9 f9 | h9 j9 g9

1WC+2FC
 a1 b1 c1 | d1 e1 f1 | g1 h1 j1
 a4 b4 c4 | d4 e4 f4 | g4 h4 j4
 a7 b7 c7 | d7 e7 f7 | g7 h7 j7
----------+----------+----------
 a2 b2 c2 | f2 d2 e2 | g2 h2 j2
 a5 b5 c5 | f5 d5 e5 | g5 h5 j5
 a8 b8 c8 | f8 d8 e8 | g8 h8 j8
----------+----------+----------
 a3 b3 c3 | e3 f3 d3 | g3 h3 j3
 a6 b6 c6 | e6 f6 d6 | g6 h6 j6
 a9 b9 c9 | e9 f9 d9 | g9 h9 j9

(Going offline now, nighty-night.)