About Red Ed's Sudoku symmetry group

Everything about Sudoku that doesn't fit in one of the other sections
ronk wrote: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.

In my previous post I also wrote:(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.)

I thought I made that point already, perhaps you missed that part?

While I said "two different topics", I didn't imply they're "two totally irrelevant topics".

However, the automorphic puzzles/solutions we're studying, has the property that you can scramble them randomly that no visual "clue positional symmetry" appears anymore, but the automorphism still exists.

Also currently in this thread a heavy focus is on the solution grids (or so it seems to me). But I think the studying of "clue positional symmetry" isn't too relevant to the solution grids (please correct me if I'm wrong).

Also, some of the "clue positional symmetries", such as horizontal/vertical reflections, has no automorphism to match.

Bottomline: if you replace all the clues of an automorphic puzzle by asterisks and perform the same row/column transformations that morph it back, you will find a certain "automorphism symmetry" on the asterisks, such as this one:

Code: Select all
`.*..**.....**.*...*..**........*..**...*..**......**.*...*...*......**......*...*`

However, I don't think a lot of players consider the clue pattern above "symmetrical", and probably not in the sense of gfroyle's paper.

That said, it would be very nice if you or someone else can somehow connect these 2 concepts together and develop something helpful for cracking very diabolic/evil puzzles with heavily scrambled hidden automorphisms.
udosuk

Posts: 2698
Joined: 17 July 2005

udosuk wrote:... the 14 "classical" symmetries, ...
What do you mean by "classical" symmetry?

You can generate all 3359232 isomorphisms/transformations from combinations of just three basic operations (plus relabelling). There are several possible choices of generating set; here's the one that Frazer found using GAP:
Code: Select all
`gap> SmallGeneratingSet(sudoku);[ (1,44,13,61)(2,53,15,79)(3,35,14,70)(4,62,10,43)(5,71,12,34)(6,80,11,52)(7,    8,17,16)(9,26,18,25)(19,45,22,63)(20,54,24,81)(21,36,23,72)(28,41,67,    57)(29,50,69,75)(30,32,68,66)(31,59,64,39)(33,77,65,48)(37,40,58,55)(38,    49,60,73)(42,76,56,46)(47,51,78,74),   (1,43)(2,52)(3,34)(4,61)(5,70)(6,    79)(8,16)(9,25)(10,44)(11,53)(12,35)(13,62)(14,71)(15,80)(18,26)(19,    45)(20,54)(21,36)(22,63)(23,72)(24,81)(28,39)(29,48)(31,57)(32,66)(33,    75)(38,46)(40,55)(41,64)(42,73)(49,56)(50,65)(51,74)(59,67)(60,76)(69,77),  (1,46,64,19,37,55)(2,47,65,20,38,56)(3,48,66,21,39,57)(4,49,67,22,40,58)(5,    50,68,23,41,59)(6,51,69,24,42,60)(7,52,70,25,43,61)(8,53,71,26,44,62)(9,    54,72,27,45,63)(10,28,73)(11,29,74)(12,30,75)(13,31,76)(14,32,77)(15,33,    78)(16,34,79)(17,35,80)(18,36,81) ]gap> Size(SmallGeneratingSet(sudoku));3gap>`

Unravelling those will be a nice challenge for someone
Red Ed

Posts: 633
Joined: 06 June 2005

udosuk wrote:But I think the studying of "clue positional symmetry" isn't too relevant to the solution grids (please correct me if I'm wrong).

Duh!
ronk
2012 Supporter

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

After looking back to Mauricio's 11 puzzles with 2 symmetries i wonder, which combinations of symmetries might give interesting puzzles.

None with sticks, which solves each puzzle alone.
Same probably with Diagonal symmetry. Both the DDS puzzles i saw and Mauricio's 3 ones with Block symmetry were too easy. The one i posted here was the only hard one i could generate (and there aren't very much).
Also 3-band Gludo puzzles seem to be too easy to solve (the 2 combined ones by Mauricio were solved with Gludo alone).

