The New Sudoku Players' Forum

[udosuk]

Now to a new, exotic symmetry, DBS (it also has diagonal symmetry like 90° has 180°).

It needs a bit to see, where the cells go to. The box cycles are B159 and B287463. Each time a cell goes to the next box, it is mirrored at the mini-diagonal.
So we have 3-cycles for the cells in the main diagonal and 6-cycles else.

I can see 2 classical symmetries in your 2 puzzles:

1. diagonal symmetry @ d\

2. whole block symmetry @ b159|267|348 with digit cycles (123)(486)(597)

The extra property you observed, I think is probably just a direct consequence of these 2 classical symmetries.

Ditto for the "alternative DDS" you suggested earlier, as ronk pointed out it's probably equivalent to the classical DDS upon morphing.

But keep up the great work, hopefully you will discover something truly new & exotic in the near future!

[champagne]

This one needs a bit more.
Code:

Code: Select all

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

DBS (123)(456789)

Maybe someone can find a nice symmetry move to finally solve it.

Here is the proposal of the solver

1 r3c3=1 2 r6c6=2 3 r9c9=3 then the symmetry leading to that map

Code: Select all

3     56789 567  |2     69    89   |1     5789  4   
45689 2     2456 |4689  1     7    |58    3     289 
489   2789  1    |5     349   3489 |78    6     2789
----------------------------------------------------
2     5679  8    |1     45679 459  |3     47    67   
69    1     367  |46789 3     3489 |4678  2     5   
56    4     3567 |678   3567  2    |9     178   1678
----------------------------------------------------
1     58    45   |3     4579  6    |2     45789 789 
4568  3     9    |47    2     145  |45678 1     1678
7     256   2456 |49    8     1459 |456   1459  3   

4 r2c2=2 5 r5c5=3 6 r8c8=1 7 r3c6=3 8 r3c9=2 9 r6c3=3
10 r6c9=1 11 r9c3=2 12 r9c6=1

and here we need more. The partially tagged map

Code: Select all

3        56k78m9  567a |2        6g9G     8c9C |1        5h7b8q9E 4   
45m689k  2        4b56 |4a6G8C9t 1        7    |5H8h     3        8E9e
4a89     7b89     1    |5        4A9a     3    |7B8b     6        2   
----------------------------------------------------------------------
2        5C6t7a9G 8    |1        4u56w79  45d9 |3        4i7I     6f7F
6G9g     1        6a7A |467u89w  3        48C9 |4I6F7Ã8d 2        5   
5c6C     4        3    |678d     5C67     2    |9        7d8D     1   
----------------------------------------------------------------------
1        5h8H     4B5b |3        4Ã5d7I9F 6    |2        4Ä578Ç9  789E
4b5q6E8h 3        9    |4I7i     2        4d5D |45Ç67Ä8  1        6F78
7        5E6e     2    |4F9f     8        1    |456E     459F     3   

and 9 AIC's that look very similar.

1)[]6r1c2.k - 6r1c5.g = 6r2c4.G - 4r2c4.a = 6r12c3.A - 6r1c2.k
2)[]5r2c1.m - 5r2c7.H = 5r1c8.h - 7r1c8.b = 5r12c3.B - 5r2c1.m
3)[]5r8c1.q - 5r8c6.D = 5r4c6.d - 5r4c2.C = 5r6c1.c - 5r8c1.q
4)[]6r4c2.t - 6r4c9.f = 6r8c9.F - 6r8c1.E = 6r9c2.e - 6r4c2.t
5)[]4r4c5.u - 4r4c8.i = 4r8c4.I - 4r2c4.a = 4r3c5.A - 4r4c5.u
6)[]6r4c5.w - 6r1c5.g = 6r2c4.G - 8r2c4.C = 6r6c45.c - 6r4c5.w
7)[]4r7c5.Ã - 4r7c3.B = 4r2c3.b - 4r2c4.a = 4r3c5.A - 4r7c5.Ã
8)[]4r7c8.Ä - 4r4c8.i = 4r8c4.I - 4r8c1.b = 4r7c3.B - 4r7c8.Ä
9)[]5r8c7.Ç - 5r2c7.H = 5r7c2.h - 5r7c5.d = 5r8c6.D - 5r8c7.Ç


Let's go thru the first one: Only one difficulty 4r2c4.a = 6r12c3.A.

4r2c4.a is symmetric to 7r4c2.a so the detailed AIC could be

