## About Red Ed's Sudoku symmetry group

Everything about Sudoku that doesn't fit in one of the other sections
deleted back to the drawing board... didnt think off patterns being found on same row in a house befor...

thanks red ed for the examples they help alot!
Last edited by StrmCkr on Fri Jan 02, 2009 10:12 am, edited 1 time in total.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 840
Joined: 05 September 2006

As udosuk already stated, all the "new" symmetries with 6/9-cycles, i.e. those we have not already handled in the symmetry threads, can be expressed also as a combination of 2 "classical" symmetries. I updated the table in the first post accordingly, also inserted the Bludo technique for the block symmetry and added the names, udosuk mentioned here.
In the bands group i changed the ops B(CR) to S(RC), so now the boxes really move in bands instead of the stacks.

From the solvers POV its easier to look at 2 simpler symmetries than at one complicated one with 6- or 9-cycles, so the new symmetries are better handled as combined ones.
We are left then with 13 classical symmetries, and after Bludo was found, only for those with fixed boxes and the Band symmetry no special techniques are known for solving (additionally probably the Gludo/Band symmetries, when 6 or all numbers are fixed).

I would like to add names for those i dont have one so far, maybe udosuk can help.

A word to the sticks symmetry. Though its the most common one, it is hard to find any challenging puzzles, if you dont have such a good program as Mauricio. And also his top rated puzzles solve with singles after applying the symmetry to the fixed cells. (A reason for this is, that each fixed cell "sees" 4 others, not only 2 like with diagonal symmetry, so the 9 number normally can be put in from the beginning)

Thanks to Red Ed for giving us an idea how the number of non-equivalent grids was calculated.
eleven

Posts: 1865
Joined: 10 February 2008

We now generated 28 puzzles with sticks symmetry with ER ratings between 9.0 and 9.2. 24 of them solved with singles after placing the numbers in the fixed cells (if you cant, the puzzle is not unique), 3 needed an xy-wing and only this one more, but i cant see a symmetry move.
Not very exciting ...

Code: Select all
` +-------+-------+-------+ | 7 . . | . . . | 1 4 . | | . . . | . . 3 | . 6 8 | | . . 2 | 8 . . | 5 . . | +-------+-------+-------+ | 4 . 5 | . 1 . | . . . | | . 2 . | . . . | . . . | | . . . | 7 . 6 | . . . | +-------+-------+-------+ | . . 6 | . . . | . 5 1 | | . . . | 3 . . | 9 7 . | | 2 . . | . . 9 | . . 4 | +-------+-------+-------+`

