## SudokuP - Analysis

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Re: SudokuP - Analysis

Mathimagics wrote:I am open to suggestion for alternate terminology, if we need to change so be it, but let's do it soon so we can get it out of the way and can still edit our posts!

I'm probably not the right one to comment, here, but for what you're doing, I would avoid the "essentially distinct" term, all together.
Off the top of my head, I might talk about partitioning the SudokuP grids into "S-classes", and wonder how many S-classes there are, for SudokuP.
blue

Posts: 894
Joined: 11 March 2013

### Re: SudokuP - Analysis

Actually, you know, that's not a bad idea at all ...

S-classes, S-equivalence, S-difference ...

P-classes, P-equivalence, P-difference ...

I'll go along with that ...

blue wrote:I might talk about partitioning the SudokuP grids into "S-classes", and wonder how many S-classes there are, for SudokuP.

A very good question! I've just been handed a telegram, and the answer is, I believe, exactly 171,677,353

That's ~ 3.137% of 5,472,730,538. More details to follow ...
Last edited by Mathimagics on Wed Feb 14, 2018 1:33 pm, edited 1 time in total.

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Analysis

Number of S-classes for std Sudoku (NSCS) and SudokuP (NSCP).

By automorphism group (|A| is automorphism count):
Code: Select all
`  |A|        NSCS         NSCP------------------------------   1   5472170387    171512273    2       548449       158125   3         7336         4165   4         2826         1671   6         1257          892   8           29           23   9           42           24  12           92           80  18           85           68  27            2            2  36           15           13  54           11           10  72            2            2 108            3            3 162            1            1 648            1            1------------------------------       5472730538    171677353`

We see that S-automorphism cases have much higher probability of P-isomorphism (30%) than the general population (3%), yet S-automorphisms don't guarantee P-isomorphisms (eg, case |A| = 54).

