About Red Ed's Sudoku symmetry group

Everything about Sudoku that doesn't fit in one of the other sections

Postby eleven » Sat Jan 10, 2009 7:43 am

I had a look at some puzzles with MD symmetry. It did not take long to find 2, which can be solved easiily using the symmetry:
Code: Select all
 +-------+-------+-------+
 | 1 8 . | . 4 . | 9 3 5 |
 | . 2 9 | . . 5 | 6 7 1 |
 | 7 . 3 | 6 . . | 2 4 8 |
 +-------+-------+-------+
 | . . 5 | 9 3 . | . . . |
 | 6 . . | . 7 1 | . . . |
 | . 4 . | 2 . 8 | . . . |
 +-------+-------+-------+
 | . . 4 | . 6 3 | . . . |
 | 5 . . | 1 . 4 | . . . |
 | . 6 . | 5 2 . | . . . |
 +-------+-------+-------+
 *-----------------------------------------------*
 | 1    8    6    | 7  4  2  | 9     3     5     |
 | 4    2    9    | 3  8  5  | 6     7     1     |
 | 7    5    3    | 6  1  9  | 2     4     8     |
 |----------------+----------+-------------------|
 | 28  #17   5    | 9  3  6  | 1478  128   247   |
 | 6    39   28   | 4  7  1  | 358   2589  239   |
 | 39   4    17   | 2  5  8  | 137   169   3679  |
 |----------------+----------+-------------------|
 | 29  #179  4    | 8  6  3  | 157   1259  279   |
 | 5   #37   278  | 1  9  4  | 378   268   2367  |
 | 389  6    18   | 5  2  7  | 1348  189   349   |
 *-----------------------------------------------*

r7c2 cannot be 1, because it would imply 7 both in r4c2 and (by symmetry) in r8c2.
Code: Select all
 +-------+-------+-------+
 | 6 8 1 | . . . | . . 3 |
 | 2 4 9 | . . . | 1 . . |
 | 7 3 5 | . . . | . 2 . |
 +-------+-------+-------+
 | 3 . . | . . 9 | 4 . 8 |
 | . 1 . | 7 . . | 9 5 . |
 | . . 2 | . 8 . | . 7 6 |
 +-------+-------+-------+
 | . 2 . | . . 5 | . 3 . |
 | . . 3 | 6 . . | . . 1 |
 | 1 . . | . 4 . | 2 . . |
 +-------+-------+-------+
 *--------------------------------------------------------*
 | 6     8     1     | 2459  2579  247   | 57  @49   3    |
 | 2     4     9     | 358   3567  3678  | 1   @68   57   |
 | 7     3     5     | 1489  169   1468  | 68   2    49   |
 |-------------------+-------------------+----------------|
 | 3     567   67    | 25    256   9     | 4    1    8    |
 |#48    1     468   | 7     36    346   | 9    5    2    |
 | 459   59    2     | 145   8     14    | 3    7    6    |
 |-------------------+-------------------+----------------|
 |#489   2     4678  | 189   179   5     | 678  3    479  |
 |#45-89 579   3     | 6     279   278   | 578 @489  1    |
 | 1     5679  678   | 389   4     378   | 2    6-89 579  |
 *--------------------------------------------------------*

r8c1=8 -> (r5c1=4 & r7c1=4) => r8c1<>8
Either r1c8=9 or (r1c8=4 -> r2c8=8 -> r8c8=9) => r9c8<>9

Here is a list of other MD puzzles with increasing ER between 7.1 and 9.2, i had not tried so far:
......593......167......8243.59.....61..7.....42..8...4...5..39.5...67.1..64..28.
..1.53...2..1.6....3.42......9..7.8.7..8....9.8..9.7..6...492...4.7.5.3...568...1
.17.5...68.2..64..39.4...5....9...8.....7...9.....87......6.835.....4691...5..247
..21....33...2.1...1...3.2.7..5....8.8..6.9....9..4.7..9.68.5....7.49.6.8..7.5..4
5..3.9.1..6.71...2..4.823...96......4.7......85.........3.2...41....35...2.1...6.
4...5.1...5...6.2...64....32...8.....3...9.....17.....8..1...49.9..2.7.5..7..368.
..169.7..2...47.8..3.8.5..91...8.5...2...9.6...37....4.6...4..5..45..6..5...6..4.
6.7....5.84......6.95...4...8...65....94...6.7...5...45..1.8..3.6.92.1....4.73.2.
..1....4.2.......5.3....6..9..2.57...7.63..8...8.41..9..3.9..1.1....7..2.2.8..3..
...1....4....2.5.......3.6...4.3.7..5....1.8..6.2....99.3...4.817....95..28....76
1..4....7.2..5.8....3..6.9...6..7..84..8..9...5..9..7...21....43...2.5...1...3.6.
2...7.....3...8.....19.......8...9.59.....67..7.....486..7.4.81.4.58.2.9..5.6973.
..14....82...5.9...3...6.7..1.....34..2...5.13.....26.95.1......76.2....4.8..3...
...25.6......36.4....4.1..5.5..8...9..6..97..4..7...8.34..9.....15..7...6.28.....
8..71...5.9..826....73.9.4.3.48.5...51.69.....62.47...7.....4...8.....5...9.....6
8...4.....9...5.....76..........7491...8..257....9.836.3.9.4.1...157...22...683..
eleven
 
