The New Sudoku Players' Forum

[Mathimagics]

A clarification is needed:

Now look at this result of the Burnside Lemma process expanded to process each FSPT transformation individually

"Burnside Lemma process" is a horrible mangling of terms, for which I apologise. It should really be Automorphism Enumeration process.

How did Russell & Jarvis count "essentially different" Sudoku grids? They simply counted all Sudoku autorphisms (aka "invariants") under the "Sudoku symmetry group" (which is same as our VPT group here), and divided this count by the order of the group.

Since Burnside's Lemma is applicable for this group, they only needed to count automorphisms for 1 transformation in each conjugacy class. In other words, the automorphism count will be exactly the same for any transformation in the same class.

The Automorphism Enumeration process is just the counting of individual grid/pattern automorphisms for a given transformation (T). If we test every T in the group, that would be "Brute Force", if we test only one T from each conjugacy class, that's "Burnside".

[Serg]

Hi, Mathimagics!

The Automorphism Enumeration process is just the counting of individual grid/pattern automorphisms for a given transformation (T). If we test every T in the group, that would be "Brute Force", if we test only one T from each conjugacy class, that's "Burnside".

Burnside's Lemma says, that for given transformation group acting on a set of elements number of essentially different elements equals to average number of elements fixed by group's transformation (done over all transformations).

Conjugacy classes are not mentioned in Burnside's Lemma. Conjugacy classes are frequently used while calculating average number of elements fixed by group's transformation, but it's not mandatory. So, calculations by Burnside's Lemma admits "counting of individual grid/pattern automorphisms" for every transformation in the group. On the other hand, using conjugacy classes can still lead to "brute force" search, as Red Ed wrote about his 275 conjugacy classes analysis.

Serg

[Serg]

Hi, Mathimagics!

Ok, let's consider DD3 patterns. These are patterns with double-diagonal symmetry in the 3x3 corners.

It seems that only these cases give rise to the orbit connection problem. Now look at this result of the Burnside Lemma process expanded to process each FSPT transformation individually:

Code: Select all

  --------------------------------
  CC        NINV    DD3?  N      Y     
  --------------------------------
  C[2,1]    2048       1536    512
  C[2,2]    2048       1536    512   
  C[2,3]    2048          0   2048

  C[3,1]     128          0    128
  C[3,2]     128          0    128
  --------------------------------
  NEDP      6528     NEDP*    6016
  --------------------------------


NINV is # of invariant patterns for each transformation.

DD3? indicates how many of these invariant patterns have DD3 property.