Here is a table of counts by (gsf) band:
Hidden Text: Show
Code: Select all
`   Band             NSCS        NSCP -----------------------------------   001           1007170      355168   002          25502082     4309260   003          16538087     1137589   004           8417906      571240   005          48737791     2266642   006          96229042     3080155   007          15765443      279125   008           5306280      102563   009           8136013      664852   010          47174193     1623405   011          46788396     1384456   012          46177270      863561   013          15340394      279409   014          45397270      767436   015          45600758      885081   016           1631576       19710   017          15093541      269114   018          45101600     3453925   019          44832423     2472535   020          88782526     2795160   021          44036568     3291519   022          85627559     2157797   023          42711122     1449040   024          85102373     1964485   025          41847039      823424   026          41335391      740455   027           4455504      205200   028          41102914     1293651   029           4591391       92523   030           4664261      156215   031          13606209      252123   032          40697707      916680   033          80468663     3816637   034          79175610     1772057   035          77979783     3778806   036          38536298      898833   037          76146967     1814020   038          74505665     1643191   039          74154564     2512096   040          72171447     1561942   041          36053455     1263991   042          70552290     1952744   043          69437575     1967292   044          67978951     2059818   045          33904021     1397305   046          66337407     2046269   047          65880161     2826619   048          64996381     3029171   049          63898062     2796678   050          62192220     1077584   051          61691475     1431958   052          60192385     1074562   053          29966384      715380   054          29734495      870038   055          58731513     1634689   056          57263818     1698901   057          57033275     2554237   058          55394556     1664289   059          55022930     2158564   060          54018514     2087154   061          52964870      994316   062          52242492     2017678   063          51245000      980404   064          50540742     1012477   065          49644127     1005415   066          49190978     1552709   067          24077300      968815   068          47978806     1502940   069          47059527     1260920   070          46231581     1210974   071          22715795      621932   072          44778204     1303763   073          44053469     1192356   074          43401907     1201460   075          21398806      582194   076          42061440      884457   077          41316125      825608   078          40571245      936432   079          40282447     1199160   080          39233218     1150017   081          38522319     1075134   082          37881913     1107320   083          37460193     1358725   084          18460204      646787   085          36127803      828468   086          35584769      831371   087          34821531      839033   088          34334716      985044   089          33769162     1153695   090          33174401     1520794   091          32520037     1100151   092          31945541      963567   093          31221072      838841   094          30579410      752365   095          29977732      720358   096          29390061      639750   097          14518368      363781   098          14372444      392678   099          28268021      563182   100          27849953      801512   101          13768854      485248   102          26929453      656310   103          26382806      493352   104           4359314      109819   105          25997296      803704   106          25467197      699571   107          24888528      573163   108          24423300      809984   109          23988326      652770   110          23541927      747909   111          23070530      625941   112          22609142      719138   113          22100458      540219   114          10879514      266446   115          21378062      497651   116          20985174      601431   117          20674972      559868   118          20107116      403264   119          19854606      706627   120           9732970      244048   121          19084488      361067   122           9491325      298447   123          18532281      450259   124           9142485      313026   125          18075269      580134   126          17675306      438257   127          17545752      808281   128          16990098      536960   129           8369473      256889   130          16406705      358268   131          16189996      593524   132          15791769      498896   133           2613345      101836   134          15362664      381910   135          15272476      803537   136          14918036      731187   137           7254450      241614   138          14383075      586267   139           7011714      169886   140          13738161      372897   141          13445152      370081   142           6593805      221747   143          12918117      306972   144           6403269      272847   145          12568136      357464   146          12354720      547880   147          12036469      423372   148           5931073      221288   149           5949060      246897   150          11577852      369636   151          11435633      539275   152          11155974      548145   153          10671486      196791   154          10525735      260642   155          10188634      186554   156          10059617      259085   157           9805813      262666   158           9629320      387614   159           9490222      498171   160           9280124      507336   161           8844112      205905   162           8628099      202902   163           8429593      191959   164           8227144      208522   165           7998287      154643   166           7813413      162732   167           3839149       74786   168           7548052      158877   169           7349287      148404   170           7146807      137500   171           6993422      186832   172           6828801      184316   173           6674911      173777   174           6476248      173877   175           3166465       63137   176           6205963      116384   177           6040631      123552   178           5882934      114042   179           5812748      144824   180           5615082      143222   181           5461387      126382   182           5367414      163401   183           5222068      167116   184           5072949      131699   185           4918277      119414   186           4778878      120025   187           4641003      153180   188           4539624      130520   189           4407284      131887   190           2186822      100655   191           4220821      118873   192           4158097      156266   193           4070158      166447   194           3857103       95121   195           3785628      120448   196           3693474      128897   197           3555681       95464   198           3453089       92086   199           3345667       85648   200           3252227       93190   201           3165254       82485   202           3064062       89715   203           2966309       83041   204           2932890      110068   205           2841380      111224   206           2701985       65304   207           2628788       73542   208           2532198       76659   209           2443960       54892   210           1243959       44047   211           2317171       51297   212           2357854       83360   213           1137589       44544   214           1083228       30745   215           2183311       88131   216           2244753      136118   217           2143677      130822   218           2100798      150217   219           1007465       50160   220           1970315      101543   221           1841722       75657   222           1873099      134720   223           1772301       88251   224            347777       72199   225           1968442      368865   226           1677704      100303   227           1521001       51042   228           1498734       51848   229           1515366       92259   230           1457098       83798   231           1331185       43393   232           1279569       41863   233           1262013       41191   234           1218744       40383   235            386642       12945   236           1182963       46348   237            570172       24320   238           1111083       45279   239           1076551       43474   240            167032        6609   241            533940       20528   242           1048083       58216   243            974591       36457   244            967788       57826   245            455310       18663   246            915249       49238   247            500537       58731   248            783336       18921   249            822496       33083   250-259       4118353      251905   260-269       4942966      130999   270-279       2374942       66598   280-289       1443458       53567   290-299       1584461       60741   300-416       2097068       93333  ----------------------------------              5472730538   171677353`

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Analysis

Hi, blue
blue wrote:
Serg wrote:Definition
SudokuP Validity Preserving Group or PVP Group is group of transformations preserving validity of any valid SudokuP puzzle or solution grid. This group is generated by following set of transformations and is subgroup of VPT Group.

1. Transposing.
2. Permutations of 3 bands.
3. Permutations of 3 stacks.
4. The same permutations of rows in every band.
5. The same permutations of columns in every stack.

Totally we have 2 x 6^4 = 2592 isomorphic transformations.

I argued earlier that this isn't the full "PVP" group.
I won't labor the point, but it's the intersection of the "full group" with the Sudoku VPT group.

I think you mean, that there are extra transformations preserving validity of some SudokuP puzzles or solution grids (for example, F-transformation). Those transformations don't participate PVP Group, so this group isn't full. But F-transformation isn't universal, i.e. it preserves validity of some SudokuP solution grids, but doesn't preserve validity of others. I wrote in my definition "PVP Group is group of transformations preserving validity of any valid SudokuP puzzle or solution grid", therefore F-transformation cannot participate this group. You can define another group (or set) of transformations including F-transformation, but that definition will define another kind of equivalence. When we say "there are 214,038,113 P-different SudokuP solutions grids" we mean that neither solution grid among those 214,038,113 SudokuP grids can be transformed to another by some transformation from PVP Group. One can define another kind of equivalency and get another number of X-equivalent SudokuP grids. But it doesn't imply that my definition of PVP Group is wrong.

