The New Sudoku Players' Forum

[Mathimagics]

Hi eleven,

I wonder if you can help me with a problem. My automorphism enumerator (in normal Sudoku mode) produces 317 cases for Ed's class 24. The table in Russell & Jarvis says there are only 288.

I have checked that there are no duplicates and that every record seems to satisfy satisfy T(X) => X for the corresponding T in Ed's table.

So I'm more than a little mystified by this. Are you able to verify them programmatically?

Solutions-CC24.txt

(25.69 KiB) Downloaded 225 times

[StrmCkr]

did you check for transformations that are identical? but uses different sets.

[Mathimagics]

Ok, I found it ...

When testing tells us white is black, it's time to test the tester!

I had forgotten to set the transformation in the verification routine, so it passed everything and anything ...

When set correctly, it failed exactly 29 records.

[Mathimagics]

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.

[eleven]

Nice to have some numbers - and you got them very fast.

But what is the (exact) number of P-equivalent PSudokus (where you can apply Burnside's Lemma)?

And isn't it possible to calculate the counts of SudokuP puzzles, which are essentially different for P-equivalence, but not for S-equivalence, from the numbers of invariants of SudokuP grids in the corresponding Sudoku and SudokuP classes ? (I don't know)

[Mathimagics]

what is the (exact) number of P-equivalent PSudokus (where you can apply Burnside's Lemma)?

Urrgh! Once I had identified and fixed the automorphism enumerator bug, I reran the P-equivalence job and to my horror the results still didn't balance, so there must be some problem with P-equivalence, but not with S-equivalence, which gets the numbers right in all 26 classes. So I still have a P-bug!

Since Serg convinced me S-equivalence was more interesting (and I now agree), I decided to pursue that and leave the P-equivalence problem till later.

And isn't it possible to calculate the counts of SudokuP puzzles, which are essentially different for P-equivalence, but not for S-equivalence, from the numbers of invariants of SudokuP grids in the corresponding Sudoku and SudokuP classes ? (I don't know)

Quite possibly, I'll have to think about that. But it might be a way of tracking down the P-bug!

[eleven]

I can't believe your invariant count for the sticks symmetry (134).
From 127566 (ed) grids with sticks symmetry 9272 were SudokuP grids.

[Mathimagics]

You're right, that figure can't be right!

Running the S-equivalence enumerator with the P-class transformations confirms the counts for all P-classes, except for P27 ~= C134, which is still running but has already turned up a much larger number of PSudoku's, so something weird is going on in that class.

[Mathimagics]

According to my explicit P-equivalence enumerator, the count is 26,410,752 for P27, and progress for the S-equiv enumerator shows that is probably correct, and more in line with your sample.

[EDIT] That result is confirmed, I have updated the table above

[Mathimagics]

Eureka!

I balanced the books! I'd not updated one of the changed figures for the bug fix.

Code: Select all


Class  Size(N)   Invariants (PA) 
===============================
  1        1    554,191,840,696
  2        4             82,204 
  3        4          1,545,472 
  4        4             82,204 
  5       16             22,852 
  6       16              8,914 
  7        4          1,545,472 
  8       16              8,914 
  9        8             82,204 
 10        8          3,186,448 
 11       36             17,052 
 12       72                126 
 13       72                126 
 14      144                 12 
 21       81            962,088 
 26      324                780 
 27       18         26,410,752 
 28       36              6,912 
 29       36              6,912 
 30       72              5,832 
===============================
TP = Sum(N*PA)  554,786,788,896
UP = TP / 2592      214,038,113
===============================


You can see how huge that UP figure is for P-equivalence compared to what we expect for S-equivalence.

[Serg]

Hi, Mathimagics!
Please, describe your method in details. I don't understand, what is "Class", what is "Invariants", etc.
If the "214,038,113" is number of P-different (instead of "essentially different" for common 3,359,232 isomorphic transformations) P-sudokus, your result looks like right ...

Serg

[Mathimagics]

Hi Serg,

My apologies! I was so immersed in problems that I assumed everybody knew what I was doing. Perhaps only eleven knows exactly what's going on here!

• this table describes calculation of NUP = number of essentially P-different SudokuP grids, using restricted symmetry group GP of 2592 elements, with 54 conjugacy classes

• the GAP group definition will be listed below

• the "Class" number, C in first column identifies a conjugacy class (1 to 54) of GP, with class 1 = the identity transformation. These numbers correspond to those given by the GAP function ConjugacyClasses(SudokuP)

• the "Size" number, N in second column is number of elements in class #C

• the "Invariants" number, PA in 3rd column is the # of invariant (automorphic) grids in each element of the class (up to relabelling). This number for class #1 is the total # of different grids (which we already know), the rest are identified by my "Automorphism Enumerator", ie my reconstruction of Red Ed's "digit-template algorithm".

• the table lists only classes with non-zero invariants (20 of 54)

Please let me know if any errors/omissions are found in this description!

If the "214,038,113" is number of P-different (instead of "essentially different" for common 3,359,232 isomorphic transformations) P-sudokus, your result looks like right ...

Yes, and yes!!

The SudokuP symmetry group definition:

Hidden Text: Show

