We can provide a good estimate of NUP = # of

essentially different SudokuP grids (using the classical definition) by simply dividing the known figure for Sudoku grids by the known ratio of Sudoku to SudokuP grids:

- e-d Sudoku grids = 5,472,730,538

- P-ratio = approx 33171.2253

- e-d SudokuP grids = 164,984.2744

Another way is to use the Russell & Jarvis method, counting for each class representative the number of invariant grids with SudokuP property:

- Code: Select all
` * indicates those S-classes with no P-class match (and PA > 0)`

======================================================

Class Size(N) Invariants (A) P-Inv (PA)

======================================================

1 1 1,838,322,242,069,299 554,191,840,696

7 96 21,233,664 24,192 *

8 16 107,495,424 829,440

9 192 4,204,224 2,304 *

10 64 2,508,084 82,204

22 5184 323,928 82,204

23 20736 162 12 *

24 20736 288 144 *

25 144 14,837,760 1,545,472

26 1728 2,592 12 *

27 288 5,184 144 *

28 864 2,085,120 103,680 *

29 3456 1,296 0

30 1728 294,912 12,960 *

31 2304 648 72 *

32 1152 6,342,480 2,773,764 *

37 1296 30,258,432 17,052

40 10368 1,854 48

43 93312 288 126

79 2916 155,492,352 192,384

86 69984 13,056 780

134 972 449,445,888 26,410,752

135 3888 27,648 128

142 31104 6,480 0

143 15552 1,728 0

144 15552 3,456 0

145 7776 13,824 0

Summing (N * A) for all classes and dividing by 3,359,232 gives NU = 5,472,730,538.

Summing (N * PA) and dividing by 3,359,232 gives NUP = approx 173,996.4155. This is not an integer, confirming

Serg's point about non-applicability of Burnside's Lemma, due to intersecting orbits, also that this value over-estimates the true figure.

To arrive at an exact number we can use these results, but we have to expand each class, ie for each invariant P-grid in class C there are N(C) "relatives", we can get these by applying the appropriate conjugation transformations and test these. A total of 4,631,625,880 grids need to be tested in this way, so it's but a slight improvement on brute-force over all 554,191,840,696 P-grids (we reduce the problem by a factor of 120).

Still, it should give a result against which other approaches can be verified.

A note on timings: the PA enumeration was done in 4 parallel batches, the longest batch time was 15 minutes. This was all done in VB6 so I would imagine a C version could be made that runs faster, as we don't have pointers in VB6.