I remember similar discussion years ago - should we treat "twin" valid sudoku puzzles, having unhitted UA sets among their clues and being transformed to each other by UA sets permutations, as different puzzles. Such "twins" have the same solution paths, so they are equivalent in wide sense. But when we say "essentially different" sudoku puzzles, we mean that neither of those puzzles can be transformed to another puzzle by one of 3,359,232 isomorphic transformations. This is question of definitions.

Serg
Serg
2018 Supporter

Posts: 717
Joined: 01 June 2010
Location: Russia

### Re: SudokuP - Analysis

Hi Serg,

I think you mean, that there are extra transformations preserving validity of some SudokuP puzzles or solution grids (for example, F-transformation). Those transformations don't participate PVP Group, so this group isn't full. But F-transformation isn't universal, i.e. it preserves validity of some SudokuP solution grids, but doesn't preserve validity of others.

There's an argument buried in this (long) post, that F is universal (for SudokuP grids). It went like this ...

blue wrote:Earlier, I wrote, of F, that:
It maps rows to boxes, boxes to rows, columns to box positions, and box positions to columns.

From that, we have that:
• F maps grids satisfying the "row property", to grids satisfying the "box property"
• F maps grids satisfying the "columns property", to grids satisfying the "position property"
• F maps grids satisfying the "box property", to grids satisfying the "row property"
• F maps grids satisfying the "position property", to grids satisfying the "column property"
It follows that F maps grids satisfying all 4 properties -- SudokuP grids -- to grids satisfying all 4 properties.
For Sudoku grids, though ... that are only required to satisfy the "row, column and box" properties ... it maps them to grids satisfying "row, position, and box" properties ... with no guarantee that the "column" property is satisfied, and so no guarantee that the result is also a Sudoku grid.

The sentence in blue, isn't part of the argument.
This is silly, but looking back at it, I meant to say "box, position, and row" properties, rather than "row, position, and box" properties ... to better highlight the connection with "what maps to what", under F.

blue

Posts: 894
Joined: 11 March 2013

### Re: SudokuP - Analysis

blue wrote:P.S. I remember Mladen's "twins".

Hi Blue,

Your F-transformation is very interesting by itself, but counting it as a universal sudokuP transformation to me is mater of convention.
A stronger than "twins" example: since we are working on full grids, you proved once that modulo swapping the values within a unavoidable set there is only one "essentially different sudokuU" grid, i.e. transformations path from any particular grid to the MC grid always exists.

edit: meant swapping the values within a minimal ua.
Last edited by dobrichev on Fri Feb 09, 2018 10:40 pm, edited 1 time in total.
dobrichev
2016 Supporter

Posts: 1785
Joined: 24 May 2010

### Re: SudokuP - Analysis

I've just had the auditors in to check my results. They came up with this account:

• NSP = 555,139,980,000
• NDP = 554,191,840,696
• NSP-NDP = 948,139,304

NSP is the total # of SudokuP isomorphisms returned by my counting procedure.

NDP is the exact number of different SudokuP grids (up to relabelling).

And 948,139,304 is the exact number of automorphic Sudoku grids (up to relabelling).

The data which produced the first figure is given here. For each grid with 1 or more SudokuP isomorphisms we add up the total number of such isomorphisms (as adjudged by the iso-checker) and multiply that by 2592 for the full count:
Hidden Text: Show
Code: Select all
`   NI             Count  ---------------------    1         143617893    2          21927558    3           3286903    4           1305594    5            227818    6            847506    7            183130    8             12353    9              4359   10               379   11              1218   12            183203   13             43996   14              2807   15              1282   16                44   17               352   19                47   21                18   23                31   25                 2   27                 8   31                 1   33                 1   36             25207   37              4437   38               299   39               682   40                25   41               124   42                20   43                23   45                13   46                 1   47                11   48                 2   51                 3   53                 1   71                 1   73                 1   --------------------   T  =     171,677,353   (# with 1 or more SudukuP-iso's)   TI =     214,174,375   (sum of NI * Count)    NP = 555,139,980,000   (TI * 2592, actual number of iso's)`

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Analysis

Hi, blue!
You are right, F-transformation is universal, i.e. it transforms any valid SudokuP puzzle/solution grid to another valid SudokuP puzzle/solution grid. Sorry, I have not carefully read your posts.

Definition (corrected)
SudokuP Validity Preserving Group or PVP Group is group of transformations preserving validity of any valid SudokuP puzzle or solution grid. This group is generated by following set of transformations.

