Sudoku Symmetry - Formalized

Everything about Sudoku that doesn't fit in one of the other sections
Red Ed wrote:This is a nice automorphic grid:
Code: Select all
` . 1 . | 5 . . | . . .  . . 2 | 3 . . | . . 4  . . 8 | . . . | 3 7 . -------+-------+------ . . . | . 1 . | . 2 5  . . . | 6 . 4 | . . .  5 8 . | . 9 . | . . . -------+-------+------ . 3 7 | . . . | 2 . .  6 . . | . . 7 | 8 . .  . . . | . . 5 | . 9 .  `
If you rotate it by 180 degrees and map digit d -> 10-d then you get back where you started.

That certainly helps, but what are the permissible types of transformations? Is there a limit on the quantity of transformation steps? And must the digit mapping, if any, follow a simple formula?

IOW without using the statistics of Sudoku, would someone please post a defintion of an automorphic grid?
ronk
2012 Supporter

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

ronk wrote:IOW without using the statistics of Sudoku, would someone please post a defintion of an automorphic grid?

You may have a look here .

Ed Russell & Frazer Jarvis wrote:
The complete list of operations that we can perform is:
1. Relabel (i.e., permute) the 9 digits;
2. Permute the three stacks;
3. Permute the three bands;
4. Permute the three columns within a stack;
5. Permute the three rows within a band;
6. Any reflection or rotation.

and of course, any combinations of these operations.
Let's call such a combination a transformation (isomorphism) t of the grid G.
The resulting grid is tG.

A grid G is automorphic if it exists a transformation t (different from the identity) such that tG=G.
For example, the grid G :
Code: Select all
` 4 1 3 | 5 7 2 | 6 8 9 7 6 2 | 3 8 9 | 5 1 4 9 5 8 | 4 6 1 | 3 7 2-------+-------+------- 3 4 6 | 7 1 8 | 9 2 5 2 7 9 | 6 5 4 | 1 3 8 5 8 1 | 2 9 3 | 4 6 7-------+-------+------- 8 3 7 | 9 4 6 | 2 5 1 6 9 5 | 1 2 7 | 8 4 3 1 2 4 | 8 3 5 | 7 9 6 `

rotation by 180 degrees :
Code: Select all
` 6 9 7 | 5 3 8 | 4 2 1 3 4 8 | 7 2 1 | 5 9 6 1 5 2 | 6 4 9 | 7 3 8-------+-------+------- 7 6 4 | 3 9 2 | 1 8 5 8 3 1 | 4 5 6 | 9 7 2 5 2 9 | 8 1 7 | 6 4 3-------+-------+------- 2 7 3 | 1 6 4 | 8 5 9 4 1 5 | 9 8 3 | 2 6 7 9 8 6 | 2 7 5 | 3 1 4`

relabelling with the permutation (123456789) -> (987654321)
Code: Select all
` 4 1 3 | 5 7 2 | 6 8 9 7 6 2 | 3 8 9 | 5 1 4 9 5 8 | 4 6 1 | 3 7 2-------+-------+------- 3 4 6 | 7 1 8 | 9 2 5 2 7 9 | 6 5 4 | 1 3 8 5 8 1 | 2 9 3 | 4 6 7-------+-------+------- 8 3 7 | 9 4 6 | 2 5 1 6 9 5 | 1 2 7 | 8 4 3 1 2 4 | 8 3 5 | 7 9 6`

which is G,
is automorphic.

JPF
JPF
2017 Supporter

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

JPF wrote:Ed Russell & Frazer Jarvis wrote:
The complete list of operations that we can perform is:
1. Relabel (i.e., permute) the 9 digits;
2. Permute the three stacks;
3. Permute the three bands;
4. Permute the three columns within a stack;
5. Permute the three rows within a band;
6. Any reflection or rotation.

and of course, any combinations of these operations.
Let's call such a combination a transformation (isomorphism) t of the grid G.
The resulting grid is tG.

A grid G is automorphic if it exists a transformation t (different from the identity) such that tG=G.

JPF, thanks ... that's quite straightforward. Is there an equally simple statement to be sure one hasn't constructed a combination of operations that result in an identity transformation?