This is the list of the other puzzles:
..1.8..6...4..21....71..5..9187.6.........8.9....2....1...9..7.5..2....16....1..4
..1..96.436...1......65.3..6.7.2....8.9.......1....9.81..8..5.7.731.........47..3
.....169..4...6..26..25.8.4.3.5.4...9.8......5.4.1.......1...87.5.7..2....7.425.9
....9.1..9..5...4715...29.........3..2.7.6...4.5..........8...1..8..465..412....8
5...64..39.....1...72..3.8...........1.6.7.......3.8.9..457.3....8.....126.3...9.
..46...8537.4....2.....1.......1.6.76.75.48.9.2.......5....749..63..52.....1.....
...9..6..65...7..1..25....45.4.2.9.8.........938...........8..7.476..1..2....45..
2..7....936...45.......214....9.8.1.4.5.......2....7.6..2..68...735....4...2...51
..8..31....4..879.....41....2....5.47.6...8.9.......1.9..3....15..9...86...15....
..6..4..5..8.....25..271.8.......8.9...7.6.1.....2....7..5..4..9.....2....4162.9.
...3...4.7....68.38..19.....2....5.45.4...6.7.......3......3.5...67..3.9..9.81...
8....4..9.5.37.4.......12......3....6.7......5.47.6.1...95..8...4..63..5...1....2
.79..2.....65.37..3......42.1.8.9.........8.9...7.6.3.86.2.....7..3.4..6..3...25.
5..1.9..6..1.5.3..7....2..58.9.2.......5.49.8.......3...48.17..1...4...3..62..4..
.41.9.6....57.4..13....1...8.9.2....5.49.8.1.......9.815..8...74..5.61....31.....
6..3....4...8....23...951..5.4....2..1.7.6..............7..35.......92....348...1
6....1..82....97....52....3...5.4....2.......9.8716.....71..9....28....64....23..
...5.8..16....3.....27...84.2.......7.6....3.4.5...8.9...9.41....73.....2....659.
.7...95..3.....1..5.63...879.8.......3.6.7..........1..6.8....4..3.....17.4..369.
47..682....274....3.6..5..75.4....2.....3.9.8..........6597...22...56...7.34..6..
2....5.434..8....6.9.1..2...2.9.8.......1....7.6........24..35...5..97...8...1..2
38...2.4...7..31....178...5...4.5.1.....2.8.9..........932...5.6..3....11...964..
4......79...2..4..39..74......8.97.67.6.2.....1.........5...86......2..5.8356....
..4..56.......829...32....5...6.7...6.75.4.1..3.......5..4....7...9...823....24..
6..7.1..53.......1.5....29....8.9...8.94.5.2..3.........71.64....3...1...4.....82
.53.7.2..1.....9..7..8....5......5.4...637......4.5.2.34..6...2..1.....8..6..94..
3..9.57..17......2..8..14......1.8.9.3.6.7..............34.8..6.61...2..9..1....5
eleven

Posts: 1865
Joined: 10 February 2008

eleven wrote:... and only this one more, but i cant see a symmetry move.
Not very exciting ...

Code: Select all
` +-------+-------+-------+ | 7 . . | . . . | 1 4 . | | . . . | . . 3 | . 6 8 | | . . 2 | 8 . . | 5 . . | +-------+-------+-------+ | 4 . 5 | . 1 . | . . . | | . 2 . | . . . | . . . | | . . . | 7 . 6 | . . . | +-------+-------+-------+ | . . 6 | . . . | . 5 1 | | . . . | 3 . . | 9 7 . | | 2 . . | . . 9 | . . 4 | +-------+-------+-------+`

After easy moves:

Code: Select all
`+-------------------+-------------------+-------------------+| 7     5689  389   |*256   569  *25    | 1     4     23    || 159   459   149   | 1245  4579  3     | 27    6     8     || 13    46    2     | 8     467   147   | 5     9     37    |+-------------------+-------------------+-------------------+| 4     3     5     | 9     1     8     | 67    2     67    || 6     2     7     |*45    3    *45    | 8     1     9     || 89    1     89    | 7     2     6     | 4     3     5     |+-------------------+-------------------+-------------------+| 389   4789  6     |*24    478  *247   | 23    5     1     || 158   458   148   | 3     4568  1245  | 9     7     26    || 2     57    13    | 156   567   9     | 36    8     4     |+-------------------+-------------------+-------------------+`

