Hi, all!
Here is calculation of the number of possible 18-clue patterns, having double diagonal symmetries (main diagonal and antidiagonal).
- Code: Select all
Layout of sudoku puzzles, having double diagonal symmetries (main diagonal and antidiagonal symmetry axes).
Area "A" contains 1 cell.
Area "B" contains 8 cells.
Area "C" contains 16 cells.
B C C | C C C | C C B
. B C | C C C | C B .
. . B | C C C | B . .
------+-------+------
. . . | B C B | . . .
. . . | . A . | . . .
. . . | . . . | . . .
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
Let
a - number of clues in "A" area of solution grid (see the picture above),
b - number of clues in "B" area,
c - number of clues in "C" area. Then for each 18-clue pattern, having double diagonal symmetries, this equation is valid:
a + 2
b + 4
c = 18.
You can see that
a must be always zero to get even number on the left side of the equation.
c can be 1, 2, 3, 4. Let's consider these all possible 4 cases. We should calculate number of patterns for all cases and then to sum that numbers to obtain total number of possible patterns. Number of possible patterns in the "C" area is described by formula n!/(k!*(n-k)!), where n = 16 - total number of cells in the "C" area, k - number of clues in the "C" area. This number must be multiplied by number of placing clues in the "B" area - m!/(p!*(m-p)!), where m = 8 - total number of cells in the "B" area, p - number of clues in the "B" area.
1. Area "C" contains 1 clue. k = 1, p = 7; number of patterns = 16 x 8 = 128.
2. Area "C" contains 2 clues. k = 2, p = 5; number of patterns = 120 x 56 = 6720.
3. Area "C" contains 3 clues. k = 3, p = 3; number of patterns = 560 x 56 = 31360.
4. Area "C" contains 4 clues. k = 4, p = 1; number of patterns = 1820 x 8 = 14560.
Total number of 18-clue double diagonal symmetric patterns: 52,768.
To calculate (approximately) number of
essentially different 18-clue double diagonal symmetric patterns, I propose to count
pattern-independent "
true" automorhisms, i.e. automorphisms which are composed from pattern-independent ("true") basic VPTs such that each basic VPT
1. Belongs to common basic VPT family - bands/stacks permutations, permutations of rows (columns) in a band (stack), transposing.
2. Transform
any double diagonal symmetric pattern to another double diagonal symmetric pattern, i.e. preserves double diagonal symmetry.
3. Is not trivial, i.e. doesn't coincide with transformation "Do nothing" for given class of patterns.
I see such pattern-independent "true" basic VPTs:
1. Mirroring around vertical symmetry axis (stacks B147/B369 and columns c1/c3, c4/c6 and c7/c9 swapping) (2 ways).
2. Rows permutations within the upper band and correlated rows permutations within the lower band, plus correlated column permutations within B147 and B369 stacks (6 ways).
3. Rows r4/r6 permutations within the middle band and correlated column c4/c6 permutations within B258 stack (2 ways).
So, alone pattern has at most 2 x 6 x 2 = 24 "true" automorphisms. (Hope I am not wrong.)
To get rough estimate of lower bound of essentially different 18-clue double diagonal symmetric patterns, one can divide total number of pattern by number of "true" automorphisms. Lower bound of e-d patterns: 52768/24 = 2200 (approx.)
I think real number of essentially different patterns is substaintially higher. (Numbers 52,768 and 24 are too low to get correct estimate.)
Serg
[Edited. I refined automorphisms description and correct VPT #1 definition.]
