The New Sudoku Players' Forum

by **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..

by **StrmCkr** » Sat Jan 10, 2009 3:16 pm

thanks elven:)

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

by **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!

When I have time (eventually) I'll write a detailed article on all 13 "basic" symmetrical groups.

by **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...

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

by **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.

by **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

by **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.

by **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 ?

by **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.

by **StrmCkr** » Sun Jan 18, 2009 9:31 pm

deleted

by **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)

by **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)

by **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. :?:

The New Sudoku Players' Forum

About Red Ed's Sudoku symmetry group