[]{9r1c2;6r1c2} - 6r1c5 = 6r2c4 - {4r2c4;7r4c2} = 7r5c3 - 6r5c3 = 6r12c3 - {6r1c2;9r1c2}

similar thing with 7rc8.b = 5r12c3.B 4r4c8.i = 4r8c4.I 5r2c7.H = 5r7c2.h
AIC's numbers 3,4,5,7 have nothing special

then singles to the end.

I did not check what is the minimum set of AIC's necessary to got to the end with singles.

nothing brillant, but no true difficulty

champagne

[eleven]

Thanks for the answers, i will think about them.

Also the third diagonal symmetry, which i now corrected to DRC, is a special case of D with additional constraints.
There are only a few interesting puzzles, which have it either. Here is an example:

Code: Select all

 +-------+-------+-------+
 | . . . | . . 2 | 1 5 8 |
 | . . . | 1 . . | 4 3 7 |
 | . . . | . 3 . | 9 6 2 |
 +-------+-------+-------+
 | . 1 . | 3 . . | . . 5 |
 | . . 3 | . 2 . | 7 . . |
 | 2 . . | . . 1 | . 9 . |
 +-------+-------+-------+
 | 1 7 6 | . 4 . | . . . |
 | 8 3 9 | . . 6 | . . . |
 | 5 4 2 | 8 . . | . . . |
 +-------+-------+-------+
 DRC (123)(945678)
 D (1)(2)(3)(47)(58)(69)

From the solving point of view it seems to me, that the 6-cycles dont help more than the normal symmetry properties.

[udosuk]

Also the third diagonal symmetry, which i now corrected to DRC, is a special case of D with additional constraints.
There are only a few interesting puzzles, which have it either. Here is an example:

Code: Select all

 +-------+-------+-------+
 | . . . | . . 2 | 1 5 8 |
 | . . . | 1 . . | 4 3 7 |
 | . . . | . 3 . | 9 6 2 |
 +-------+-------+-------+
 | . 1 . | 3 . . | . . 5 |
 | . . 3 | . 2 . | 7 . . |
 | 2 . . | . . 1 | . 9 . |
 +-------+-------+-------+
 | 1 7 6 | . 4 . | . . . |
 | 8 3 9 | . . 6 | . . . |
 | 5 4 2 | 8 . . | . . . |
 +-------+-------+-------+
 DRC (123)(945678)
 D (1)(2)(3)(47)(58)(69)

From the solving point of view it seems to me, that the 6-cycles dont help more than the normal symmetry properties.

This puzzle is actually also a combination of 2 classical symmetries:

1. Diagonal Symmetry @ d\ with pairings 1-1,2-2,3-3,4-7,5-8,6-9

2. Mini-Diagonal Symmetry - each leading mini-diagonals (including "broken ones") must be one of these cycles: (132)(468)(579)

As a matter of fact, I think all the 26 groups you summarised can be expressed as combinations of one or more of the following classical symmetries:

1. Rotation (180 or 90)
2. Diagonal Reflection (d\ or d/ or both)
3. Stick (r258c456 or r456c258)
4. Band or Stack
5. Block ([159|267|348] or [168|249|357])
6. Mini-diagonal (leading or non-leading)
7. Mini-row or Mini-column

However, more effort is required to be spent to work out all the exact combinations...

