About Red Ed's Sudoku symmetry group

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

Postby udosuk » Sat Jan 03, 2009 1:51 am

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.:idea:

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

Postby Red Ed » Sat Jan 03, 2009 1:53 am

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));
3
gap>

Unravelling those will be a nice challenge for someone:)
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby ronk » Sat Jan 03, 2009 2:03 am

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

Postby eleven » Sat Jan 03, 2009 9:03 am

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: 3149
Joined: 10 February 2008

Postby JPF » Sat Jan 03, 2009 11:29 am

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 25
62 80 71 44 35 53 17 08 26
63 81 72 45 36 54 18 09 27
57 75 66 39 30 48 12 03 21
55 73 64 37 28 46 10 01 19
56 74 65 38 29 47 11 02 20
58 76 67 40 31 49 13 04 22
59 77 68 41 32 50 14 05 23
60 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: 6139
Joined: 06 December 2005
Location: Paris, France

Postby StrmCkr » Sat Jan 03, 2009 5:38 pm

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.
stormdoku
User avatar
StrmCkr
 
Posts: 1430
Joined: 05 September 2006

Postby eleven » Sun Jan 04, 2009 12:57 am

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 ?:D
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: 3149
Joined: 10 February 2008

Re: About Red Ed's Sudoku symmetry group

Postby udosuk » Sun Jan 04, 2009 2:02 am

eleven wrote:
Code: Select all
M           C         N        L    S

2. Boxes move in bands
S          25     14.837.760   3    N  Band symmetry
SR1        28      2.085.120   3    Y  Gludo
SR1R2      30        294.912   3    Y  Gludo
SR         32      6.342.480   3    Y  Gludo
SC1        27          5.184   9    N  equivalent to S+C
SR1C1      26          2.592   9    Y  equivalent to SR1+C
SR1R2C1    29          1.296   9    Y  equivalent to SR1R2+C
SRC1       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.:idea:

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:D ). 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

Postby eleven » Sun Jan 04, 2009 2:48 am

Thanks, you are right. i was too little interested in the 9-cycles to look at more than one column.
eleven
 
Posts: 3149
Joined: 10 February 2008

Postby Red Ed » Sun Jan 04, 2009 4:58 am

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

Postby eleven » Sun Jan 04, 2009 9:50 am

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: 3149
Joined: 10 February 2008

Postby Red Ed » Sun Jan 04, 2009 10:11 am

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!:D
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby udosuk » Sun Jan 04, 2009 1:08 pm

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!:D

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.:idea:



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, Bludo
BSR1       24            288   9    Y  equivalent to BS+R
BSR1C1     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 symmetries
BxCx      134    449.445.888   2    Y  Sticks symmetry, 9 cells fixed
BxCxR     135         27.648   6    Y  equivalent to BxCx+R
BxCxS     145         13.824   6    Y  equivalent to BxCx+S
BxCxSR2   144          3.456   6    Y  equivalent to BxCx+SR2
BxCxSR    142          6.480   6    Y  equivalent to BxCx+SR
BxCxSR1R2 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

Postby Red Ed » Sun Jan 04, 2009 6:25 pm

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!:D

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

Postby eleven » Mon Jan 05, 2009 2:42 am

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: 3149
Joined: 10 February 2008

PreviousNext

Return to General