1. Transposing.
2. Permutations of 3 bands.
3. Permutations of 3 stacks.
4. The same permutations of rows in every band.
5. The same permutations of columns in every stack.
6. F-transformation (permutations of minirows in each band).
7. G-transformation (permutations of minicolumns in each stack).

Totally we have 8 x 6^4 = 10368 isomorphic transformations.

Therefore, number of p-different SudokuP solution grids should be recalculated. It seems true number of p-different SudokuP solution grids should be around 214,038,113/4 = 53,509,528 (approx.)

Can we be sure that all possible transformations preserving validity of any valid SudokuP solution grid are accounted for?

Good news is that number of coset representatives is 4 times less now - 324 transformations instead of 1296 transformations.

Separate set of transformations potentially preserving validity of SudokuP solution grids should be defined (instead of VPT Group), and it looks like that set of such transformations won't form a group ...

Serg

[Edited. I got excited, stating, that known results in Sudoku Mathematics are in question. Really, F-transformation effects essentially different SudokuP solution grids enumeration only. I'm sorry.]
[Edited2. PVP Group is redefined and added some considerations.]
Serg
2018 Supporter

Posts: 717
Joined: 01 June 2010
Location: Russia

### Re: SudokuP - Analysis

Serg wrote:I remember similar discussion years ago - should we treat "twin" valid sudoku puzzles, having unhitted UA sets among their clues and being transformed to each other by UA sets permutations, as different puzzles. Such "twins" have the same solution paths, so they are equivalent in wide sense.

This is not quite true. If you take a puzzle, and swap the digits of an unavoidable set in the solution, thus swapping at least one given in the puzzle, then the new puzzle generally will not have a unique solution too. The new grid has a very different set of puzzles at all.
But i remember from solving digit symmetric (automorph) puzzles using symmetry techniques, that you can use them too, if a puzzle with the givens of an unavoidable set swapped would be digit symmetric.
The solution path is only the same, if all digits of an unavoidable set are givens in the puzzle.
eleven

Posts: 2461
Joined: 10 February 2008

### Re: SudokuP - Analysis

Hi, eleven!
eleven wrote:
Serg wrote:I remember similar discussion years ago - should we treat "twin" valid sudoku puzzles, having unhitted UA sets among their clues and being transformed to each other by UA sets permutations, as different puzzles. Such "twins" have the same solution paths, so they are equivalent in wide sense.

This is not quite true. If you take a puzzle, and swap the digits of an unavoidable set in the solution, thus swapping at least one given in the puzzle, then the new puzzle generally will not have a unique solution too. The new grid has a very different set of puzzles at all.

You are right. But I meant not swapping the digits of an unavoidable set in the solution, I meant swapping the givens (clues) only.

This is an example.
Code: Select all
`2 . 3 . . . 4 . 6       2 . 3 . . . . . .     puzzle 1. 1 . . . . . 2 .       . . . . . . . . .5 . 7 . . . 8 . 3       . . . . . . . . .. . . 2 . 3 . . .       . . . . . . . . .. . . . 1 . . . .       . . . . . . . . .. . . 4 . 5 . . .       . . . . . . . . .3 . 2 . . . 6 . 8       3 . 2 . . . . . .. 6 . . . . . 4 .       . . . . . . . . .8 . 1 . . . 5 . 9       . . . . . . . . .3 . 2 . . . 4 . 6       3 . 2 . . . . . .     puzzle 2. 1 . . . . . 2 .       . . . . . . . . .5 . 7 . . . 8 . 3       . . . . . . . . .. . . 2 . 3 . . .       . . . . . . . . .. . . . 1 . . . .       . . . . . . . . .. . . 4 . 5 . . .       . . . . . . . . .2 . 3 . . . 6 . 8       2 . 3 . . . . . .. 6 . . . . . 4 .       . . . . . . . . .8 . 1 . . . 5 . 9       . . . . . . . . .`

Puzzle 1 and puzzle 2 are twins, because puzzle 1 produces puzzle 2 by U4 unavoidable set permutation of clues (and vice versa). Both puzzles have the same solution paths.

Serg
Serg
2018 Supporter

Posts: 717
Joined: 01 June 2010
Location: Russia

### Re: SudokuP - Analysis

Yes, here all 4 UA4 digits are givens. Thus the puzzles are "solver equivalent". But not the grids (solutions).
eleven

Posts: 2461
Joined: 10 February 2008

### Re: SudokuP - Analysis

serg wrote:Therefore, number of p-different SudokuP solution grids should be recalculated.

Having established universality of F, G, then that makes sense. I will reconfigure the PVP group and make a new pass over the data ...

Serg wrote:Can we be sure that all possible transformations preserving validity of any valid SudokuP solution grid are accounted for?

That seems highly probable, unless blue has another trick up his sleeve?

Serg wrote:Good news is that number of coset representatives is 4 times less now - 324 transformations instead of 1296 transformations.

I am not sure how this helps. We only used the 1296-transformation set in the context of counting P-isotopes among the 5.47 billion ED-Sudoku representatives. That result is now known, and using a different PVP group has no effect on this result, it seems to me.

Put another way, the splitting of S-group into 1296 x 2592 makes sense to me, since the 2592 P-preserving transformations were a subset of the S-preserving transformations. With P-preservers extended to include F and G, this subset relationship no longer holds true, so we can't do the same splitting operations.

Unless, of course, I have made (yet another) group-theoretical blunder?

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Analysis

Hi, Mathimagics!
Mathimagics wrote:
serg wrote:Therefore, number of p-different SudokuP solution grids should be recalculated.

Having established universality of F, G, then that makes sense. I will reconfigure the PVP group and make a new pass over the data ...

I am waiting for new results.
Mathimagics wrote:
Serg wrote:Good news is that number of coset representatives is 4 times less now - 324 transformations instead of 1296 transformations.

I am not sure how this helps. We only used the 1296-transformation set in the context of counting P-isotopes among the 5.47 billion ED-Sudoku representatives. That result is now known, and using a different PVP group has no effect on this result, it seems to me.

Put another way, the splitting of S-group into 1296 x 2592 makes sense to me, since the 2592 P-preserving transformations were a subset of the S-preserving transformations. With P-preservers extended to include F and G, this subset relationship no longer holds true, so we can't do the same splitting operations.

You are right. We cannot consider targeted set of SudokuP solution grids as subset of 5.47 billion ed sudoku solution grids. Even the name of those searched SudokuP solution grids isn't known. What are we searching for? Not essentially different SudokuP solution grids, because VPT Group doesn't contain F/G-transformations. Here is my trial to define them.

Definition
Two SudokuP puzzles/grids/patterns are naturally the same if there is VPT or PVP transformation transforming one puzzle/grid/patterns to another. Otherwise these puzzles/grids/patterns are naturally different or nd-different.

Not elegant definition, of course ...

blue's discovery destroys common concepts ...

Mathimagics wrote:Unless, of course, I have made (yet another) group-theoretical blunder?

I don't see any errors (but I am not Group Theory expert myself too). It seems to me your English is not native - your vocabulary is too rich (I was forced to search "blunder" in Google translator ).

Serg
Serg
2018 Supporter

Posts: 717
Joined: 01 June 2010
Location: Russia

### Re: SudokuP - Analysis

It seems true number of p-different SudokuP solution grids should be around 214,038,113/4 = 53,509,528 (approx.)

Very close! The actual number is 53,666,689

Burnside's Lemma method, details for each non-empty class:

Hidden Text: Show
Code: Select all
`Class # Invts   Members   Class Invariants  ------------------------------------------  1                        554,191,840,696  2   1545472         8         12,363,776  3     82204        16          1,315,264  4   3186448         8         25,491,584  5      8914        32            285,248  6     22852        16            365,632  7    962088        81         77,929,128  8     17052        72          1,227,744  9       126       288             36,288 10        12       288              3,456 11  13511908        36        486,428,688 12      3280       144            472,320 13       592       144             85,248 17       780       648            505,440 18       580       324            187,920 19  26410752        18        475,393,536 20      6912        72            497,664 21      5832        72            419,904 34  78307288        12        939,687,456 35     11344        48            54,4512 36      8296        24            199,104 37       904        96             86,784 38     27028        48          1,297,344 39       766        96             73,536 40   1834384       108        198,113,472 41      2632       216            568,512 42      1222       432            527,904 43         4       864              3,456 46      2316        72            166,752 47        48       144              6,912 48       264       144             38,016 49        30       288              8,640 50        46      1296             59,616------------------------------------------    125962376      6155    556,416,231,552Sum(NI * Members)/10368         53,666,689 `

Serg wrote:I was forced to search "blunder" in Google translator

Howls of derisive laughter! I am in fact Australian, of mostly Irish/Scotttish extraction.

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Analysis

Serg wrote: It seems to me your English is not native - your vocabulary is too rich (I was forced to search "blunder" in Google translator ).

Apologies for interrupting your interesting discussion. I couldn't ignore though Serg's post of the day

tarek

tarek

Posts: 3745
Joined: 05 January 2006

PreviousNext