Posts: 1741
Joined: 10 February 2008

Postby StrmCkr » Sat Jan 10, 2009 3:16 pm

thanks elven:)

im almost done with my findings. {i have 4/5 more grids to complete}.

udosuk:
finding the correct issomporh for each of the 26 varations from each of red eds puzzles:
ive had to morph the puzzles alot to get what i wanted visually.
deffinitly a fun challeng.

post more soon.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 755
Joined: 05 September 2006

Postby eleven » Sun Jan 11, 2009 6:23 am

A summary of symmetrical solution techniques

Different to sudoku variations (like Sudoku X) symmetrical puzzles are also classical ones, i.e. they dont need any additional rule for solving (if they are unique, you can solve them with pure classical methods).
However by the fact, that if a puzzle is symmetrical and (guaranteed to be) unique, then the whole solution must be symmetrical, most symmetries allow special techniques, which make them much easier in the most cases.
Symmetrical puzzles are very rare compared to non-symmetrical ones, also under those, whose givens have a suitable symmetrical pattern like 180° rotational symmetry, because normally the symmetrical givens dont follow the same number mapping (here each number always has to be "opposite" to the same number).

Symmetrical techniques have been found for 7 types of symmetries. In historical order these are:
- Half-Turn (180° rotational symmetry)
- Diagonal-Mirror
- Quarter-Turn (90° rotational symmetry)
- Column-Sticks
- Gliding-Rows (in at least one band)
- Jumping-Diagonals (Box symmetry)
- Mini-Diagonals (in at least one band)

