---

Automorphic solution grids

Automorphic solution grids are a subset of the isomorphic solution grids. The set of isomorphic solution grids for a particular solution grid is formed by choosing the unique permutations of that solution grid from all the possible permutations (renumbering and geometric) for that grid. With relatively rare probability, sometimes all the possible permutations for a grid creates duplicate permutations. A permutation which has duplicates is an automorphic solution grid.

Contents 1 The Importance of Automorphic Puzzles 1.1 Renumbering Permutations 1.2 Geometric Permutations 1.3 Possible Permutations 2 An Example of an Automorphic Solution Grid 3 External links

The Importance of Automorphic Puzzles

The existence of automorphic solution grids and the nature of automorphic transformations is interesting because it helps explain one of the mysteries of Sudoku puzzles.

 6,671,248,172,291,458,990,080  5,472,730,538 * 3,359,232 * 362,880
 6,670,903,752,021,072,936,960  exact number of Sudoku solution grids
 -----------------------------
       344,420,270,386,053,120  grid deficiency 

                 5,472,730,538  exact number of unique Sudoku solution grids
                     3,359,232  possible geometric permutations of solution grid
                       362,880  number of ways to renumber a grid 

The really interesting point in the above table is that if every solution grid had all the possible geometric permutations and renumbering permutations then there should be exactly 6,671,248,172,291,458,990,080 possible solution grids. But there is actually a deficiency of 344,420,270,386,053,120 grids. The reason that there is a deficiency of grids is due to the fact that some of the permutations create automorphic grids. Automorphic grids are the permutations which have duplicates.

It should be pointed out that most of the unique solution grids ( however we canonicalize them) do not have automorphs.

Renumbering Permutations

Renumbering Permutations are simply the permutations that swap one digit for another. For example swapping all the 9s for 1s, and all 1s for 9s would be one of the 9! possibilities for renumbering. If renumbering were he only possible permutation then all 9! renumbering permutations would be unique.

Geometric Permutations

The sufficient list of the possible set of geometric permutations is:

1. Permute the three towers;
2. Permute the three floors;
3. Permute the three columns within a tower;
4. Permute the three rows within a floor;
5. A transposition = diagonal reflection.

The list above is sufficient since other symmetries, such as rotation, can be created from applying a combination of the above operations. Consider a simple 3x3 block below.

 123        987
 456        654
 789        321
Start    Rotate 180
          degrees

 123        789          987         
 456        456          654
 789        123          321
Start    Swap floors   Swap Towers  
            1&3          1&3

Possible Permutations

The possible permutations is any combination of the renumbering and geometric operations.

  362,880 x 3,359,232 = 1,218,998,108,160

Note that the most permutations that a particular solution grid can have is 1,218,998,108,160.

An Example of an Automorphic Solution Grid

Let's:

1. Label a rotation of 180 degrees as the transformation (isomorphism) t of the grid G. So rotating the grid will creating the resulting grid is G^t.
2. Label renumbering a grid with the permutation (123456789) -> (987654321) as the transformation (isomorphism) u of the grid G. So this particular renumbering of the grid will creating the resulting grid is G^u.

A grid G is automorphic over this combination of transformations if:

G =  ( Gt )u 

For example, the grid G :

    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
              G  

rotation by 180 degrees :

    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
           Gt 

relabeling with the permutation (123456789) -> (987654321)

    4 1 3 | 5 7 2 | 6 8 9                 4 1 3 | 5 7 2 | 6 8 9
    7 6 2 | 3 8 9 | 5 1 4                 7 6 2 | 3 8 9 | 5 1 4
    9 5 8 | 4 6 1 | 3 7 2                 9 5 8 | 4 6 1 | 3 7 2
   -------+-------+-------                -------+-------+-------
    3 4 6 | 7 1 8 | 9 2 5                 3 4 6 | 7 1 8 | 9 2 5
    2 7 9 | 6 5 4 | 1 3 8       =         2 7 9 | 6 5 4 | 1 3 8   
    5 8 1 | 2 9 3 | 4 6 7                 5 8 1 | 2 9 3 | 4 6 7
   -------+-------+-------                -------+-------+-------
    8 3 7 | 9 4 6 | 2 5 1                 8 3 7 | 9 4 6 | 2 5 1
    6 9 5 | 1 2 7 | 8 4 3                 6 9 5 | 1 2 7 | 8 4 3
    1 2 4 | 8 3 5 | 7 9 6                 1 2 4 | 8 3 5 | 7 9 6
           ( Gt )u   =                               G

So G, is an automorphic solution grid.

External links

• [40482] Post by JPF in The New Sudoku Players' Forum

This page was last modified 23:41, 8 October 2010.  

---