But the combination of 180° and Block symmetry gave some nice puzzles. I solved all with symmetry alone, but often needed several steps (of course i might have missed a good one at the beginning).

So only combinations of 2 "weak" symmetries should make sense. To combine two 3-cycle symmetries probably also is an overkill. With one number found you could place up to 9.
This doesn't leave much:
180° combined with fixed boxes, Band and Block symmetries. And i doubt, that Band symmetry can make any puzzle interesting ...
eleven

Posts: 2013
Joined: 10 February 2008

A bit off topic.

I understand that any transformation (before relabelling) t can be written as a finite product of some basic transformations.

t=h1.h2….hn ; hi being one of the 3 "basic" operations given by GAP

t is actually a permutation of the digits 1,2,...,81
How many data are necessary to characterize a transformation t ?

Here is a solution with 14 numbers :
Take the first GAP's basic transformation h as example :
Code: Select all
`61 79 70 43 34 52 16 07 2562 80 71 44 35 53 17 08 2663 81 72 45 36 54 18 09 2757 75 66 39 30 48 12 03 2155 73 64 37 28 46 10 01 1956 74 65 38 29 47 11 02 2058 76 67 40 31 49 13 04 2259 77 68 41 32 50 14 05 2360 78 69 42 33 51 15 06 24`

The initial position of the digits is in the 9 boxes :

B1 B2 B3
B4 B5 B6
B7 B8 B9

The first 2 numbers give the location of B1, B5 after h

B1-->B6
B5-->B8

We can conclude that :
B9-->B1

Now, in each box h(B1), h(B5), h(B9), 4 numbers are required to be able to fill the box (3 in the main diagonal + one other)

Exemple h(B1) :
Code: Select all
`12  03   . .  01   . .   .  20`

is enough to fill h(B1)

For the boxes h(B1), h(B5), h(B9) a total of 3 x 4 = 12 numbers is then necessary.

Knowing the content of these 3 boxes :
Code: Select all
`61 79 70                  62 80 71                  63 81 72                                    12 03 21                  10 01 19                  11 02 20         40 31 49                  41 32 50                  42 33 51         `

it seems to me that all the h(i) are known [i=1,2,...,81]

and t can be characterized by [6,8 ; 12,01,20,03 ; 40,32,51,31 ; 61,80,72,79]

JPF
JPF
2017 Supporter

Posts: 3754
Joined: 06 December 2005
Location: Paris, France

edit
Last edited by StrmCkr on Mon Dec 17, 2018 11:16 am, edited 1 time in total.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 946
Joined: 05 September 2006

JPF wrote:Now, in each box h(B1), h(B5), h(B9), 4 numbers are required to be able to fill the box (3 in the main diagonal + one other)

3 numbers should be enough. 2 in a line fix one minirow (-column), one elsewhere the second, the third falls into place.
[Added:] If you use this for the boxes instead (which fixes vertical or horizontal orientation), you only need 2 from the diagonal inside the boxes. Then only 9 instead of the 14 numbers are needed.
Example: 657 924 557 would mean, box 1 goes to box 6, the first cell in box 1 to the 5th, the center cell to the 7th, same for boxes 2 and 4.

and t can be characterized by [6,8 ; 12,01,20,03 ; 40,32,51,31 ; 61,80,72,79]

Ah, isnt that R23DBSSc23c45c78R2 ?
You see, my notation is optimised for the symmetry operations only.

[Edit2: corrected a typo in the sample]
Last edited by eleven on Sat Jan 03, 2009 10:34 pm, edited 2 times in total.
eleven

Posts: 2013
Joined: 10 February 2008

Re: About Red Ed's Sudoku symmetry group

