I propose to discuss symmetrical patterns enumeration problem.
The first time I encountered this problem in the thread Symmetric 18s. In this thread 18-clue sudoku puzzles, having vertical symmetry, were discussed, and essentially different clues configurations (i.e. patterns) were collected. I tried to calculate mathematically number of essentially different 18-clue symmetrical patterns, but couldn't do it. The problem was decided by "brute force" method, by generation of all possible 18-clue symmetrical patterns and filtered out isomorphs.
Further in the cited thread 18-clue double diagonal symmetrical patterns were investigated (see Afmob's post in the thread Symmetric 18s). Again, there were no methods to compute exact number of such patterns. The problem was solved by generation of all possible patterns.
The next case - enumeration of fully symmetrical patterns - the thread "Fully symmetrical puzzles" (see, for example, gfroyle's post here and JPF's post here). The problem was solved by generation of all possible patterns (number of such patterns is 2^15 only) and applying all possible isomorphic transformations.
My goal is to find mathematical method of symmetrical patterns enumeration, to find mathematical base (like conjugacy classes technique, Burnside's Lemma, etc.), substantially reducing complexity of original problem. Such a method would make it possible to obtain exact number very fast for the cases cited above and even enumerate patterns/grids in more complicated cases, such as enumeration of essentially different P-Sudoku (aka "Sudoku DG") solution grids, etc.
Let's consider a problem of enumerating fully symmetrical patterns, as an example.
Definition
Pattern is 9x9 binary matrix (i.e. containing "0" or "1" in each cell). Cell containg "1" means that sudoku puzzle, constructed on the base of this pattern must have clue in this cell. Cell containg "0" means that sudoku puzzle, constructed on the base of this pattern must not have clue in this cell. So, pattern defines a family of sudoku puzzles. These puzzles may have equal or different digits in the same cells, but all these puzzles have the same structure (the same pattern of clues). Here is an example of (fully symmetrical) pattern.
- Code: Select all
1 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 1 0
0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0
0 1 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 1
Very often cells containing clues are marked by "x", cells not containing clues are marked by ".".
Total number of "all different" fully symmetrical patterns (i.e. patterns having vertical, horizontal, diagonal and antidiagonal symmetries simultaneously) is 2^15 or 32768. But how many are there essentially different patterns?
It is rather evident, that there are 6 "universal" isomorphic transformations, which transform any fully symmetrical pattern to another fully symmetrical pattern, all transformation having similar type: permutation of rows in B123 band AND the same permutation of columns in B147 stack AND "mirrored" permutation of rows in B789 band AND the same "mirrored" permutation of columns in B369 stack. "Mirrored" permutation means that r1/r2 permutation must be supplemented by r8/r9 permutation, left cyclical shift of columns c1-c3 must be supplemented by right cyclical shift of columns c7-c9, etc.
Besides those "universal" isomorphic transformations, there are "non-universal" transformations, which transform some fully symmetrical patterns to other fully symmetrical patterns, but drop fully symmetry for certain fully symmetrical patterns.
It looks like JPF was the first, who counted essentially different fully symmetrical patterns. It turns out, there are 6016 such patterns. Later this number was confirmed and there is no doubt that this is true.
So, I invite everyone to develop mathematical approach for enumeration of essentially different fully symmetrical patterns.
Serg