[edit:No answer required. I just remembered that reflections and rotations can be expressed as a re-ordering of the rows and columns. So it should be rather easy to keep track of the overall re-ordering of the rows and columns due to operations 2 through 6 above. If both the rows and colums are simply scrambled back to their original order, then the transformation was an identity positional transformation.

Keeping track of value transformations is even easier.

For a little fun, I'll set up an Excel spreadsheet as a test bed for this.]

Thanks again, Ron
ronk
2012 Supporter

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

ronk wrote:
JPF wrote:Ed Russell & Frazer Jarvis wrote:
The complete list of operations that we can perform is:
1. Relabel (i.e., permute) the 9 digits;
2. Permute the three stacks;
3. Permute the three bands;
4. Permute the three columns within a stack;
5. Permute the three rows within a band;
6. Any reflection or rotation.

and of course, any combinations of these operations.
Let's call such a combination a transformation (isomorphism) t of the grid G.
The resulting grid is tG.

Is there an equally simple statement to be sure one hasn't constructed a combination of operations that result in an identity transformation?

[edit:No answer required. I just remembered...]

Too late !

At least, for somebody else :
Actually, line 6 can be limited to : transposition = diagonal reflection.

Any reflections or rotations is a combination of some of these operations : permutations 2,3,4,5, transposition.

For example :
Let's take a 90-rotation.
Initial grid G :
Code: Select all
`  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81`

Final grid G'
Code: Select all
` 73 64 55 46 37 28 19 10  1 74 65 56 47 38 29 20 11  2 75 66 57 48 39 30 21 12  3 76 67 58 49 40 31 22 13  4 77 68 59 50 41 32 23 14  5 78 69 60 51 42 33 24 15  6 79 70 61 52 43 34 25 16  7 80 71 62 53 44 35 26 17  8 81 72 63 54 45 36 27 18  9`

By using these succesive operations (see the notations below):
• transp
• stack(1,3)
• col(1,3)
• col(4,6)
• col(7,9)
we get G'.

which is written :
rot(90) = col(7,9).col(4,6).col(1,3).stack(1,3).transp

As far as reflections are concern, here are some possible breakdowns (which are not unique) :
RefV = col(7,9).col(4,6).col(1,3).stack(1,3)

Notations :
rot(90) : 90 rotation
transp : transposition
thing(i,j) : permutation of thing i with thing j
RefV : vertical reflection

Consequence :
Every (isomorphic) transformation on a grid G is a combination of the following operations :

1. Relabel (i.e., permute) the 9 digits;
2. Permute the three stacks;
3. Permute the three bands;
4. Permute the three columns within a stack;
5. Permute the three rows within a band;
6. transposition

which gives a number of possible transformations equal to 9!x 6^8 x 2 = 362880 x 3359232 =1,218,998,108,160

JPF
Last edited by JPF on Thu Jan 18, 2007 1:14 pm, edited 1 time in total.
JPF
2017 Supporter

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

Good explanation JPF...

Just curious, what does "lig" stand for, and why didn't you use "row" instead?

So, every transformation can be expressed as a combination of at most () 10 operations, one each from 1,2,3,6 and three each from 4,5:

1. Relabel (i.e., permute) the 9 digits;
2. Permute the three stacks;
3. Permute the three bands;
4. Permute the three columns within a stack;
5. Permute the three rows within a band;
6. transposition

Now, if I haven't mistaken, any transformation involving relabelling will definitely not be an identity one... And all automorphic transformation must involve some relabelling? Or could anyone show me a pure positional automorphic transformation (i.e. only operations 2-5 involved)? Thanks!
udosuk

Posts: 2698
Joined: 17 July 2005

An example is shown below. Cycle the stacks left by one place (i.e. replace stack1,stack2,stack3 by stack2,stack3,stack1) and cycle the contents of each band up by one place (e.g. row1,row2,row3 -> row2,row3,row1). The grid is unchanged.
Code: Select all
` 1 2 3 7 8 9 4 5 6 4 5 6 1 2 3 7 8 9 7 8 9 4 5 6 1 2 3 9 1 2 6 7 5 8 3 4 8 3 4 9 1 2 6 7 5 6 7 5 8 3 4 9 1 2 2 9 1 5 6 7 3 4 8 3 4 8 2 9 1 5 6 7 5 6 7 3 4 8 2 9 1`
Hopefully that doesn't confuse anyone's understanding of automorphisms!
Red Ed

Posts: 633
Joined: 06 June 2005

Excellent example! Thanks Red Ed!
udosuk

Posts: 2698
Joined: 17 July 2005

udosuk wrote:Good explanation JPF...
Just curious, what does "lig" stand for, and why didn't you use "row" instead?
Thanks.
lig stands for ... ligne... which is a french row.
Edited.

JPF
JPF
2017 Supporter

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

Red Ed wrote:(e.g. row1,row2,row3 -> row2,row3,row1).

I don't want to nitpick but isn't :
row1,row2,row3 -> row3,row1,row2 ?

JPF
JPF
2017 Supporter

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

JPF wrote:
Red Ed wrote:(e.g. row1,row2,row3 -> row2,row3,row1).

I don't want to nitpick but isn't :
row1,row2,row3 -> row3,row1,row2 ?

I suppose what Red Ed meant was: "r1 is replaced by r2, r2 is replaced by r3, r3 is replaced by r1"...

And a simple way to represent this operation could be r(231)...
udosuk

Posts: 2698
Joined: 17 July 2005

To repeat my question.
Are there other puzzles with an automorphism than those that are isomorphic to puzzles, which have
- 180 degree rotational symmetry (2-folded)
- diagonal symmetry (2-folded)
- chunk symmetry (like Red Ed's sample, each stack or band transformed to the next, 3-folded)
- box symmetry (b1->b6->b8, b2->b4->b9, b3->b5->b7, 3-folded)
- 90 degree rotational symmetry (4-folded)
- combinations of them (e.g. double diagonal - then also rotational - plus box symmetry)
ravel

Posts: 998
Joined: 21 February 2006

ravel -- all the transformations you seek are available, up to conjugacy, here.

It was Frazer's idea to use conjugacy classes. It saves a lot of work in the count of the number of essentially-different solution grids, as I will now attempt to explain.

Suppose solution grid G is fixed by validity-preserving cell permutation f (some combination of ops 2-6 above), plus probably some digit relabelling. I'll write G ~ fG as short-hand (so ~f means fixed, up to relabelling, by f). Now pick any cell permutation x made up of ops 2-6 and write x' to mean x-inverse. Some arithmetic ...
• Given G ~ fG
• Then xG ~ xfG (apply x on the left to both sides)
• So xG ~ xfx'xG (simply noting that xfx'x = xf)
... which means the grid xG is fixed, up to relabelling, by xfx'.

There are at least two ways to make use of this:
• If you are told that some transformation f has fixed grids, then you know that all conjugates, xfx', also have (the same number of) fixed grids. This fact is what "saves a lot of work" as mentioned above.
• If you know that G is fixed (up to relabelling) by f, then any isomorph xG is fixed (up to relabelling) by xfx'.
Soooo.... to get back to your question. Let's have a look at conjugacy class 43 on that web page. The representative element, call it f, listed there is a product of the following cycles:
• (1 55 61 34 31 4) which means: cell 1 (r1c1) goes to cell 55 (r7c1) goes to r7c7 goes to r4c7 goes to r4c4 goes to r1c4
• (2 64 62 43 32 13)
• (3 73 63 52 33 22)
• (5 10 56 70 35 40)
• (6 19 57 79 36 49)
• (7 28 58)
• (8 37 59 16 29 67)
• (9 46 60 25 30 76)
• (11 65 71 44 41 14)
• (12 74 72 53 42 23)
• (15 20 66 80 45 50)
• (17 38 68)
• (18 47 69 26 39 77)
• (21 75 81 54 51 24)
• (27 48 78)
At first this looks nonsensical! But with a little perserverence, you can see that what's really happening is:
• the contents of stacks 1,2,3 are moved into stacks 3,1,2 respectively
• (the order of columns within stacks is left unchanged)
• then the grid is tranposed
... which is clearly a composition of ops 2-6 after all. If you computed random conjugates, xfx', of this transformation then all 93312 (see the web page) conjugates would have the same cycle structure and basically the same "shape", i.e. band/stack cycling of some sort plus transposition.

Red Ed

Posts: 633
Joined: 06 June 2005

At first glance, no.
ravel

Posts: 998
Joined: 21 February 2006

Let's take an example :

The transformation f :
Code: Select all
` 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1`

In which class is f among the 275 ?

If the number of grids (equivalent up to relabelling) fixed by f is > 0, how can we find one such grid ?

JPF
JPF
2017 Supporter

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

ravel wrote: