## SudokuP - Analysis

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Re: SudokuP - Frequency Analysis

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

Mathimagics
2017 Supporter

Posts: 1274
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Frequency Analysis

did you check for transformations that are identical? but uses different sets.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 979
Joined: 05 September 2006

### Re: SudokuP - Frequency Analysis

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
2017 Supporter

Posts: 1274
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Frequency Analysis

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               780134      972            449,445,888        26,410,752  135     3888                 27,648               128142    31104                  6,480                 0143    15552                  1,728                 0144    15552                  3,456                 0145     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.
Last edited by Mathimagics on Sat Jan 20, 2018 2:50 am, edited 2 times in total.

Mathimagics
2017 Supporter

Posts: 1274
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Frequency Analysis

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)
eleven

Posts: 2076
Joined: 10 February 2008

### Re: SudokuP - Frequency Analysis

eleven wrote: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.

eleven wrote: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!

Mathimagics
2017 Supporter

Posts: 1274
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Frequency Analysis

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

Posts: 2076
Joined: 10 February 2008

### Re: SudokuP - Frequency Analysis

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
2017 Supporter

Posts: 1274
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Frequency Analysis

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
2017 Supporter

Posts: 1274
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Frequency Analysis

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.

Mathimagics
2017 Supporter

Posts: 1274
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Frequency Analysis

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
Serg
2018 Supporter

Posts: 651
Joined: 01 June 2010
Location: Russia

### Re: SudokuP - Frequency Analysis

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!

Serg wrote: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
2017 Supporter

Posts: 1274
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Frequency Analysis

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 ...

Mathimagics
2017 Supporter

Posts: 1274
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Frequency Analysis

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.
eleven

Posts: 2076
Joined: 10 February 2008

### Re: SudokuP - Frequency Analysis

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.

Mathimagics
2017 Supporter

Posts: 1274
Joined: 27 May 2015
Location: Canberra

PreviousNext