(So, with due respect, I'm afraid your "6-cycles" interpretations are merely making things more complicated than necessary, since the classical ones should be enough for classification purposes. But great work for finding all those nice puzzles! )

Back to the puzzle, using Diagonal Symmetry it's not hard at all to crack (only takes an x-wing). However, if we make use of the Mini-Diagonal Symmetry it even saves us the trouble of that x-wing. Here is how:

After simple Diagonal Symmetry tricks:

Code: Select all

+-------------------+-------------------+-------------------+
| 3     69   *47    | 4679  679   2     | 1     5     8     |
| 69    2     58    | 1     5689  589   | 4     3     7     |
| 47    58    1     | 457   3     4578  | 9     6     2     |
+-------------------+-------------------+-------------------+
|*4679  1    *478   | 3     6789  4789  | 28    24    5     |
| 469  *5689  3     | 4569  2     4589  | 7     14    16    |
| 2     568  -4578  | 4567  5678  1     | 38    9     36    |
+-------------------+-------------------+-------------------+
| 1     7     6     | 25    4     35    | 23    8     9     |
| 8     3     9     | 27    17    6     | 5     12    4     |
| 5     4     2     | 8     19    39    | 6     7     13    |
+-------------------+-------------------+-------------------+

The mini-diagonal @ r4c1+r5c2+r6c3 must be (468|579)
Now r14c3 can't be [77]
=> r146c3+r4c1+r5c2 can't be [77468]
=> r6c3 can't be 4

All singles from here.

[udosuk]

This one needs a bit more.

Code: Select all

 +-------+-------+-------+
 | 3 . . | 2 . . | 1 . 4 |
 | . . . | . 1 7 | . 3 . |
 | . . . | 5 . . | . 6 . |
 +-------+-------+-------+
 | 2 . 8 | 1 . . | 3 . . |
 | . 1 . | . . . | . 2 5 |
 | . 4 . | . . . | 9 . . |
 +-------+-------+-------+
 | 1 . . | 3 . 6 | 2 . . |
 | . 3 9 | . 2 . | . . . |
 | 7 . . | . 8 . | . . . |
 +-------+-------+-------+
 DBS (123)(456789)

Maybe someone can find a nice symmetry move to finally solve it.

I have 3 different solving paths for this one:

(Since this puzzle has Block Symmetry, I will use a new technique called Bludo, which you can read about here. )



Path 1

After simple Diagonal Symmetry moves and singles:

Code: Select all

+----------------------+----------------------+----------------------+
| 3      56789  567    | 2      69     89     | 1     #5789   4      |
| 45689  2      456    | 4689   1      7      | 58     3      89     |
| 489   *789    1      | 5      49     3      |#78     6      2      |
+----------------------+----------------------+----------------------+
| 2      5679   8      | 1      45679  459    | 3      47     67     |
| 69     1      67     | 46789  3      489    | 4678   2      5      |
| 56     4      3      | 678    567    2      | 9     -78     1      |
+----------------------+----------------------+----------------------+
| 1     #58     45     | 3      4579   6      | 2      45789  789    |
| 4568   3      9      | 47     2      45     | 45678  1      678    |
| 7     #56     2      | 49     8      1      | 456    459    3      |
+----------------------+----------------------+----------------------+

7 @ b3 locked @ r1c8+r3c7
=> r3c2+r6c8 can't be [77]
r8c2 must be from {58}
=> r39c2 can't be [85]
Block Symmetry: r3c2+r6c8 can't be [87]
Bludo: r3c2+r6c8 can't be [97]
In summary: r3c2+r6c8 can't be [77|87|97]
=> r6c7 can't be 7
Block Symmetry: r3c5<>9, r9c2<>5
Diagonal Symmetry: r5c3<>6, r8c6<>4, r2c9<>8

Code: Select all

+----------------+----------------+----------------+
| 3   -578  56   | 2    69   89   | 1   *57   4    |
| 458  2    456  | 68   1    7    | 58   3    9    |
| 89   789  1    | 5    4    3    | 78   6    2    |
+----------------+----------------+----------------+
| 2   *59   8    | 1    569  49   | 3    47   67   |
| 69   1    7    | 689  3    489  | 46   2    5    |
| 56   4    3    | 67   567  2    | 9    8    1    |
+----------------+----------------+----------------+
| 1    58   45   | 3   *79   6    | 2    479  78   |
| 48   3    9    | 47   2    5    | 467  1    678  |
| 7    6    2    | 49   8    1    | 45   459  3    |
+----------------+----------------+----------------+

Block Symmetry: r1c8+r4c2+r7c5=[597|759]
=> r1c8+r4c2=[59|75], must have 5
=> r1c2, seeing r1c8+r4c2, can't be 5
Block Symmetry: r4c5<>9, r7c8<>7
Diagonal Symmetry: r2c1<>8, r5c4<>6, r8c7<>4

Code: Select all

+----------------+----------------+----------------+
| 3   *78   56   | 2    69   89   | 1   -57   4    |
| 45   2    456  | 68   1    7    | 58   3    9    |
| 89   789  1    | 5    4    3    | 78   6    2    |
+----------------+----------------+----------------+
| 2    59   8    | 1    56   49   | 3   *47   67   |
| 69   1    7    | 89   3    489  | 46   2    5    |
| 56   4    3    | 67   567  2    | 9    8    1    |
+----------------+----------------+----------------+
| 1    58   45   | 3    79   6    | 2    49   78   |
| 48   3    9    | 47   2    5    | 67   1    678  |
| 7    6    2    | 49   8    1    | 45   459  3    |
+----------------+----------------+----------------+

Bludo: r1c2+r4c8 can't be [84]
=> r1c2+r4c8=[74|77|87], must have 7
=> r1c8, seeing r1c2+r4c8, can't be 7

All singles from here.



Path 2 (a step shorter than the one above)

After the first block of moves in Path 1:

Code: Select all

+----------------+----------------+----------------+
| 3    578 #56   | 2    69   89   | 1    57   4    |
| 458  2   *456  | 68   1    7    | 58   3    9    |
| 89   789  1    | 5    4    3    | 78   6    2    |
+----------------+----------------+----------------+
| 2    59   8    | 1    569  49   | 3    47  #67   |
| 69   1    7    | 689  3   -489  |*46   2    5    |
| 56   4    3    | 67   567  2    | 9    8    1    |
+----------------+----------------+----------------+
| 1    58   45   | 3    79   6    | 2    479  78   |
| 48   3    9    | 47   2    5    | 467  1    678  |
| 7    6    2    | 49   8    1    | 45   459  3    |
+----------------+----------------+----------------+

Bludo: r1c3+r4c9 can't be [57]
=> r1c3+r4c9=[56|66|67], must have 6
=> r2c3+r5c7 can't be [66]
Block Symmetry: r5c6 can't be 4

All singles from here.



Path 3 (no Bludo in this approach)

After simple Diagonal Symmetry moves and singles:

Code: Select all

+----------------------+----------------------+----------------------+
| 3      56789  567    | 2      69     89     | 1      5789   4      |
| 45689  2     *456    | 4689   1      7      | 58     3      89     |
|*489    789    1      | 5     *49     3      | 78     6      2      |
+----------------------+----------------------+----------------------+
| 2      5679   8      | 1      45679  459    | 3      47     67     |
| 69     1      67     | 46789  3      489    | 4678   2      5      |
| 56     4      3      | 678    567    2      | 9      78     1      |
+----------------------+----------------------+----------------------+
| 1      58    *45     | 3     -4579   6      | 2      45789  789    |
| 4568   3      9      | 47     2      45     | 45678  1      678    |
| 7      56     2      | 49     8      1      | 456    459    3      |
+----------------------+----------------------+----------------------+

Turbot fish (kite):
4 @ r3 locked @ r3c15
4 @ c3 locked @ r27c3
r2c3+r3c1 can't be [44]
=> r3c5+r7c3=[44|45|94], must have 4
=> r7c5, seeing r3c5+r7c3, can't be 4
Block Symmetry: r1c8<>8, r4c2<>6
Diagonal Symmetry: r5c7<>7, r8c1<>5, r2c4<>9

Code: Select all

+----------------------+----------------------+----------------------+
| 3      56789  567    | 2     #69    -89     | 1      579    4      |
| 45689  2      456    | 468    1      7      | 58     3      89     |
| 489    789    1      | 5     *49     3      | 78     6      2      |
+----------------------+----------------------+----------------------+
| 2      579    8      | 1     @45679  459    | 3     *47    #67     |
| 69     1      67     | 46789  3      489    | 468    2      5      |
| 56     4      3      | 678    567    2      | 9     -78     1      |
+----------------------+----------------------+----------------------+
| 1      58     45     | 3      579    6      | 2      45789  789    |
| 468    3      9      | 47     2      45     | 45678  1      678    |
| 7      56     2      | 49     8      1      | 456    459    3      |
+----------------------+----------------------+----------------------+

Block Symmetry: r3c5+r6c8=[48|97]
4 @ c5 locked @ r34c5
=> r3c5+r46c8 can't be [947]
=> r6c8 can't be 7
Block Symmetry: r9c2<>5, r3c5<>9

Block Symmetry: r1c6+r4c9=[86|97]
6 @ r4 locked @ r4c59
=> r1c56+r4c9 can't be [697]
=> r1c6 can't be 9
Block Symmetry: r4c9<>7, r7c3<>5

All singles from here.



Personally I like the 3rd path the best, but the usage of Bludo in the first 2 paths probably makes them easier.

[Red Ed]

I just noticed this thread. I can't really comment on the solving techniques part, but I would like to offer a correction to the very first sentence: it was Frazer Jarvis that first did the breakdown of the symmetries into 275 conjugacy classes; my role was just to count the number of grids fixed by a representative member of each class. Still, nice to see that the work hasn't been forgotten!

[udosuk]

I have had a good read about the first post in this thread. Will spend more time to analyse each of the 26 groups...

Meanwhile, seeing master Red Ed is here, I would like to ask both you guys (and perhaps Frazer if possible) why were these particular groups chosen? Some of them are obviously combinations of simpler symmetries (e.g. DBS is Diagonal plus Block, DRC is Diagonal plus Mini-Diagonal) but some combinations are not included (e.g. Double Diagonal Symmetry as a combination of 180 symmetry plus Diagonal Symmetry on any one diagonal). For example, the following puzzle:

Code: Select all

1..3....8
....4..2.
..9..6...
6..1.27..
.7.....3.
..38.9..4
...4..1..
.8..6....
2....7..9

Should it be classified under group 4a (DD2) or group 5a (D)?

[eleven]

Sorry for the late response to your contributions, I was bound to bed by the Brisbane influenza.

Bludo is great, i did not expect a symmetry move for block symmetry.

I will update the first post soon with Bludo, add Frazer Jarvis as author and add equivalent combinations of symmetries as far i can see it.

Regarding the question about these groups:
The symmetry classes are (all possible) single symmetries with one equivalence transformation for the cells (and - in real grids - one renumbering).
It is a nice observation, that some (or many) of them are equivalent to a combination of 2 symmetries, but in this meaning they exist for their own.

[Red Ed]

Basically what we did was apply the orbit-counting theorem to the problem of determining the number of essentially-different completed sudoku grids (henceforth just "grids"). In this case, the theorem can be used as follows:

• Let G be the group of 3359232 cell-scrambling operations that are guaranteed to leave a valid grid still valid. (That's just the cell-scrambling ops; not the digit-relabelling ones.)
• Pick any cell-scrambling operation, g, in G. We say that a grid is "essentially fixed" by g, if g leaves the grid unchanged or relabelled.
• Let f(g) be the number of grids essentially fixed by g. Then (theorem) the number of essentially-different grids is equal to the average, over all g in G, of f(g).

So using this theorem, the naive way of computing the 5472730538 number is to do this:

Code: Select all

sum = 0
for g in G:   # 3359232 values
    let f = number of grids essentially fixed by g
    sum = sum + f
print sum / 3359232

Now here's the clever bit (take a bow, Frazer). If X is a grid essentially fixed by g then hX is a grid essentially fixed by hgh' (where h' means inverse of h). So f(g) = f(hgh'). The set of all values hgh', for a given g, is called the conjugacy class of g. What I'm saying is that you only need to work out f(g) for a single g in each of the 275 conjugacy classes, not for all 3359232 g in the whole group.

With that observation, we can compute the 5472730538 number much more quickly:

Code: Select all

let C be the conjugacy classes of G
for c in C:   # 275 values
    let s be the size of c      # i.e. number of elements, g, in C
    let g be any element of c   # doesn't matter which one
    let f = number of grids essentially fixed by g
    sum = sum + f*s
print sum / 3359232

So that's where the 275 scrambling operations come from: a random choice from each of the 275 conjugacy classes. Different random choices would give essentially the same scrambling ops, just "rewritten" a bit (not in an interesting way).

I'll answer your question about absence of certain symmetries later. But first I'm being told (quite firmly!) that I have to help get the kids ready for bed. Back in a couple of hours ...

[udosuk]

Regarding the question about these groups:
The symmetry classes are (all possible) single symmetries with one equivalence transformation for the cells (and - in real grids - one renumbering).
It is a nice observation, that some (or many) of them are equivalent to a combination of 2 symmetries, but in this meaning they exist for their own.

Thanks eleven! You answered my question. Combinations of symmetries can only be included in your list if all involved symmetries have non-conflicting digit mappings. My example of 180 symmetry + diagonal symmetry can't work because they each must have different digit mappings which conflict each other.

Also thanks Red Ed for reposting the outline of that ingenious proof. Even though I need time to digest it I can already appreciate the neatness of it. Mind you it's a long time since I touched linear algebra, group theory etc during my college days.

[Red Ed]

Right, just one thing to add then. If a grid has any symmetries then, usually, there's a single "basic" symmetry (from the list of 26 in the first post of this thread) that generates all of them. But there are also a few special grids (e.g. the "most canonical"/MC grid) whose full set of symmetries cannot be generated by a single "basic" symmetry. It would be interesting to classify and count all multiply-symmetric grids. AFAIK, no-one's got around to doing that yet.

[StrmCkr]

removed.

[Red Ed]

No, StrmCkr, there are 648 automorphisms of the MC grid.

[StrmCkr]

deleted rebuilding to incorporate other variations of my pattern..
that i never considerd befor....

[Red Ed]

Well of course it's impossible to tell when you use undefined phrases like "repeating pattern association", but still: you're either trying to do automorphisms/symmetries, in which case your number is wrong; or you're not, in which case I don't know why you're posting to this thread.