The New Sudoku Players' Forum

[ronk]

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?

[JPF]

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

[ronk]

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

[JPF]

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

[udosuk]

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!

[Red Ed]

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!

[udosuk]

Excellent example! Thanks Red Ed!

[JPF]

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]

(e.g. row1,row2,row3 -> row2,row3,row1).

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

JPF

[udosuk]

(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)...

[ravel]

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)

[Red Ed]

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?

[ravel]

Does that go some way to answering your question?

At first glance, no.

[JPF]

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

[Red Ed]

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.