eleven wrote:
Code: Select all
`M           C         N        L    S2. Boxes move in bandsS          25     14.837.760   3    N  Band symmetrySR1        28      2.085.120   3    Y  GludoSR1R2      30        294.912   3    Y  GludoSR         32      6.342.480   3    Y  GludoSC1        27          5.184   9    N  equivalent to S+CSR1C1      26          2.592   9    Y  equivalent to SR1+CSR1R2C1    29          1.296   9    Y  equivalent to SR1R2+CSRC1       31            648   9    Y  equivalent to SR+C`

eleven,

I'm gradually studying your table in details. For this section I found that the comments for the last 4 groups are not correct - these are not equivalent to "S/SR1/SR1R2/SR+C". All of them have mini-row (C) symmetry but I don't see them having S/SR1/SR1R2/SR as you stated.

As a matter of fact, I think I've found 2 new "basic" symmetries from these 4 groups (SC1 & SRC1 respectively). I call them "full-row" and "sliding-row" respectively, and they both have a digit cycle of length 9 (as stated in your table). I'll soon reveal them in a summary post of all "basic/classical" symmetries with detailed descriptions.

Also on names, I think "band symmetry" for mapping "S" is really not good enough. In my current project I call the symmetry group "hopping-row" as the digit cycles appear on 3 separate cells on a row (e.g. r1c147).

PS:

