Sudoku Symmetry - Formalized

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

Postby ronk » Wed Jan 17, 2007 8:03 pm

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

Postby JPF » Wed Jan 17, 2007 11:30 pm

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.

This is just recapping what has already been said about automorphisms:(

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby ronk » Thu Jan 18, 2007 5:18 am

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

Postby JPF » Thu Jan 18, 2007 4:01 pm

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)
RefAD= row(7,9).row(4,6).row(1,3).col(7,9).col(4,6).col(1,3).stack(1,3).band(1,3).transp

Notations :
rot(90) : 90 rotation
transp : transposition
thing(i,j) : permutation of thing i with thing j
RefV : vertical reflection
RefAD : antidiagonal 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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby udosuk » Thu Jan 18, 2007 4:35 pm

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

Postby Red Ed » Thu Jan 18, 2007 4:47 pm

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

Postby udosuk » Thu Jan 18, 2007 5:12 pm

Excellent example! Thanks Red Ed!:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby JPF » Thu Jan 18, 2007 5:18 pm

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby JPF » Thu Jan 18, 2007 5:26 pm

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby udosuk » Thu Jan 18, 2007 5:37 pm

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

Postby ravel » Thu Jan 18, 2007 5:50 pm

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

Postby Red Ed » Thu Jan 18, 2007 8:51 pm

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.


Does that go some way to answering your question?
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby ravel » Thu Jan 18, 2007 11:54 pm

Red Ed wrote:Does that go some way to answering your question?
At first glance, no.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby JPF » Fri Jan 19, 2007 12:49 am

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby Red Ed » Fri Jan 19, 2007 8:26 am

ravel wrote:
Red Ed wrote:Does that go some way to answering your question?
At first glance, no.
ravel, why don't you try clarifying your question before I run out of patience with your dismissive attitude?

JPF, I'm not sure which class your example is in. If I had the time now, I'd use the GAP program to find the answer. As to finding fixed grids: the method I used is here. A convenient way of quickly ruling out the possibility of fixed grids for certain types of transformation is here.
Red Ed
 
Posts: 633
Joined: 06 June 2005

PreviousNext

Return to General