Code: Select all

SudokuP := Group(
 (2,10)(3,19)(4,28)(5,37)(6,46)(7,55)(8,64)(9,73)(12,20)(13,29)(14,38)(15,47)(16,56)(17,65)(18,74)(22,30)(23,39)(24,48)(25,57)(26,66)(27,75)(32,40)(33,49)(34,58)(35,67)(36,76)(42,50)(43,59)(44,68)(45,77)(52,60)(53,69)(54,78)(62,70)(63,79)(72,80),
 (1,9,81,73)(2,18,80,64)(3,27,79,55)(4,36,78,46)(5,45,77,37)(6,54,76,28)(7,63,75,19)(8,72,74,10)(11,17,71,65)(12,26,70,56)(13,35,69,47)(14,44,68,38)(15,53,67,29)(16,62,66,20)(21,25,61,57)(22,34,60,48)(23,43,59,39)(24,52,58,30)(31,33,51,49)(32,42,50,40),
 (1,2)(10,11)(19,20)(28,29)(37,38)(46,47)(55,56)(64,65)(73,74)(4,5)(13,14)(22,23)(31,32)(40,41)(49,50)(58,59)(67,68)(76,77)(7,8)(16,17)(25,26)(34,35)(43,44)(52,53)(61,62)(70,71)(79,80),
 (2,3)(11,12)(20,21)(29,30)(38,39)(47,48)(56,57)(65,66)(74,75)(5,6)(14,15)(23,24)(32,33)(41,42)(50,51)(59,60)(68,69)(77,78)(8,9)(17,18)(26,27)(35,36)(44,45)(53,54)(62,63)(71,72)(80,81),
 (1,4)(2,5)(3,6)(10,13)(11,14)(12,15)(19,22)(20,23)(21,24)(28,31)(29,32)(30,33)(37,40)(38,41)(39,42)(46,49)(47,50)(48,51)(55,58)(56,59)(57,60)(64,67)(65,68)(66,69)(73,76)(74,77)(75,78),
 (4,7)(5,8)(6,9)(13,16)(14,17)(15,18)(22,25)(23,26)(24,27)(31,34)(32,35)(33,36)(40,43)(41,44)(42,45)(49,52)(50,53)(51,54)(58,61)(59,62)(60,63)(67,70)(68,71)(69,72)(76,79)(77,80)(78,81) );


Note that this definition has 6 elements, but only 5 are actually required to generate the group. Element #2 is 90-degree rotation, which is redundant. See Russelll & Jarvis. However if you remove the redundant element the GAP conjugacy class numbers change, but not their composition.

Red Ed had already established his list of class numbers before he realised this, and I too didn't realise this until I had done the same! So I have followed R & J methodology most closely, even to point of reapeating this "mistake".

[Mathimagics]

Now, if I could just resolve the "transformation mapping" problem, which should allow me to identify the invariant grids for each member of a conjugacy class, I can arrive at the number we really would prefer to know, the number of essentially different (in the classical definition) SudokuP grids.

For some reason this mapping continues to elude me, despite eleven's attempts to explain it.

But I will persist ...

[eleven]

To illustrate the symmetries:

This is the example for class 6 (bands down/stacks right/rows up)
123 456 789
759 183 426
486 729 153

814 597 362
392 864 517
567 312 894

935 271 648
678 945 231
241 638 975

With the number cycle: (132)(486)(597) you get the same grid then.

Now cycle the rows in bands 2 downwards and in band 3 upwards.
What you get is a puzzle in class 4 (Jumping rows - bands down/stacks right)

123 456 789
759 183 426
486 729 153

567 312 894
814 597 362
392 864 517

678 945 231
241 638 975
935 271 648

So all invariants in PSudoku class 6 are S-equivalent to one in class 4.

Same for the the grids in class 5:
Bands down/stacks right/rows down/columns right
Example:
123 456 789
897 123 564
645 879 123

318 564 297
279 318 645
456 792 318

931 645 872
782 931 456
564 287 931

(1)(289)(3)(4)(5)(6)(7)

Move the rows in band 2 up, in band 3 down, and the columns in stack 2 left and in stack 3 right.
Then again you get a grid of class 4:

123 564 978
897 231 456
645 798 312

279 183 564
456 927 831
318 645 729

564 872 193
931 456 287
782 319 645

So also all invariants in PSudoku class 5 are S-equivalent to one in class 4.
Same for classes 9 with S-equivalents in class 7, 8 in 10 and 14 in 13.

[Mathimagics]

Ok, thanks, but what I really want to do is this:

For a given S-class, #7, I have A = set of grids for the representative transform T = t(1), where t(1...96) is the set of T's in class #7.

I also have B = set of for U = t(3). The inverse transform is U' = t(32).

My problem is that EVERY grid B in set 7/3 satisfies U'(A) = B and U(B) = A, and does so for EVERY grid A.

But I want to match ONE grid B to one A. I want to be able to generate the set B given set A alone.

I'll defer apologies for my general level of obtuseness, and expressions of eternal gratitude for your patience, until I resolve this. They do apply, however!

[EDIT] Removed reference to "SudokuP" grids, I just want generalised S-class mapping.