The last several posts in this thread are getting very technical, I need some time to digest them. I'm still more inclined to work things out based on the classical symmetry groups so will at the moment give the GAP transformations a pass (even though I'm a fan of Boston Celtics' 3 great players ). Will also wait to see StrmCkr's new findings although I highly doubt the validity of his pattern which "maps into all 26 symmetric groups" (whatever it's supposed to mean).
udosuk

Posts: 2698
Joined: 17 July 2005

Thanks, you are right. i was too little interested in the 9-cycles to look at more than one column.
eleven

Posts: 2013
Joined: 10 February 2008

udosuk, I guess you missed it the first time I asked: what do you mean by "basic/classical" symmetry? How is "basic/classical" defined?
Red Ed

Posts: 633
Joined: 06 June 2005

udosuk calls the symmetries "classical", which we already used/investigated for solving, the rotationals, diagonals, sticks (3-cycled), 3-cycled Bands and more recently those with fixed boxes.

Three puzzles with 2 symmetries, 180° plus RC ("minidiagonal").
The first one is easy.
Code: Select all
` +-------+-------+-------+ | . . 2 | 8 9 . | . . . | | 7 . . | . 1 3 | . . . | | . 6 . | 5 . 4 | . . . | +-------+-------+-------+ | 1 . 7 | . . . | 2 8 . | | 6 4 . | . . . | . 7 1 | | . 2 8 | . . . | 4 . 6 | +-------+-------+-------+ | . . . | 7 . 9 | . 1 . | | . . . | 3 6 . | . . 4 | | . . . | . 5 2 | 8 . . | +-------+-------+-------+ +-------+-------+-------+ | . 5 . | . . 8 | . 4 . | | . . 9 | 1 . . | . . 8 | | 3 . . | . 4 . | 1 . . | +-------+-------+-------+ | . . 2 | 9 . . | . 1 . | | 7 . . | . 3 . | . . 4 | | . 6 . | . . 5 | 8 . . | +-------+-------+-------+ | . . 6 | . 7 . | . . 3 | | 2 . . | . . 6 | 5 . . | | . 7 . | 2 . . | . 9 . | +-------+-------+-------+ +-------+-------+-------+ | . . . | 3 4 . | . 1 . | | . . . | . 5 8 | . . 4 | | . . . | 1 . 9 | 8 . . | +-------+-------+-------+ | 8 3 . | . . . | 7 . 5 | | . 1 5 | . . . | 9 6 . | | 9 . 4 | . . . | . 3 2 | +-------+-------+-------+ | . . 2 | 5 . 6 | . . . | | 7 . . | 2 9 . | . . . | | . 6 . | . 7 3 | . . . | +-------+-------+-------+`
eleven

Posts: 2013
Joined: 10 February 2008

eleven wrote:udosuk calls the symmetries "classical", which we already used/investigated for solving, the rotationals, diagonals, sticks (3-cycled), 3-cycled Bands and more recently those with fixed boxes.

I was surprised that udosuk claimed to have found 2 new "basic" symmetries. If "basic" was a concept relating to solution grids then I could have helped you out. But if (as you seem to be saying) "basic" means "gives rise to a (specialised) solving technique" then I won't have anything to add!
Red Ed

Posts: 633
Joined: 06 June 2005

Red Ed wrote:I was surprised that udosuk claimed to have found 2 new "basic" symmetries. If "basic" was a concept relating to solution grids then I could have helped you out. But if (as you seem to be saying) "basic" means "gives rise to a (specialised) solving technique" then I won't have anything to add!

I call a symmetry "basic" when it can't be expressed as a combination of 2 or more of other symmetries. The adjective "classical" currently describes the 7 or 8 (depending if you count the 2 rotational symmetries together) symmetries that we've been analysing and developing new techniques for.

At the moment we can't see any interesting puzzle/technique for the 2 new symmetries I mentioned. But there are 2 more of them which I call "broken row/column" & "full diagonal", hopefully they're more likely to produce interesting puzzles/techniques.

So for now these are the 13 groups of "basic" symmetries which I think should be exhaustive:

1. Mini-Row/Mini-Column (MR/MC) - 3 cycle - e.g. r1c123

2. Mini-Diagonal (MD or M\ or M/) - 3 cycle - e.g. r1c1+r2c2+r3c3

3. Jumping-(mini-)Row/Jumping-(mini-)Column (JR/JC) - 3 cycle - e.g. r1c147
(previously called "hopping row/column" or "stack/band symmetry")

4. Gliding-(mini-)Row/Gliding-(mini-)Column (GR/GC) - 3 cycle - e.g. r1c1+r2c4+r3c7
(previously called "horizontal/vertical glide")

5. Jumping-(mini-)Diagonal (JD or J\ or J/) - 3 cycle - e.g. r1c1+r4c4+r7c7
(previously called "hopping diagonal" or "block symmetry")

6. Half-Turn (HT) - 2 cycle - e.g. r2c3+r8c7
(previously called "180 symmetry" or "180 degree rotational symmetry")

7. Quarter-Turn (QT) - 4 cycle - e.g. r2c3+r3c8+r8c7+r7c2
(previously called "90 symmetry" or "90 degree rotational symmetry")

8. Diagonal-Mirror (DM or \M or /M) - 2 cycle - e.g. r1c6+r6c1
(previously called "diagonal symmetry" or "diagonal reflection symmetry")

9. Row-Sticks/Column-Sticks (RS/CS) - 2 cycle - e.g. r4c1-r6c7
(previously called "horizontal/vertical sticks symmetry")

10. Full-Row/Full-Column (FR/FC) - 9 cycle - e.g. r1c147258369

11. Waving-Row/Waving-Column (WR/WC) - 9 cycle - e.g. r1c1+r2c4+r3c7+r1c2+r2c5+r3c8+r1c3+r2c6+r3c9
(previously called "sliding row/column symmetry")

12. Broken-Row/Broken-Column (BR/BC) - 9 cycle - e.g. r1c1+r4c4+r7c7+r1c2+r4c5+r7c8+r1c3+r4c6+r7c9

13. Full-Diagonal (FD or F\ or F/) - 9 cycle - e.g. r1c1+r4c4+r7c7+r2c2+r5c5+r8c8+r3c3+r6c6+r9c9

Each of these 13 groups represents a single group in Fraser/Red Ed's 26 groups which are listed by eleven in the 1st post of this thread. The other 13 groups are all combinations of them. I'll give it a full analysis pretty soon.

Meanwhile, more corrections () for eleven's table:
Code: Select all
`3. Boxes move triangular (B 159, 267, 368)BS         22        323.928   3    Y  Block symmetry, BludoBSR1       24            288   9    Y  equivalent to BS+RBSR1C1     23            162   9    Y  equivalent to BS+RC`

Likewise, the last 2 shouldn't be equivalence to BS+R/RC as they don't have BS. These are the "broken row/column" & "full diagonal" I mentioned above.

Code: Select all
`6. Sticks symmetriesBxCx      134    449.445.888   2    Y  Sticks symmetry, 9 cells fixedBxCxR     135         27.648   6    Y  equivalent to BxCx+RBxCxS     145         13.824   6    Y  equivalent to BxCx+SBxCxSR2   144          3.456   6    Y  equivalent to BxCx+SR2BxCxSR    142          6.480   6    Y  equivalent to BxCx+SRBxCxSR1R2 143          1.728   6    Y  equivalent to BxCx+SR1R2`

I suspect the last one should be BxCxSR1R3 instead?

Edited: "9. Row-Sticks/Column-Sticks (RS/CS)" (changed from "Sticks-Row/Sticks-Column (SR/SC)")
Last edited by udosuk on Mon Jan 05, 2009 8:25 am, edited 1 time in total.
udosuk

Posts: 2698
Joined: 17 July 2005

udosuk wrote:
Red Ed wrote:I was surprised that udosuk claimed to have found 2 new "basic" symmetries. If "basic" was a concept relating to solution grids then I could have helped you out. But if (as you seem to be saying) "basic" means "gives rise to a (specialised) solving technique" then I won't have anything to add!

I call a symmetry "basic" when it can't be expressed as a combination of 2 or more of other symmetries. The adjective "classical" currently describes the 7 or 8 (depending if you count the 2 rotational symmetries together) symmetries that we've been analysing and developing new techniques for.

None of the 3359232 validity-preserving transformations is "basic" by that definition. So: what do you mean by "symmetry"

(I'm not just playing with words: we need to get the terminology nailed-down.)
Red Ed

Posts: 633
Joined: 06 June 2005

udosuk wrote:At the moment we can't see any interesting puzzle/technique for the 2 new symmetries I mentioned. But there are 2 more of them which I call "broken row/column" & "full diagonal", hopefully they're more likely to produce interesting puzzles/techniques.

I gave both a try, but there are only trivial puzzles like those:
Code: Select all
` +-------+-------+-------+ | . 3 1 | 5 . 7 | 8 9 . | | . 6 4 | 8 . 1 | 2 3 . | | . 9 7 | 2 . 4 | 5 6 . | +-------+-------+-------+ | 9 1 . | . 4 2 | 6 . 8 | | 3 4 . | . 7 5 | 9 . 2 | | 6 7 . | . 1 8 | 3 . 5 | +-------+-------+-------+ | 7 . 9 | 1 2 . | . 5 3 | | 1 . 3 | 4 5 . | . 8 6 | | 4 . 6 | 7 8 . | . 2 9 | +-------+-------+-------+ +-------+-------+-------+ | 5 . . | . . 9 | . 8 3 | | . 8 . | 3 . . | 6 . 2 | | . . 2 | . 6 . | 5 9 . | +-------+-------+-------+ | 4 . 9 | 6 . . | . . 1 | | 3 7 . | . 9 . | 4 . . | | . 6 1 | . . 3 | . 7 . | +-------+-------+-------+ | 2 . . | 5 . 1 | 7 . . | | . 5 . | 4 8 . | . 1 . | | . . 8 | . 7 2 | . . 4 | +-------+-------+-------+`

Code: Select all
`BxCxSR1R2 143          1.728   6    Y  equivalent to BxCx+SR1R2`

I suspect the last one should be BxCxSR1R3 instead?
Yes, this is, what i have in my notes, thanks.

I will update the table after your analysis.
eleven

Posts: 2013
Joined: 10 February 2008

PreviousNext