NEDP (# of FS-different grids) is (32768 + 3 x 2048 + 2 x 128) / 6 = 6528.

Interestingly, ALL invariants for 3 of the 5 transformations have DD3 property, but for the first two transformations only one in 4 have DD3 property.

And if we redo the NEDP calculation counting ONLY the DD3 invariants we get the desired result NEDP* (# of essentially different patterns) as (32768 + (2048 + 2 x 512) + 2 x 128) / 6 = 6016.

Unfortunately I can not find an explanation of your method of 6016 calculation. Maybe your intuition points right way ...
The main thing that confuses me in your calculations - highlighting the transformation "Swap r1/r3 + ..." among all permitted pairwise swaps ("Swap r1/r2 +" and "Swap r2/r3 +"). Property of "Swap r1/r3 +" should not differ from others pairwise swaps. Deeper thinking is necessary ...

Serg

[eleven]

If you have one of these patterns in box 1, and mirrored in boxes 379,

Code: Select all

  x . .   . . x        x . .   . . x       . x x   x x .       x x .   . x x
  . . .   . . .        . x .   . x .       x x x   x x x       x . x   x . x
  . . x   x . .        . . x   x . .       x x .   . x x       . x x   x x .

and one of these in box 2 and mirrored in boxes 468,

Code: Select all

  . . .   . . .   x . x   . x .   x . x   . x .    x x x   x x x
  . . .   . x .   . . .   x . x   . x .   x x x    x . x   x x x
  . . .   . . .   x . x   . x .   x . x   . x .    x x x   x x x

and one of all in the center box, you have a fully symmetric pattern.

If you swap r13 and r79, you get another fs pattern (with boxes 1379 changed to their pair), which is s-equivalent, but not fs-equivalent.
4 of the first boxes, 8 of the next and 16 for the center can be chosen to get non s-equivalent combinations.
So i know now, how the 512 patterns look like.

[Serg]

Hi, eleven!

If you swap r13 and r79, you get another fs pattern (with boxes 1379 changed to their pair), which is s-equivalent, but not fs-equivalent.
4 of the first boxes, 8 of the next and 16 for the center can be chosen to get non s-equivalent combinations.
So i know now, how the 512 patterns look like.

What can you say about these fully symmetrical patterns:

Code: Select all

        #5

x . . . . . . . x
. x . x x x . x .
. . x . . . x . .
. x . . . . . x .
. x . . . . . x .
. x . . . . . x .
. . x . . . x . .
. x . x x x . x .
x . . . . . . . x

        #6

. . . . . . . . .
. x . . . . . x .
. . x . . . x . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . x . . . x . .
. x . . . . . x .
. . . . . . . . .


Pattern #5 turns into another fully symmetrical pattern by swapping r1/r3 and r7/r9 rows, pattern #6 turns into another fully symmetrical pattern by swapping r2/r3 and r7/r8 rows. If I am not mistaken, both patterns are absent in your list.

Serg

[eleven]

I think, pattern #6 is fs-equivalent to the first box 1 pattern.
But you are right about #5. Not only fully symmetric patterns can be in boxes B2468, but all, for which the pattern does not change by the swap (16).

[Added:] The other 8 patterns, which can be selected for box 2:

Code: Select all

  . x .    x x x    . x .   x x x   . . .    x . x    . . .    x . x   
  . . .    . . .    . x .   . x .   x . x    x . x    x x x    x x x   
  . x .    x x x    . x .   x x x   . . .    x . x    . . .    x . x


[eleven]

Well, you can do the same for the center box. Select one of the 4 patterns, one of the 16 for box 2 and any fs-symmetric one for box 1. Then change rows 46.
This gives a lot more.

[Mathimagics]

Bearing in mind Serg's gentle (but absolutely factual) insistence regarding the true nature of Burnside's Lemma, I finally decided it was worth switching from Automorphism Enumeration to actual orbit counting.

Again, Serg is correct when he stated that:

When we count non-equivalent in some sense or different in some sense puzzles/grids/patterns for given transformations group, we are counting orbits.

Using the only available enumeration of individual orbits (for the case of 20 clues, given by Gordon Foyle here), I was able to determine that we can connect orbits if, and only if, for some image in the orbit:

• the 3x3 corner pattern has DD3 symmetry

• the 3x3 corner pattern does not have full symmetry, ie its horizontal reflection is different

So we need to distingish between non-reflecting cases (DD3 type 1), and fully-symmetric cases (DD3 type 2). The DD3 type 1 patterns are those box 1 patterns given above by eleven above, the DD3 type 2 patterns are his box 2 patterns.

When I run the orbit counter with this orbit-joining tweak, I get results that correspond exactly with JPF's table.

My results:

Hidden Text: Show

[/code]
Clues Patterns Orbits
----------------------
0 1 1
1 1 1
4 8 4
5 8 4
8 34 10
9 34 10
12 104 24
13 104 24
16 253 52
17 253 52
20 512 98
21 512 98
24 888 165
25 888 165
28 1344 246
29 1344 246
32 1794 323
33 1794 323
36 2128 380
37 2128 380
40 2252 402
41 2252 402
----------------------
32768 6016
[/code]

I guess what this shows is that we can arrive at the desired result without having to check orbits under every VPT transformation, we only need to do it over FSPT, and check for explicit orbit connections (which the evidence suggests are possible only via "swap r1,r3" transformations on the applicable orbit images), so that's quite a saving.

I am thinking about how this approach might be applied to the SudokuP problem.

PS: the reason I say "only the 20-clues" case is available is that the link to Gordon Royle's full listing of S-equivalence classes no longer works, and I can't track it down. But I'm confident that they will all match up.

[Mathimagics]

I am thinking about how this approach might be applied to the SudokuP problem.

And the answer is, with great difficulty!

The trouble with orbit counting is that it essentially requires the partitioning of the entire grid set into equivalence classes, and the sheer number of grids is prohibitively large.

[Serg]

Hi, Mathimagics!

I am thinking about how this approach might be applied to the SudokuP problem.

...
The trouble with orbit counting is that it essentially requires the partitioning of the entire grid set into equivalence classes, and the sheer number of grids is prohibitively large.

And this is why I opened this thread. The task of fs-patterns enumeration can be solved by checking all 3359232 images of every fs-pattern, because total number of checked patterns is relatively small. But this approach doesn't work in SudokuP grids enumeration - the number of such grids is too large. So, I am trying to find some mathematical approach to enumeration essentially different fs-patterns without their direct counting. I feel the same approach can be used for SudokuP grids enumeration.

Serg