127.0.0.1: Created page with "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 uni..."

2021-10-26T19:19:44Z

Created page with "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 uni..."

New page

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.

== 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:

# Permute the three towers;
# Permute the three floors;
# Permute the three columns within a tower;
# Permute the three rows within a floor;
# 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:

# 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'''.
# 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 = ( G'''t''' )'''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
G'''t'''

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
( G'''t''' )'''u''' = G

So G, is an automorphic solution grid.

== External links ==
*[[http://forum.enjoysudoku.com/post40482.html#p40482 40482]] Post by JPF in ''The New Sudoku Players' Forum''

{{incomplete}}

Automorphic solution grids - Revision history

127.0.0.1: Created page with "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 uni..."