Actually there is a simple symmetry-BUG-lite move (I'm not that hot on "classical uniqueness techniques" like BUG-lite but since all symmetry-based moves are also uniqueness-based I guess here the "ethical issue" is diluted a little bit ):

r157c46 can't form the deadly pattern {245}
Stick Symmetry: r1c4+r7c6=[67]

Unfortunately, that doesn't crack the puzzle directly - you still need a chain-like move later on, which can actually be applied right away. So let's forget the move above and proceed from the previous pencilmark state:

Code: Select all
`+-------------------+-------------------+-------------------+| 7     5689  389   |#256   569   25    | 1     4    *23    || 159   459   149   | 1245  4579  3     | 27    6     8     || 13    46    2     | 8     467   147   | 5     9     37    |+-------------------+-------------------+-------------------+| 4     3     5     | 9     1     8     | 67    2     67    || 6     2     7     |#45    3     45    | 8     1     9     || 89    1     89    | 7     2     6     | 4     3     5     |+-------------------+-------------------+-------------------+|-389   4789  6     |#24    478   247   |*23    5     1     || 158   458   148   | 3     4568  1245  | 9     7     26    || 2     57   *13    |#156   567   9     |-36    8     4     |+-------------------+-------------------+-------------------+`

r1579c4 from {12456} must have 1 or 2 or both
Stick Symmetry: r1c9+r7c7+r9c3 can't be [221]
=> r7c7+r9c3 can't be [21], must be [23|31|33] having 3
=> r7c1+r9c7, seeing r7c7+r9c3, can't have 3

udosuk

Posts: 2698
Joined: 17 July 2005

### Re: About Red Ed's Sudoku symmetry group

eleven wrote:
Code: Select all
`    M         C         N        L    S1. Fixed boxesR           8    107.495.424   3    N  Mini-row symmetryRC1         7     21.233.664   3    N  RC1C2       9      4.204.224   3    N  RC         10      2.508.084   3    N  Mini-diagonal symmetry`

Just some thoughts here:

"Mini-row symmetry" should be given by the mapping "C" instead. As a result I think the table should be like this:

Code: Select all
`M           C         N        L    S1. Fixed boxesC           8    107.495.424   3    N  Mini-row symmetryR1C         7     21.233.664   3    N  MDS @ band 1, MRS @ band 2,3R1R2C       9      4.204.224   3    N  MDS @ band 1,2, MRS @ band 3RC         10      2.508.084   3    N  Mini-diagonal symmetry`

Also, since you asked me for names, here are some proposals:

C -> Mini-Row Symmetry (MRS)
R -> Mini-Column Symmetry (MCS)
RC -> Mini-Diagonal Symmetry (MDS)
S -> Band Symmetry (BAS)
B -> Stack Symmetry (SAS)
BS -> Block Symmetry (BOS) (Bludo applicable)
SR -> Horizontal Glide Symmetry (HGS) (Gludo applicable)
BC -> Vertical Glide Symmetry (VGS) (Gludo applicable)
DD2 or BxRxSxCx-> Half-Turn (180 Degree Rotation) Symmetry (HTS)
DBxRx -> Quarter-Turn (90 Degree Rotation) Symmetry (QTS)
D -> Leading-Diagonal (Reflection) Symmetry (D\S)
D2 -> Non-Leading-Diagonal (Reflection) Symmetry (D/S)
SxRx -> Horizontal Stick Symmetry (HSS)
BxCx -> Vertical Stick Symmetry (VSS)

(All names/abbreviations are subjected to rectifying.)

Also note that MRS, MCS, HGS, VGS sometimes can be applied locally in the grid (i.e. in certain bands/stacks) instead of globally to the whole grid.

The next item on my wishlist is an example puzzle/solution grid for each of the 26 groups.
udosuk

Posts: 2698
Joined: 17 July 2005

udusuk wrote:r1579c4 from {12456} must have 1 or 2 or both
Stick Symmetry: r1c9+r7c7+r9c3 can't be [221]
=> r7c7+r9c3 can't be [21], must be [23|31|33] having 3

Nice solution using the symmetry, though not easy needing a 4-cell ALS. Because i misinterpreted the notation first: The second line follows from the first (not from the symmetry).
Since i doubt that many sticks puzzles will be generated, that need a second interesting step, its a historical solution

Now to the last post. I think, we should be careful here not to repeat the problems we have with this flood of horribly bad and partially contradictory names for solving techniques. How often was the y/Y/w-wing [styles]/SRP theme discussed ? And why does everyone call a unique rectangle, what definitely is the opposite ?
We are only a few people and should manage to have the same name for the same thing - and the name should make sense. (Also here i already saw discrepances, which lead to a discussion about Eels vs. EUR's, later on NEP's - i really want to avoid that from beginning).

So thanks for the suggestions, and this is my opinion:

I not happy with "Block symmetry", because i suppose, most people would more expect it to be the "Band symmetry" (a stack - a block of boxes - moves right in the symmetry) than what is meant. Didn't Mauricio originally call it the "Threefold symmetry" ? For me a better name.

"Mini-row symmetry" is no good name either: It is true, that its analogue to the Band symmetry, where the boxes move in the band, here the cells in the minirow. But when i think of mini-row and symmetry, i am interested, where it goes to by the symmetry in first line, only in second line, what happens with the cells inside. Thats why i had as mini-row symmetry, what you would call mini-column symmetry. So my proposal is "Mini-band symmetry".

"Mini-diagonal symmetry" is definitely a wrong name: The cells are not diagonally reflected like the cells in the diagonal boxes, when you have "Diagonal symmetry". Unfortunately "Mini-threefold symmetry" is a very long name.

"MDS @ band 1, MRS @ band 2,3" is much too complicated for a simple thing. I have no suggestion yet, it also depends on the names we can find for the "Gludo applicable" symmetries, which are similar. "Horizontal Glide Symmetry" is fine for me, so we just have to add something to say that 1, 2 or 3 bands have this glide.

I wouldn't need new names for the rotational symmetries, but if everything needs a TLA ...

Hope that others also have suggestions here.

udusuk wrote:The next item on my wishlist is an example puzzle/solution grid for each of the 26 groups.

The time my friend and i reserved for this thread is over. But the program is here and we may adopt it for generating other puzzles step by step. But for the others out of the symmetries in the table, where no examples exist so far, i dont see much worth. E.g. you will never find a good puzzle with a 9-cycle symmetry, i suppose. Same for the exotic stick symmetries. What we got was trivial even without the stick symmetry included. But here are 3 grids, we have calculated:
Code: Select all
` +-------+-------+-------+ | 1 7 6 | 2 5 4 | 3 9 8 | | 3 9 4 | 1 7 8 | 2 5 6 | | 2 8 5 | 3 6 9 | 1 4 7 | +-------+-------+-------+ | 4 1 7 | 8 2 5 | 6 3 9 | | 5 2 8 | 9 3 6 | 7 1 4 | | 6 3 9 | 4 1 7 | 8 2 5 | +-------+-------+-------+ | 9 4 1 | 7 8 2 | 5 6 3 | | 7 6 3 | 5 4 1 | 9 8 2 | | 8 5 2 | 6 9 3 | 4 7 1 | +-------+-------+-------+Sticks (1)(2)(3)(47)(58)(69)S (123)(486)((597)BxCxS (123)(456789) +-------+-------+-------+ | 8 7 2 | 1 6 5 | 9 4 3 | | 6 5 3 | 2 4 9 | 7 8 1 | | 4 9 1 | 3 8 7 | 5 6 2 | +-------+-------+-------+ | 7 2 4 | 9 1 6 | 8 3 5 | | 5 3 8 | 7 2 4 | 6 1 9 | | 9 1 6 | 5 3 8 | 4 2 7 | +-------+-------+-------+ | 2 4 5 | 8 9 1 | 3 7 6 | | 3 8 9 | 6 7 2 | 1 5 4 | | 1 6 7 | 4 5 3 | 2 9 8 | +-------+-------+-------+Sticks (1)(2)(3)(47)(58)(69)R (123)(486)(597)BxCxR (123)(456789) +-------+-------+-------+ | 6 9 1 | 4 7 2 | 8 5 3 | | 5 4 3 | 9 8 1 | 7 6 2 | | 2 8 7 | 3 6 5 | 1 4 9 | +-------+-------+-------+ | 9 2 6 | 5 1 8 | 4 3 7 | | 8 1 5 | 7 3 4 | 9 2 6 | | 7 3 4 | 6 2 9 | 5 1 8 | +-------+-------+-------+ | 1 6 9 | 2 4 7 | 3 8 5 | | 3 7 8 | 1 5 6 | 2 9 4 | | 4 5 2 | 8 9 3 | 6 7 1 | +-------+-------+-------+Sticks (1)(2)(3)(47)(58)(69)SR2 (123)(486)(597)BxCxSR2 (123)(456789)`
eleven

Posts: 1865
Joined: 10 February 2008

### Re: About Red Ed's Sudoku symmetry group

udosuk wrote:The next item on my wishlist is an example puzzle/solution grid for each of the 26 groups.
I now have a catalogue of all of them (automorphic solution grids, that is) which I am in the process of canonicalising and deduping.

Here's one solution grid from each class. I've borrowed eleven's terminology, since that's what you seem to have got used to already.
Code: Select all
`1. Fixed boxesR           8 : 123456789987123546645987132312564897879312465456879213231645978798231654564798321RC1         7 : 123456789897123456645978123312564978978312564456897312581249637734681295269735841RC1C2       9 : 123456789456789123789231645247395861691842537835617294374168952518924376962573418RC         10 : 1234567894567891237891234562148659378659372149372148653715426985426983716983715422. Boxes move in bandsS          25 : 123456789789123456645798123312564897897312564456879312231645978978231645564987231SR1        28 : 123456789456789123789123456234891567591267834867534291348915672612378945975642318SR1R2      30 : 123456789456789123789123456231897564567234891894561237315648972648972315972315648SR         32 : 123456789897123654654879132312564978978312465546798321231645897789231546465987213SC1        27 : 123456789456789123789123456234567891567891234891234567345678912678912345912345678SR1C1      26 : 123456789456789123789231645231897456645123978897564231312978564564312897978645312SR1R2C1    29 : 123456789456789123789231645231897456645123978897564231312645897564978312978312564SRC1       31 : 1234567894567891237892316452315649786458972318971234563126458975649783129783125643. Boxes move triangular (B 159, 267, 368)BS         22 : 123456789456789123789123456235964817817235964964817235392641578578392641641578392BSR1       24 : 123456789456789231789123645231564897564897312978312564312645978645978123897231456BSR1C1     23 : 1234567894572891636891734522357418968163925749745682313928176455689243177416359284. Rotational symmetriesDD2        79 : 123456789869127435457938126216374958785219643934685217671543892392861574548792361DBxRx      86 : 1234567894567892317893124562149385673756418926985273145612739488371946259428651735. Diagonal symmetriesD          37 : 123456789579128643684739125412673958958214376367985214831562497796841532245397861DBS        43 : 123456789457189236968372514291738465374265198685941327546813972732694851819527643DRC        40 : 1234567894567892317891236452153489763986725146749158235418973628325641979672314586. Sticks symmetriesBxCx      134 : 123456789978213465546798231217864593835129674469375128752931846694582317381647952BxCxR     135 : 123456789456789123789123456234591867567834291891267534378942615612375948945618372BxCxS     145 : 123456789457189326689327154291635847745891632836742591318264975574918263962573418BxCxSR2   144 : 123456789456789123789132465218967534564213978937548216391875642645321897872694351BxCxSR    142 : 123456789456789123789123456214937865865214937937865214342678591591342678678591342BxCxSR1R2 143 : 123456789456789123789132465248573916537961248961248537394815672672394851815627394`

In some sense, this is just a rehash of work that I did with Frazer three years ago!
Red Ed

Posts: 633
Joined: 06 June 2005

Thanks Red Ed for all the example grids. Saved and studying.

Also I agree with you eleven that my names need a lot of rectifying. I'm no good in the art of nomenclature and just name them with my instincts, which are probably too inconsistent and I just wish someone else can systematically name them properly.

Meanwhile I have this project to briefly describe the "instinctive structure" of each of the 14 "classical" symmetries, i.e. the way digit cycles/pairings generally appear in the grid.

(The 14 "classical" symmetries are actually of 8 essentially different ones as besides the 2 rotational symmetries all other 12 are actually 6 pairs, each in 2 orientations.)

udosuk

Posts: 2698
Joined: 17 July 2005

thanks red ed that helps me alot
i can see all those symmetries better with the complteted grids.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 840
Joined: 05 September 2006

udosuk wrote:(The 14 "classical" symmetries are actually of 8 essentially different ones as besides the 2 rotational symmetries all other 12 are actually 6 pairs, each in 2 orientations.)
I counted 13. In fact all possible symmetries are built up very simple.

We have the 2-cycled symmetries
- 180° rotational
- diagonal
- sticks, described here

the 4-cycled symmetry
- 90° rotational

and the 3-cycled symmetries. They are built with only 2 patterns:

Code: Select all
` A1 A2 A3         A1 C2 B3 B1 B2 B3   and   B1 A2 C3    C1 C2 C3         C1 B2 A3`

where A1 goes to A2 goes to A3 goes to A1, same for B, C

These patterns can be
- pattern 1 or 2 in the cells of all boxes of a band (fixed boxes symmetries)
- the mini-rows in a band have pattern 1 or 2 (Band symmetries)
- boxes have pattern 2 (Block/Threefold symmetry)

Thats all.

[Added:] I suspect, that to get all possible combinations of symmetries, you just have to add the 90° rotated versions (bands/rows/columuns -> stacks/columns/rows) of the Diagonal, Band and fixed boxes symmetries and try to combine them.
eleven

Posts: 1865
Joined: 10 February 2008

eleven wrote:In fact all possible symmetries are built up very simple.

We have the 2-cycled symmetries
- 180° rotational
- diagonal
- sticks, described here

the 4-cycled symmetry
- 90° rotational

and the 3-cycled symmetries.

How would you correlate the above to gfroyle's Combinatorial Concepts With Sudoku I: Symmetry, Gordon Royle, March 29, 2006 ?

Additionally, discussion of this paper occurred at Sudoku Symmetry - Formalized.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:How would you correlate the above to gfroyle's Combinatorial Concepts With Sudoku I: Symmetry, Gordon Royle, March 29, 2006 ?

Additionally, discussion of this paper occurred at Sudoku Symmetry - Formalized.

Ron, the 2 links you cited are concerning the clue-pattern/shape symmetry of puzzles. In this thread Red Ed, eleven, I & others are talking about the automorphism symmetry of puzzles/solutions. Two different topics. (Although all automorphic puzzles should be in theory morphable into a form with a certain clue-pattern/shape symmetry, we generally aren't putting much interest in that aspect.)

eleven wrote:I counted 13.

You probably didn't count diagonal reflection symmetry in 2 different orientations.

I generally agree with your view that all symmetries can be built up from various basic ones, but am still working hard to write out all 26 groups in details. The 5 "flavoured" stick symmetries are especially tricky to analyse.

Red Ed, I've just realised most of the example grids you listed are normalised. Which means I have my work cut out to work out the morphing operations to "expose" the symmetries. Very tough work!
udosuk

Posts: 2698
Joined: 17 July 2005

udosuk wrote:the 2 links you cited are concerning the clue-pattern/shape symmetry of puzzles. In this thread Red Ed, eleven, I & others are talking about the automorphism symmetry of puzzles/solutions. Two different topics.

I don't think they're as different as you make it sound.

In order to have "clue value symmetry", you first need "clue positional symmetry". And the symmetry doesn't need to be perfect, i.e., the "symmetric distance" may be greater than zero.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:How would you correlate the above to gfroyle's Combinatorial Concepts With Sudoku I: Symmetry, Gordon Royle, March 29, 2006 ?

Gordon was just looking at isometries -- that is, the different forms you can get by rotating and turning-over a puzzle drawn on a piece of tracing paper. Other validity-preserving operations such as band-cycling are, I suppose, not so pleasing to the human eye. That's why his list of symmetries is so much shorter than our list of "symmetries". To be fair, "symmetry" is probably not quite the right word for what we're doing.
Red Ed

Posts: 633
Joined: 06 June 2005

udosuk wrote:Red Ed, I've just realised most of the example grids you listed are normalised. Which means I have my work cut out to work out the morphing operations to "expose" the symmetries. Very tough work!

Ah yes, sorry about that. I've done one of those "expositions" myself. It was tough, sure, but satisfying ... just like a good Sudoku puzzle
Red Ed

Posts: 633
Joined: 06 June 2005

PreviousNext