Note, that symmetrical puzzles are not necessarily in the "normalised" form as shown in the representatives. They can be transformed to any isomorphic puzzle (by the known equivalence transformations, e.g. see at the top of the Symmetry group article), so that the symmetry can be well hidden (e.g. see Mauricio's puzzles here). Obviously is, that e.g. diagonal symmetry is equivalent to subdiagonal symmetry, Mini-Row to Mini-Column, Column-Sticks to Row-Sticks, Jumping-Diagonals to Jumping-Subdiagonals etc. Just turn the puzzle around by 90° to get from one to the other.

Additionally combined symmetries like Double-Diagonal (DDS), HT/JD or HT/MD and others have been investigated.
Other symmetries like the 9-cycled ones or the Sticks variations dont allow puzzles, which cannot be solved with simple classical methods.

For the Mini-Rows and Jumping-Rows symmetries no special techniques could be found. But of course the puzzles are easier in the sense, that each solving move you can find, can be replicated 2 times with the symmetrical cells/numbers.

1. Sticks symmetry
Puzzles with this symmetry are the easiest to solve.
Sample:
Code: Select all
Mauricio, ER 9.2

9 . .|. . 3|. . 6    b a c|. . .|. . .
. 6 .|. . 1|. 5 .    b a c|. . .|. . .
. . 4|6 . .|2 . .    b a c|. . .|. . .
-----+-----+-----    -----+-----+-----
. 7 .|. 1 .|9 . 8    d X d|. X .|. X .
. . .|. . .|. . .    d X d|. X .|. X .
3 . 2|. . .|. 7 .    d X d|. X .|. X .
-----+-----+-----    -----+-----+-----
. . 8|2 . .|5 . .    c a b|. . .|. . .
. 5 .|1 . .|. 6 .    c a b|. . .|. . .
4 . .|. . 5|. . 3    c a b|. . .|. . .

BxCx (exchange bands 13 and Columns 13,46,79)
Number cycles (1)(4)(7)(23)(56)(89)


The cells X map to themselves and the minicolumns with a,b,c,and d to one another (same in each stack).
All numbers in the 9 fixed cells X can immediately filled in with the 3 numbers 147.

So almost all puzzles (known with ER up to 9.9) are reduced to singles after this step.
Only one is known so far, which needed another advanced step (more than xy-wing) after this simple symmetry move, see here.

2. Diagonal-Mirror symmetry
Here we also have 9 fixed cells, which only can have 3 fixed numbers (and not one out of the 3 pairs of numbers). But this does not solve all diagonal cells from the beginning, only all other candidates can be eliminated from them.

See Example 1 in Automorphic sudokus.
I did not find any links to other DM techniques, though there should be some.

3. Half-Turn symmetry
HT and QT have one fixed cell, the center cell (in the representative form). So it must hold the (only) fixed number. This is called Gurth's symmetrical placement and was the first discovered symmetrical technique.
Some more simple techniques have been found soon, the Emerald techniques, see e.g. there (i did not find the original definitions for udosuk's EUR, EUP, NEP etc.)
A nice sample is udosuk's Down Under puzzle with his solution presented here.

4. Quarter-Turn
Since each puzzle with this symmetry also has Half-Turn symmetry, all HT techniques can be applied also.
Additionally the windmill technique can be applied, see a sample here.

More recently it was found, that also the following symmetries allow special techniques.

5. Gliding-Rows
In a band with the gliding-row property the mini-rows of the boxes follow this pattern:
| A1 | C2 | B3 |
| B1 | A2 | C3 |
| C1 | B2 | A3 |
That means that the minirow A1 maps to A2, A2 to A3 and A3 to A1, in the sense that the number in the first cell of A1 maps (according to the number cycles) to the number in the first cell of A2 and so on. Same for B and D.
If you have a symmetry with at least one band of Gliding-Rows and a number mapping with at least two 3-cycles (i.e. maximum 3 numbers map to themselves), you can apply the Gludo technique, which turned out to be rather strong. Many hard rated puzzles can be solved with Gludo alone.

Another simple technique is "Eleven's elimination for minirow shifting cyclic triple". It needs at least one 3-cycle.

6. Jumping-Diagonals (Box symmetry)
The only known special technique for this symmetry is Bludo. It says, that the corrsponding cells in two "antidiagonal" boxes (the "diagonals" are Boxes 159, 267 and 348, antidiagonal are 68, 49, 57, 37, 18, 29, 24, 35, 67) cannot have two numbers of the same number cycle. This does not allow direct eliminations, but needs a combination with other (classical) deductions. Thus it is a relatively weak symmetry technique.
See a sample here.

7. Mini-Diagonals
In a band with the mini-diagonal property each of the 3 boxes follow this pattern:
| A1 C2 B3 |
| B1 A2 C3 |
| C1 B2 A3 |
The number in cell A1 maps (according to the number cycles) to the one in A2, A2 to A3 and A3 to A1. Same for B and D.

This symmetry implies, that the cells in a mini-row or mini-column always must have numbers from the 3 different number cycles. This sometimes can easily be used to solve also hard rated puzzles immediately.
See the sample 2 posts back.


Additionally to directly applying these "basic" solving methods, of course they can be combined with classical techniques, i.e. as part of chains or - more favorable - in combination with a strong link, an ALS or whatever. You can find many samples in Gurth's puzzles and udosuk's thread Down Under Upside Down.


----
If someone has good samples/links, please post them (searching in the forum is very cumbersome).
eleven
 
Posts: 1741
Joined: 10 February 2008

Postby udosuk » Sun Jan 11, 2009 11:21 am

Thanks eleven, great analysis. Also nice to see you have updated the top post of this thread on p.1. Good on you!:D

When I have time (eventually) I'll write a detailed article on all 13 "basic" symmetrical groups.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby udosuk » Mon Jan 12, 2009 8:12 am

eleven wrote:Here is a list of other MD puzzles with increasing ER between 7.1 and 9.2, i had not tried so far:
......593......167......8243.59.....61..7.....42..8...4...5..39.5...67.1..64..28.
..1.53...2..1.6....3.42......9..7.8.7..8....9.8..9.7..6...492...4.7.5.3...568...1
.17.5...68.2..64..39.4...5....9...8.....7...9.....87......6.835.....4691...5..247
..21....33...2.1...1...3.2.7..5....8.8..6.9....9..4.7..9.68.5....7.49.6.8..7.5..4
5..3.9.1..6.71...2..4.823...96......4.7......85.........3.2...41....35...2.1...6.
4...5.1...5...6.2...64....32...8.....3...9.....17.....8..1...49.9..2.7.5..7..368.
..169.7..2...47.8..3.8.5..91...8.5...2...9.6...37....4.6...4..5..45..6..5...6..4.
6.7....5.84......6.95...4...8...65....94...6.7...5...45..1.8..3.6.92.1....4.73.2.
..1....4.2.......5.3....6..9..2.57...7.63..8...8.41..9..3.9..1.1....7..2.2.8..3..
...1....4....2.5.......3.6...4.3.7..5....1.8..6.2....99.3...4.817....95..28....76
1..4....7.2..5.8....3..6.9...6..7..84..8..9...5..9..7...21....43...2.5...1...3.6.
2...7.....3...8.....19.......8...9.59.....67..7.....486..7.4.81.4.58.2.9..5.6973.
..14....82...5.9...3...6.7..1.....34..2...5.13.....26.95.1......76.2....4.8..3...
...25.6......36.4....4.1..5.5..8...9..6..97..4..7...8.34..9.....15..7...6.28.....
8..71...5.9..826....73.9.4.3.48.5...51.69.....62.47...7.....4...8.....5...9.....6
8...4.....9...5.....76..........7491...8..257....9.836.3.9.4.1...157...22...683..

Here is how I solved 6 of these 16 nice puzzles:



#01
Code: Select all
+----------------+----------------+----------------+
|*128 *26   1-47 | 167 #248  127  | 5    9    3    |
| 258  239  34   | 238  248  359  | 1    6    7    |
| 15   369  137  | 167  139  359  | 8    2    4    |
+----------------+----------------+----------------+
| 3    78   5    | 9    6    12   | 4    17   28   |
| 6    1    89   | 23   7    4    | 39   5    28   |
| 79   4    2    | 5    13   8    | 39   17   6    |
+----------------+----------------+----------------+
| 4    28   18   | 17   5    127  | 6    3    9    |
| 29   5    39   | 238  28   6    | 7    4    1    |
| 17   37   6    | 4    139  39   | 2    8    5    |
+----------------+----------------+----------------+

r1c5 from {248}
=> r1c123 can't be [824]
MD Symmetry: r1c3<>4



#02
Code: Select all
+----------------------+----------------------+----------------------+
|#48     67     1      | 9      5      3      |*468    2-467  2-4678 |
| 2      59     48     | 1      7      6      | 34589  459    3458   |
| 59     3      67     | 4      2      8      | 1569   15679  567    |
+----------------------+----------------------+----------------------+
| 14-5  &256    9      |@25     36     7      | 13456  8      23456  |
| 7      256    346    | 8      36     14     | 13456  12456  9      |
|$145    8      346    |$25     9     $14     | 7     %12456  23-4-56|
+----------------------+----------------------+----------------------+
| 6      1      78     | 3      4      9      | 2      57     578    |
| 89     4      2      | 7      1      5      | 689    3      68     |
| 3      79     5      | 6      8      2      | 49     479    1      |
+----------------------+----------------------+----------------------+

r1c1 from {48}
=> r1c78 & r1c79 can't be [84]
MD Symmetry: r1c89<>4

r4c4 from {25}
=> r4c12 can't be [52]
MD Symmetry: r4c1<>5

r6c146 from {1245} must have {14|15|24|25}
=> r6c56 can't be [14|15|24|25]
MD Symmetry: r6c6<>4,5

Code: Select all
+----------------------+----------------------+----------------------+
|*48     67     1      | 9      5      3      | 468    267    2678   |
| 2      59    *48     | 1      7      6      | 34589  459   *3458   |
| 59     3      67     | 4      2      8      | 1569   15679  567    |
+----------------------+----------------------+----------------------+
| 1-4    256    9      | 25     36     7      | 13456  8     *23456  |
| 7      256    346    | 8      36     14     | 13456  12456  9      |
| 145    8      346    | 25     9      14     | 7      12456  236    |
+----------------------+----------------------+----------------------+
| 6      1      78     | 3      4      9      | 2      57     578    |
| 89     4      2      | 7      1      5      | 689    3      68     |
| 3      79     5      | 6      8      2      | 49     479    1      |
+----------------------+----------------------+----------------------+

Turbot Fish:
4 @ b1 locked @ r1c1+r2c3, 4 @ c9 locked @ r24c9
r2c39 can't be [44]
=> r1c1+r4c9 must have at least one 4
=> r4c1<>4
MD Symmetry: r4c1=1, r5c2=2, r6c3=3
Hidden Pair @ c9: r24c9={34}



#03
Code: Select all
+-------------------+-------------------+-------------------+
| 4     1     7     | 8     5     3     | 9     2     6     |
| 8     5     2     | 1     9     6     | 4     7     3     |
| 3     9     6     | 4     2     7     | 1     5     8     |
+-------------------+-------------------+-------------------+
| 67    67    13    | 9    *134   1-25  | 35    8    #24    |
| 12    48    48    | 236   7     125   | 35    16    9     |
| 59    23    59    | 236   134   8     | 7     16    24    |
+-------------------+-------------------+-------------------+
| 1279  247   149   | 27    6     129   | 8     3     5     |
| 257   2378  358   | 237   38    4     | 6     9     1     |
| 169   368   1389  | 5     138   19    | 2     4     7     |
+-------------------+-------------------+-------------------+

r4c9 from {24}
=> r4c56 can't be [42]
MD Symmetry: r4c6<>2
Hidden Single @ r4: r4c9=2
MD Symmetry: r5c7=3, r6c8=1



#04
Code: Select all
+-------------------+-------------------+-------------------+
| 9     456   2     | 1    #57   @68    |*4-67 &4-58  3     |
| 3     7     456   | 49    2     68    | 1     458   569   |
| 456   1     8     | 49    57    3     | 467   2     569   |
+-------------------+-------------------+-------------------+
| 7     2346  1346  | 5     9     12    | 2346  134   8     |
| 1245  8     1345  | 23    6     7     | 9     1345  125   |
| 1256  2356  9     | 8     13    4     | 236   7     1256  |
+-------------------+-------------------+-------------------+
| 124   9     134   | 6     8     12    | 5     13    7     |
| 125   235   7     | 23    4     9     | 8     6     12    |
| 8     236   136   | 7     13    5     | 23    9     4     |
+-------------------+-------------------+-------------------+

r1c5 from {57}
=> r1c78 can't be [75]
MD Symmetry: r1c8<>5

r1c6 from {68}
=> r1c78 can't be [68]
MD Symmetry: r1c7<>6
MD Symmetry: r2c8<>4, r3c9<>5

5 @ r2,b3 locked @ r2c89
Hidden Single @ c3: r5c3=5
MD Symmetry: r6c1=6, r4c2=4



#05
Code: Select all
+----------------------+----------------------+----------------------+
| 5      78     2      | 3      46     9      | 4678   1      678    |
| 3      6      89     | 7      1      45     | 489    4589   2      |
| 79     1      4      | 56     8      2      | 3      579    5679   |
+----------------------+----------------------+----------------------+
| 2      9      6      |#48     357    178    |*478    3457-8 157-8  |
| 4      3      7      |@289   @59     168    |&2689  @589    1-56-89|
| 8      5      1      | 249    379    67     | 24679  3479   679    |
+----------------------+----------------------+----------------------+
| 6      78     3      | 589    2      578    | 1      789    4      |
| 1      4      89     | 689    679    3      | 5      2      789    |
| 79     2      5      | 1      479    478    | 789    6      3      |
+----------------------+----------------------+----------------------+

r4c4 from {48}
=> r4c78 & r4c79 can't be [48]
MD Symmetry: r4c89<>8

r5c458 from {2589} must have {25|28}
=> r5c79 can't be [25|28]
MD Symmetry: r5c9<>5,8

Code: Select all
+----------------------+----------------------+----------------------+
| 5     *78     2      | 3      46     9      | 4678   1     *678    |
| 3      6     *89     | 7      1      45     | 489    4589   2      |
| 79     1      4      | 56     8      2      | 3      579    5679   |
+----------------------+----------------------+----------------------+
| 2      9      6      | 48     357    178    | 478    3457   157    |
| 4      3      7      | 289    59     168    | 2689   589    169    |
| 8      5      1      | 249    379    67     | 24679  3479   679    |
+----------------------+----------------------+----------------------+
| 6      78     3      | 589    2      578    | 1      789    4      |
| 1      4     -89     | 689    679    3      | 5      2     *789    |
| 79     2      5      | 1      479    478    | 789    6      3      |
+----------------------+----------------------+----------------------+

Turbot Fish:
8 @ b1 locked @ r1c2+r2c3, 8 @ c9 locked @ r18c9
r1c29 can't be [88]
=> r2c3+r8c9 must have at least one 8
=> r8c3<>8
=> r28c3=[89], r17c2=[78]
Hidden Single @ c8: r5c8=8
MD Symmetry: r6c9=9, r4c7=7



#07
Code: Select all
+----------------------+----------------------+----------------------+
| 48    #48     1      | 6      9      23     | 7      5      23     |
| 2      59     59     | 13     4      7      | 13     8      6      |
| 67     3      67     | 8      12     5      | 4      12     9      |
+----------------------+----------------------+----------------------+
| 1     *479    679    | 234    8      236    | 5      2379   237    |
| 478    2      578    | 134    135    9      | 138    6      1378   |
| 689    5-89   3      | 7      125    126    | 1289   129    4      |
+----------------------+----------------------+----------------------+
| 3789   6      2789   | 1239   1237   4      | 12389  12379  5      |
| 3789   1789   4      | 5      1237   1238   | 6      12379  12378  |
| 5      1789   2789   | 1239   6      1238   | 12389  4      12378  |
+----------------------+----------------------+----------------------+

r1c2 from {48}
=> r46c2 can't be [48]
MD Symmetry: r6c2<>8
MD Symmetry: r4c3<>9, r5c1<>7

Naked Pair @ c1: r15c1={48}
Hidden Single @ r6: r6c7=8
Hidden Single @ r7: r7c3=8
Hidden Single @ c3: r9c3=2
Hidden Single @ c7: r7c7=2
MD Symmetry: r8c8=3, r9c9=1



The remaining 10 will have to wait...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby eleven » Fri Jan 16, 2009 1:10 am

Nice solutions.

Another DS+MD puzzle
Code: Select all
 
 +-------+-------+-------+
 | 1 . . | . 5 . | . . 2 |
 | . 2 . | . . 9 | 3 . . |
 | . . 3 | 7 . . | . 1 . |
 +-------+-------+-------+
 | . . 4 | . . . | . 6 7 |
 | 8 . . | . . . | 5 . 4 |
 | . 6 . | . . . | 8 9 . |
 +-------+-------+-------+
 | . 3 . | . 8 5 | 1 . . |
 | . . 1 | 9 . 6 | . 2 . |
 | 2 . . | 4 7 . | . . 3 |
 +-------+-------+-------+

And some diagonal puzzles.
Code: Select all
 
 +-------+-------+-------+
 | . . . | . . . | . . 9 |
 | . . . | . 5 . | 7 6 . |
 | . . . | . . 3 | 4 1 5 |
 +-------+-------+-------+
 | . . . | . . . | . . 6 |
 | . 4 . | . . 7 | . . 3 |
 | . . 3 | . 6 1 | 5 . . |
 +-------+-------+-------+
 | . 6 5 | . . 4 | . 8 . |
 | . 7 1 | . . . | 9 . . |
 | 8 . 4 | 7 3 . | . . . |
 +-------+-------+-------+
 +-------+-------+-------+
 | . 7 . | 8 . . | . . 9 |
 | 6 . . | . 5 . | . 8 3 |
 | . . . | 2 . . | 1 . . |
 +-------+-------+-------+
 | 9 . 2 | . . . | . 5 7 |
 | . 4 . | . 2 . | 9 . . |
 | . . . | . . . | 6 . . |
 +-------+-------+-------+
 | . . 1 | . 8 7 | . . . |
 | . 9 . | 4 . . | . . . |
 | 8 3 . | 6 . . | . . . |
 +-------+-------+-------+
 +-------+-------+-------+
 | . 9 5 | . . . | 3 . . |
 | 8 . . | . . . | 6 . . |
 | 4 . . | . 1 8 | . 9 . |
 +-------+-------+-------+
 | . . . | 3 . . | 8 . . |
 | . . 1 | . 2 . | . . 7 |
 | . . 9 | . . . | . . . |
 +-------+-------+-------+
 | 3 7 . | 9 . . | . . 5 |
 | . . 8 | . . . | . . . |
 | . . . | . 6 . | 4 . . |
 +-------+-------+-------+
 +-------+-------+-------+
 | . . . | 9 . 6 | 4 7 . |
 | . . . | . . . | . . 1 |
 | . . . | 7 2 . | 8 . . |
 +-------+-------+-------+
 | 8 . 6 | . . . | 3 . . |
 | . . 2 | . 3 . | . 5 7 |
 | 7 . . | . . . | 2 8 . |
 +-------+-------+-------+
 | 5 . 9 | 3 . 2 | . . . |
 | 6 . . | . 4 9 | . . . |
 | . 1 . | . 6 . | . . . |
 +-------+-------+-------+
eleven
 
Posts: 1741
Joined: 10 February 2008

Postby Red Ed » Sun Jan 18, 2009 6:33 am

back <here>, I wrote: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.

I finally got around to calculating all sudoku symmetry groups, up to isomorphism.

A symmetry group is the collection of all automorphisms of a given grid, ignoring relabelling. We regard the automorphism groups of two isomorphic grids as being essentially the same. There are 123 essentially-different symmetry groups, ranging in size from 1 (no non-trivial automorphisms) to 648 (the MC grid).

Sample grids for each of the 122 non-trivial symmetry groups are shown below. The first number on each line is the size of the group.

Code: Select all
  2 274365981653189724198427536742813695936754218581296473865971342319642857427538169
  2 514738296873692154629154738741369582265481379938275461392516847156847923487923615
  2 759384261163259487482167359597436128834712596621598743975821634248673915316945872
  3 159423678742861935386597214861935742493278156527614389615782493934156827278349561
  3 351279648927684315684513729135927486792846531846351297279468153468135972513792864
  3 394178256278956431561243897732481965815769342946532718627314589489625173153897624
  3 457916328183275946962348175639854217275193864841627593714539682596482731328761459
  3 485632917392175468671498325917253846253846791846917532739521684528364179164789253
  3 541396278768512439329784651213479865687251943495638127974865312152943786836127594
  3 597841263236795418814326579469538127782619354351472986975184632623957841148263795
  3 683149275275836941149572386914725638752368194368491527527683419836914752491257863
  3 915874236748263195326519847693125478874936512152487963487392651561748329239651784
  4 173569842569482173824713695382956714417328569956174238695231487231847956748695321
  4 419268357538947162267153894794681523356492781182735649925316478673824915841579236
  4 726185439413269758985473126154697382862531947397842615538916274641728593279354861
  6 128574936496312587735689142241897365963245871857163429574928613689731254312456798
  6 164839257725164983398572146839257461641983572572641839257416398983725614416398725
  6 198467253563298417427153968635829174274315689981746532746981325352674891819532746
  6 239586741741293568568174932317845296854629317692731854976452183425318679183967425
  6 248637591736195248591842736623978154179456823854321679987264315312589467465713982
  6 324758691957126438168934257415673829736289514289415376892541763673892145541367982
  6 364172589721859634859643271938527416146938725275461398513284967697315842482796153
  6 372419586194865723658237941427391658865742139913586274249173865731658492586924317
  6 412756938896324751735918264269437815341285697578691423184562379653879142927143586
  6 492867513817935642635421987356142879781359264924786135249678351178593426563214798
  6 532961487816457293479823561254389716168745329397216845681574932945132678723698154
  6 541732968673498152289615374765841239498273516132569847314986725956327481827154693
  6 591762438486315729327489651168253947743891562952647183819526374235974816674138295
  6 592814673368527941741396258936481527184752396257639814475963182813275469629148735
  6 628914375194735826375268491916842753753196284482573619261357948849621537537489162
  6 687914325519382746243765918174238569862591473935476281398147652756823194421659837
  6 748159236326748519159326478591263847263487951487591623835614792612975384974832165
  6 759681342234759618861324597675918423342567981198432756587196234423875169916243875
  6 781624593392857164465913287913578426654239718827146359578462931239781645146395872
  6 863541279951327846247689315592714683318956427674238591729863154486195732135472968
  6 876945231945231876231876945719362458462758319358419762527194683693587124184623597
  6 894365172657421938213789546576214389938657421142893765465132897389576214721948653
  6 967451823538792416124863759853614297792538164416927538279385641641279385385146972
  6 982614573375829416614537289298753164753461892461298357537982641146375928829146735
  8 895423671126978543347165298234516987651897432789342156473651829562789314918234765
  9 145278693263945718978163425814327956526894137397516284632459871451782369789631542
  9 145396872826174539937528416682417395514639728793852164451963287379285641268741953
  9 217853946694127835583964172352419687149678523768532491425396718936781254871245369
  9 269435718817269345435817296983521467521746983746983152178354629692178534354692871
  9 327416985819753462654928731173692548598341276246875193931287654762534819485169327
  9 328947516469521387571683492613479825784215963295836174142368759856794231937152648
  9 476358912251694738983127465538219647714865329692473581129746853345981276867532194
  9 518392647473685192692147385951234768387569214264718539739456821826971453145823976
  9 541982637239761458867345129785493261194826375623517984472659813318274596956138742
  9 584671392193258647726349185265487913349516278871932564932864751618725439457193826
  9 751982463263471958894653172175298634489365721326147589517829346632714895948536217
  9 819542763543679182672813459257136948384795216961428375728351694195264837436987521
  9 826375491139642587754918263578193624362457819941286735693524178285731946417869352
  9 914523876532867149876941253149235687768419325325678914491786532687352491253194768
  9 918246573753819246264573198537198462642735981189462735891624357426357819375981624
  9 964813752318527946572469138183946275496275381257138469831752694649381527725694813
 12 279684135864531927351729486127395864648217593935468712713952648592846371486173259
 12 296431875548679132317852469123768954964325781785194623871543296632917548459286317
 12 361978254524361798978254361452136987897542136136897542789425613613789425245613879
 12 381697542452183976796254831813976425524318697967542318245831769679425183138769254
 12 634789521851624793927135468263478915149352876785961234516247389492813657378596142
 12 718695234249731685653284791587946312136852947492317856924173568375468129861529473
 12 861942735249537681375168249534279168186354972927816453493681527618725394752493816
 18 135748629926351478874269531487135296351692847269487153692513784748926315513874962
 18 167853942835249671294176358526987413789314526413625789942761835358492167671538294
 18 196587423423169578857324619578243961619758342342691785961432857785916234234875196
 18 231795846957846312684231579896124735573689124412573968129457683368912457745368291
 18 295476831467318925381259647529764318674831592138592476746925183813647259952183764
 18 297681534854723961163954278536872149921435687478169352782596413345218796619347825
 18 316284759759631842842975316128749563497356128563812497931468275275193684684527931
 18 329786541486351279751429836178932465935648712642175398294817653513264987867593124
 18 352781946617934258849265713761428539235196487984573162193652874578349621426817395
 18 352974168489156237671283945265739814147862593938541726726398451814625379593417682
 18 356984721172536948489127356518342679967815432243769185721653894635498217894271563
 18 435861792867295134291437568314678259958312476672954813146789325783526941529143687
 18 456197238921348765837256491645719823783625149192834576564971382378562914219483657
 18 486732159372591684951846273139487526847265931625319748263954817594178362718623495
 18 538974162216583947479162358345719286791628435862435791987246513153897624624351879
 18 569378241241965387387421695412596738695837124873142569738214956124659873956783412
 18 573912486498765132612843975261438597357129648849657213735291864126384759984576321
 18 579834612162579384834162759483627195627915843915483267296751438348296571751348926
 18 581763294362948517749125386236894751158376429974512638815637942497251863623489175
 18 642158793981372645375496128234615879198237564567849312453961287726584931819723456
 18 642371895985426731713598624426985173137264589859713462371859246598642317264137958
 18 748261359563849721219753864921386475874925136356174982137592648495638217682417593
 18 753869214698241357412537689124375968986412735375986142869124573241753896537698421
 18 763529481548136792192784356314865279256397148879241635681453927935672814427918563
 18 765134298314298675928675134472519386591863742836427951649352817253781469187946523
 18 854327619169485372327916584273691458691548237548732961732169845916854723485273196
 18 864932157759168432231457968618243579547896321392715684986321745175684293423579816
 18 912534678678921543543687912435712896896453721721869435269178354354296187187345269
 18 923517468684932715571648923736891542819254376245763891468329157157486239392175684
 18 928354176674291835531768429745829613286135947319476582192547368867913254453682791
 18 987561423156234987234987156879615234561342879342879561798423615423156798615798342
 27 528697134497531826631428795275916483386274519914385672152869347763142958849753261
 27 657132984948576231213489675539724168472861593186395427894213756321657849765948312
 36 145836279297514386368729154683245917971368425452197638836471592529683741714952863
 36 295134768761829345438576921843765192529341876176298534617982453952413687384657219
 36 432587916875961234961324785324875691196432857587196342243758169619243578758619423
 36 453619278728354619169782543231975864684231957597468321916827435345196782872543196
 36 467259381528317694139648275285493167674182539391576428746835912852961743913724856
 36 537812694162495378948367152789521436315946287624783519873254961251679843496138725
 36 594617328168234597327958164971465832643821759285793416412386975756149283839572641
 36 621845793759163482438972615594731268216458379387629541162584937875396124943217856
 36 652397418973841652418265973526418397397652184184739526739184265841526739265973841
 36 685471392793286451421935768354897216912653847867124935539768124176342589248519673
 54 162457893534189762897236514345891627978362145621574938216745389789623451453918276
 54 329786415578124369416593278854912736732648591691357824167435982243869157985271643
 54 361542789245798136897163524734219658586374912129856473672481395953627841418935267
 54 367145829829673514514298367482369751751824936936517482245986173173452698698731245
 54 514692873982173654763854192391746528478521936256938741127365489649287315835419267
 54 617342895432598761958167243863921574745683129291475386589716432324859617176234958
 54 847132659231569478965748312618973524452816793379254186583627941194385267726491835
 54 891632574632475981475918236754189623326754198918326457263547819189263745547891362
 54 967248315531976428842513796679824153315697284428351967284135679153769842796482531
 72 274158639581396742963427815639581274815274963742963581396742158427815396158639427
 72 478156923321974856569832147142769538837541269695283714713495682284617395956328471
108 256473918891652743374198562189526374437981256625734891562819437743265189918347625
108 782695314153842796964713258431287965825469173679351482248976531317528649596134827
108 935187246246359718718462935462593871359718462871624359624935187187246593593871624
162 125867439876493125943521687394215768687934512512678943439152876768349251251786394
648 765891324891243576243765189189324657324576918576189432432657891918432765657918243

The next obvious step would be to do as eleven has done for single symmetries and produce a "nice" description of each group. That's doable given the code I've already written, but it will have to wait until I've got more time.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby JPF » Sun Jan 18, 2009 8:54 am

How the size of each group fits with the number of grids given by gsf here ?
gsf wrote:here is a table of #autmorphisms and #essentially-different-grids with that number of automorphisms
Code: Select all
   1 5472170387
   2     548449
   3       7336
   4       2826
   6       1257
   8         29
   9         42
  12         92
  18         85
  27          2
  36         15
  54         11
  72          2
 108          3
 162          1
 648          1

JPF
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Postby Red Ed » Sun Jan 18, 2009 4:49 pm

My calculations go a step further and actually find the symmetry group in each case. So, for example, where gsf - and kjellfp before him - shows a count of 548449 e-d grids that each have exactly two (one non-trivial + the identity) automorphisms, I have shown that the corresponding 548449 symmetry groups boil down to "essentially" just three types. (Actually that is obvious from the table of conjugacy classes; but other parts of the table are not obvious.)

But it's a good prod: I ought to write out the number of e-d grids for each symmetry group. That's just a case of running the program again (fairly quick) and maintaining a counter for each symmetry group.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby eleven » Sun Jan 18, 2009 7:35 pm

Thanks for this list, Red Ed.
Without a program it is too hard for me to find the symmetries in the grids, so i will patiently wait:) ( i am short of time either).

Surprising for me is, that there is a third symmetry with 4 automorhisms. I thought, there only would be the quarter turn (90° rotational) and the double diagonal symmetry. Whats the third one ?
eleven
 
Posts: 1741
Joined: 10 February 2008

Postby ronk » Sun Jan 18, 2009 8:51 pm

eleven wrote:I thought, there only would be the quarter turn (90° rotational) and the double diagonal symmetry. Whats the third one ?

Perhaps it's simultaneous horizontal and vertical ("double axial") symmetry.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby StrmCkr » Sun Jan 18, 2009 9:31 pm

heres my down of my findings...
Last edited by StrmCkr on Tue Jan 20, 2009 4:09 pm, edited 3 times in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 755
Joined: 05 September 2006

Postby eleven » Sun Jan 18, 2009 9:57 pm

ronk wrote:Perhaps it's simultaneous horizontal and vertical ("double axial") symmetry.

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)
eleven
 
