The New Sudoku Players' Forum

by **blue** » Fri Feb 09, 2018 6:03 am

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.

by **Mathimagics** » Fri Feb 09, 2018 7:28 am

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

by **Mathimagics** » Fri Feb 09, 2018 8:49 am

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

by **Serg** » Fri Feb 09, 2018 9:51 am

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

by **blue** » Fri Feb 09, 2018 11:39 am

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.

P.S. I remember Mladen's "twins".

by **dobrichev** » Fri Feb 09, 2018 2:10 pm

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.

by **Mathimagics** » Fri Feb 09, 2018 3:00 pm

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

by **Serg** » Fri Feb 09, 2018 5:48 pm

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

by **eleven** » Fri Feb 09, 2018 10:17 pm

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.

by **Serg** » Fri Feb 09, 2018 10:41 pm

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

by **eleven** » Fri Feb 09, 2018 11:26 pm

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

by **Mathimagics** » Sat Feb 10, 2018 4:54 am

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?

by **Serg** » Sat Feb 10, 2018 9:06 am

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

by **Mathimagics** » Sat Feb 10, 2018 6:08 pm

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,552 Sum(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. 8-)

by **tarek** » Sat Feb 10, 2018 8:19 pm

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 :lol:

tarek

The New Sudoku Players' Forum

SudokuP - Analysis

Re: SudokuP - Analysis

Re: SudokuP - Analysis

Re: SudokuP - Analysis

Re: SudokuP - Analysis

Re: SudokuP - Analysis

Re: SudokuP - Analysis

Re: SudokuP - Analysis

Re: SudokuP - Analysis

Re: SudokuP - Analysis

Re: SudokuP - Analysis

Re: SudokuP - Analysis

Re: SudokuP - Analysis

Re: SudokuP - Analysis

Re: SudokuP - Analysis

Re: SudokuP - Analysis