Posts: 1741
Joined: 10 February 2008

Postby eleven » Mon Jan 19, 2009 1:21 am

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

DS: (14)(2)(35)(6)(78)(9)
CS: (1)(2)(3)(45)(67)(89)
RS: (13)(2)(4)(5)(68)(79)
eleven
 
Posts: 1741
Joined: 10 February 2008

Postby udosuk » Mon Jan 19, 2009 2:43 am

Great, thanks for the immaculate results, guys.:)

I suppose given time I'd set out to define each of all 122 automorphisms in terms of the combinations of the 13 basic symmetries. But it will be a major project and unfortunately, summer holiday Down Under is almost over.:(

So, in summary, there are 13 basic symmetries: MR|MC, M\|M/, JR|JC, GR|GC, FR|FC, WR|WC, J\|J/, BR|BC, F\|F/, HT, QT, \M|/M, RS|CS. Or, if we use L for "line" to represent "row/column": ML, MD, JL, GL, FL, WL, JD, BL, FD, HT, QT, DM, LS.

These 13 can be merged to form 13 other symmetries (here "merged" means a single digit remapping system allows for multiple basic symmetries to co-exist, either locally or globally): MLDD, MDLL, JGGL, GJJL, FWWL, WFFL, DMMD, DMJD, LSML, LSJL, LSGL, LSJGGL, LSGJJL.

Together these 26 symmetry groups are essentially all possible automorphisms with a single digit remapping system. However, with different digit remapping systems, a sudoku grid can possess more than one of these symmetries simultaneously, and I'd call these "combined symmetries".

So it seems there are 122 different possible combinations of these 26 symmetries for a sudoku grid. (And if we count the trivial combination of 0 symmetry, 123 in total.) Looking forward to working out all the formulas.:) And I'd be interested in how many of these 26 symmetries the Most Canonical grid (with 648 automorphisms) possess.:?:
udosuk
 
Posts: 2698
Joined: 17 July 2005

PreviousNext

Return to General

cron