## Solution grids with higher potential to have 17-clue puzzles

Everything about Sudoku that doesn't fit in one of the other sections

### Solution grids with higher potential to have 17-clue puzzles

Can we reduce the grid candidates having undiscovered 17-clue puzzle(s) using reasonable amount of calculations?

This is a compound picture of statistics published elsewhere.

Scales and offsets on abscissa were chosen to match the straight lines of the correlating proportions.
Ordinate values are the corresponding (All Grids) / (Puz17), in logarithmic scale.

This is the raw data. Columns Gr17 are for completeness and aren't shown on the picture.
Code: Select all
`+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------+|Method|     Count UA 4       |    Count UA6 type 1  |    Count UA6 type 2  |    Count UA6 type 3  |    Count UA6 type 4  |   Resolve Bands      |  Resolve 3-templates |+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------+|Count |All Grids |Gr17 |Puz17|All Grids |Gr17 |Puz17|All Grids |Gr17 |Puz17|All Grids |Gr17 |Puz17|All Grids |Gr17 |Puz17|All Grids |Gr17 |Puz17|All Grids |Gr17 |Puz17|+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------+|0     |352894    |93   |104  |7058239   |60   |60   |175280926 |1932 |2055 |713721185 |6387 |6792 |262638183 |5283 |5727 |          |     |     |          |     |     ||1     |1654475   |398  |438  |53596343  |482  |509  |628112738 |6352 |6746 |1502357397|13278|14091|688798768 |8435 |8988 |          |     |     |          |     |     ||2     |6891532   |1231 |1362 |190542546 |1585 |1674 |1078390061|10014|10585|1396463035|12158|12917|1078929598|9669 |10303|          |     |     |          |     |     ||3     |21107315  |2561 |2791 |425402053 |3330 |3485 |1195195635|10199|10802|884489561 |7291 |7713 |1174616582|8774 |9298 |          |     |     |          |     |     ||4     |51765007  |4005 |4331 |678502202 |5166 |5467 |977370324 |7958 |8480 |481429573 |3711 |3932 |974546767 |6279 |6579 |          |     |     |          |     |     ||5     |105759561 |5583 |6003 |835908150 |6364 |6718 |647529117 |4824 |5153 |242241411 |1874 |2019 |647368042 |4041 |4240 |          |     |     |          |     |     ||6     |186644998 |6369 |6740 |844110777 |6570 |6934 |373877515 |2580 |2768 |127764002 |841  |890  |359613894 |2171 |2285 |          |     |     |          |     |     ||7     |289799298 |6418 |6832 |734477502 |5844 |6178 |198448822 |1317 |1386 |60676743  |393  |417  |171856991 |944  |995  |          |     |     |          |     |     ||8     |402555715 |5827 |6170 |573956910 |4889 |5199 |100290117 |602  |635  |30522261  |168  |180  |72638561  |417  |438  |         6|     |     |      2826|    4|    6||9     |505627121 |4787 |4997 |413948030 |3911 |4266 |49202638  |275  |292  |14251151  |99   |101  |27623697  |192  |201  |   1239360|  250|  271|  75838126| 4901| 5320||10    |580153348 |3489 |3643 |279269015 |2775 |2984 |23694335  |126  |129  |8223423   |35   |39   |9650892   |66   |72   |  97729312| 5750| 6215| 870139488|19187|20438||11    |612280600 |2397 |2478 |177823515 |2023 |2134 |11580594  |67   |71   |4337237   |24   |25   |3117453   |19   |19   |1082360670|20922|22235|2522652319|17559|18539||12    |598177291 |1513 |1577 |108305416 |1252 |1343 |6067695   |25   |25   |2939620   |18   |18   |949921    |7    |9    |2631838676|16691|17642|1682829554| 4182| 4373||13    |543232929 |820  |862  |64072036  |842  |913  |3381776   |10   |11   |1308222   |6    |6    |272448    |3    |3    |1364599022| 2550| 2654| 291188927|  429|  442||14    |460415833 |418  |427  |37213845  |497  |541  |1970365   |6    |6    |824117    |7    |7    |77070     |     |     | 263770800|  126|  129|  25155656|   33|   34||15    |364777309 |228  |236  |21203099  |286  |301  |1011309   |3    |3    |370638    |3    |3    |21587     |     |     |  28131065|   10|   10|   4636997|    5|    5||16    |270755777 |99   |100  |11938874  |175  |189  |545106    |6    |6    |334313    |2    |2    |6455      |     |     |   2785923|    1|    1|    267033|     |     ||17    |188260086 |43   |45   |6653163   |111  |117  |263987    |     |     |111665    |2    |2    |2047      |     |     |    228185|     |     |     13660|     |     ||18    |122672303 |18   |18   |3764132   |53   |54   |157074    |3    |3    |86570     |2    |2    |829       |     |     |     47519|     |     |      5952|     |     ||19    |74788269  |3    |3    |2067657   |34   |36   |111238    |     |     |99778     |     |     |330       |     |     |          |     |     |          |     |     ||20    |42628010  |     |     |1194516   |16   |19   |107537    |     |     |92733     |     |     |188       |     |     |          |     |     |          |     |     ||21    |22634443  |     |     |684316    |16   |16   |53319     |     |     |22966     |     |     |85        |     |     |          |     |     |          |     |     ||22    |11177578  |     |     |417528    |10   |11   |32866     |1    |1    |18569     |1    |1    |61        |     |     |          |     |     |          |     |     ||23    |5123654   |     |     |226767    |3    |3    |8405      |     |     |2296      |     |     |31        |     |     |          |     |     |          |     |     ||24    |2176664   |     |     |158141    |4    |4    |7827      |     |     |4956      |     |     |20        |     |     |          |     |     |          |     |     ||25    |854253    |     |     |71129     |1    |1    |1527      |     |     |167       |     |     |4         |     |     |          |     |     |          |     |     ||26    |311585    |     |     |51015     |     |     |1919      |     |     |1685      |     |     |8         |     |     |          |     |     |          |     |     ||27    |105410    |     |     |29609     |1    |1    |7109      |     |     |12564     |     |     |8         |     |     |          |     |     |          |     |     ||28    |33612     |     |     |25368     |     |     |9904      |     |     |10967     |     |     |5         |     |     |          |     |     |          |     |     ||29    |9897      |     |     |15640     |     |     |8166      |     |     |5000      |     |     |2         |     |     |          |     |     |          |     |     ||30    |2798      |     |     |17213     |     |     |5623      |     |     |3509      |     |     |6         |     |     |          |     |     |          |     |     ||31    |721       |     |     |7604      |     |     |2167      |     |     |1212      |     |     |          |     |     |          |     |     |          |     |     ||32    |186       |     |     |5779      |     |     |1344      |     |     |1029      |     |     |1         |     |     |          |     |     |          |     |     ||33    |43        |     |     |3545      |     |     |599       |     |     |257       |     |     |          |     |     |          |     |     |          |     |     ||34    |14        |     |     |2661      |     |     |405       |     |     |359       |     |     |          |     |     |          |     |     |          |     |     ||35    |          |     |     |600       |     |     |40        |     |     |4         |     |     |          |     |     |          |     |     |          |     |     ||36    |9         |     |     |2675      |     |     |268       |     |     |245       |     |     |2         |     |     |          |     |     |          |     |     ||37    |          |     |     |345       |     |     |6         |     |     |          |     |     |          |     |     |          |     |     |          |     |     ||38    |          |     |     |788       |     |     |53        |     |     |52        |     |     |          |     |     |          |     |     |          |     |     ||39    |          |     |     |473       |     |     |10        |     |     |          |     |     |          |     |     |          |     |     |          |     |     ||40    |          |     |     |271       |     |     |6         |     |     |          |     |     |          |     |     |          |     |     |          |     |     ||41    |          |     |     |73        |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     ||42    |          |     |     |802       |     |     |60        |     |     |61        |     |     |1         |     |     |          |     |     |          |     |     ||43    |          |     |     |1         |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     ||44    |          |     |     |50        |     |     |1         |     |     |          |     |     |          |     |     |          |     |     |          |     |     ||45    |          |     |     |28        |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     ||46    |          |     |     |44        |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     ||47    |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     ||48    |          |     |     |10        |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     ||49    |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     ||50    |          |     |     |8         |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     ||51    |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     ||52    |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     ||53    |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     |          |     |     ||54    |          |     |     |35        |     |     |5         |     |     |5         |     |     |1         |     |     |          |     |     |          |     |     ||Total:|5472730538|46300|49157|5472730538|46300|49157|5472730538|46300|49157|5472730538|46300|49157|5472730538|46300|49157|5472730538|46300|49157|5472730538|46300|49157|+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------+`

6-cells UA 6.1, 6.2, 6.3 and 6.4 definitions.
Hidden Text: Show
UA 6.1
Code: Select all
`AB* *** ****** *** ****** *** ***BC* *** ****** *** *** or AB,CA,BC*** *** ***CA* *** ****** *** ****** *** ***`

UA 6.2
Code: Select all
`AB* *** ****** *** ****** *** ***B*A *** ****** *** ****** *** ****AB *** ****** *** ****** *** ***`

UA 6.3
Code: Select all
`ABC *** ****** *** ****** *** ***BCA *** ****** *** ****** *** ****** *** ****** *** ****** *** ***`

UA 6.4
Code: Select all
`AB* *** ****** *** ****** *** ***B** A** ****A* B** ****** *** ****** *** ****** *** ****** *** ***`

The 6-clue UA sets don't correlate with 17s.
The lower left end of the green Templates line possibly is an artefact of the small number of grids.
The extreme for Bands at 6 grids requiring 8 clues isn't shown because none has a 17-clue puzzle. Same for Boxes requiring 8 clues.

Excluding the 6-cell UA, the number of 17-clue puzzles in a grid also trends to increase with decreasing the count (min clues or number of UA respectively).

Multiple edits: Added Boxes to the picture.
Hidden Text: Show
gridsper17.png (61.11 KiB) Viewed 1857 times
Last edited by dobrichev on Sun Aug 05, 2018 10:44 am, edited 9 times in total.
dobrichev
2016 Supporter

Posts: 1827
Joined: 24 May 2010

### Re: Solution grids with higher potential to have 17-clue puz

This is data for a method similar to the (3x) "band/stack" and (3x) "3-template" parititioning methods.
The MC54 value is the maximum of 9 sums, related to the 9 ways to partition a grid into "B12347/B5689"-like sections (B = boxes).

Code: Select all
`MC54 |      grids |  17CG | 17CG/grids | 17CGP | 17CGP/17CG-----+------------+-------+------------+-------+-----------  7  |          0 |       |            |       |  8  |          4 |       |            |       |  9  |      26845 |    11 | 0.0409760% |    13 |      1.182 10  |  608975654 | 19775 | 0.0032473% | 21169 |      1.070 11  | 3479609749 | 24517 | 0.0007046% | 25887 |      1.056 12  | 1242604679 |  1871 | 0.0001506% |  1959 |      1.047 13  |  129868993 |   111 | 0.0000855% |   114 |      1.027 14  |   10762326 |    15 | 0.0001394% |    15 |      1.000 15  |     860960 |       |            |       | 16  |      19976 |       |            |       | 17  |       1152 |       |            |       | 18  |        200 |       |            |       |-----+------------+-------+------------+-------+-----------     | 5472730538 | 46300 | 0.0008460% | 49157 |      1.062`

The minimum number of clues for a B12347 section (a band crossing a stack) is 5.
The minimum number of clues for a B5689 section (a 2x2 set of boxes) is 2.
The minimum clue count distributions, for the respective canonical forms, are below.

Hidden Text: Show
Code: Select all
`B12347 MinClues distribution (for the 18296007 canonical forms)5:   8793816: 123322507:  48226918:   2582369:     3449B5689 MinClues distribution (for the 5699915 canonical forms)2:       443:   5535914:  46030355:   5272586:    157017:      2848:        19:        1`

The 4+26845 grids with MC54 <= 9 have been checked for 17's.
Nothing new, came of it.

Edit: corrected multiple errors in table, that were due to late night "manual summing" of results from 3 threads (using copy/paste with a calculator app). Many thanks to dobrichev for spotting the bad "total grids" number.
blue

Posts: 894
Joined: 11 March 2013

### Re: Solution grids with higher potential to have 17-clue puz

Good job Blue!

Your progress is impressive. For these calculations I am spending hundreds of CPU hours. You use calculator.

The Boxes results are added to the picture in the opening post.

Concerning the X axes of the picture.
The measured values by the different methods are in general incompatible and this gives freedom in choice of the scales and origins for the different X axes for better comparison of the shapes.
dobrichev
2016 Supporter

Posts: 1827
Joined: 24 May 2010

### Re: Solution grids with higher potential to have 17-clue puz

dobrichev wrote:Your progress is impressive. For these calculations I am spending hundreds of CPU hours. You use calculator.

It did take a long time ... ~76 core hours to get the minclues values for the canonical forms, and ~122 to process the grid catalog.
blue

Posts: 894
Joined: 11 March 2013

### Re: Solution grids with higher potential to have 17-clue puz

The 2826 grids with MC3T = 8 were checked for 17s too.

This subgrid appears, which should have imbalanced UA distribution.
Code: Select all
`123456789456789123798132564275813496381964257964527318539671842617248935842395671...4..........9.2.7.............3.9...1..........................................`

From the perspective of the given solution grid, this subgrid generated 3,230,330 low-clue puzzle candidates. For all other grids that were ever scanned using this tool (> 4000) the candidates were < 200,000.
Most of the candidates were discarded by the secondary low-quality UA filter and for the whole grid 1,116,669 solver calls were made which isn't unusual. The scanning time was 1790 seconds and isn't unusual too.

The uncovered by the subgrid area should be rich in medium and large sized UA, or the covered areas is rich in low-sized simple and composite UA so that others are discarded from the primary filter being qualified as low-quality.
dobrichev
2016 Supporter

Posts: 1827
Joined: 24 May 2010

### Re: Solution grids with higher potential to have 17-clue puz

blue wrote:
Code: Select all
`MC54 |      grids |  17CG | 17CG/grids | 17CGP | 17CGP/17CG-----+------------+-------+------------+-------+-----------  7  |          0 |       |            |       |  8  |          4 |       |            |       |  9  |      26845 |    11 | 0.0409760% |    13 |      1.182 10  |  608975654 | 19775 | 0.0032473% | 21169 |      1.070 11  | 3479609749 | 24517 | 0.0007046% | 25887 |      1.056 12  | 1242604679 |  1871 | 0.0001506% |  1959 |      1.047 13  |  129868993 |   111 | 0.0000855% |   114 |      1.027 14  |   10762326 |    15 | 0.0001394% |    15 |      1.000 15  |     860960 |       |            |       | 16  |      19976 |       |            |       | 17  |       1152 |       |            |       | 18  |        200 |       |            |       |-----+------------+-------+------------+-------+-----------     | 5472730538 | 46300 | 0.0008460% | 49157 |      1.062`

would there be an option to estimate the numbers of 17 and 18 clue puzzles [like you did with the sudokup 12C] ?

also i dont believe that the number of ed canonical forms has been elucidated / published ... well done ...
Code: Select all
`B12347 - 18296007 canonical formsB5689  -  5699915 canonical forms`
coloin

Posts: 2178
Joined: 05 May 2005
Location: Tenerife

### Re: Solution grids with higher potential to have 17-clue puz

Hi Colin,

Thanks.

would there be an option to estimate the numbers of 17 and 18 clue puzzles [like you did with the sudokup 12C] ?

For 17s, no. Too many samples would be required.
For 18s, it would be possible, but it would take a long time.
Also, it might be better to use the "band-based" or "3-template-based" breakdown, than the "5+4 boxes" breakdown.
[ A reminder: I only estimated the number of grids with 12C SudokuP puzzles ]

----------------------

If you're just interested in numbers for 18 clue puzzles ...

About 5 years ago now, I ran a modified version of Gary McGuire's "checker16" code, to try to get an estimate for 18's ... and never published the results. I ended up sampling 100,000 grids -- far more than I had planned -- before the error estimates got down to a range that I was comfortable with. It took ~2 months. I didn't publish the results, because I was too embarassed and angry at myself, over spending so much time on it.

I've lost the grid list and "found" puzzle output, it seems, but I finally found the "statistics" data in one of my backups.
This is the "raw data" ... what's left of it: (grids with N puzzles, for the "seen" values of N)

Hidden Text: Show
Code: Select all
`ED puzzles |   grids-----------+--------         0 |   82306         1 |   10876         2 |    3359         3 |    1483         4 |     698         5 |     421         6 |     235         7 |     169         8 |     109         9 |      83        10 |      63        11 |      34        12 |      40        13 |      18        14 |      25        15 |      14        16 |      11        17 |       6        18 |       6        19 |       6        20 |       3        21 |       5        22 |       4        23 |       1        25 |       2        26 |       2        27 |       3        28 |       1        30 |       1        31 |       3        32 |       1        34 |       2        44 |       1        45 |       2        46 |       1        52 |       1        70 |       1        75 |       1        82 |       1        87 |       1       152 |       1-----------+--------           |  100000  grid samples           | - 82306  ("no 18" count)           +--------           | = 17694  "grids with an 18" samples`

These are some of the results that can be calculated, based on that:
(with 95% confidence levels for the error estimates)

Code: Select all
`Avg. Puzzles per grid:  0.3534 +/- 0.0086Total puzzles        : (1.9340 +/- 0.0468) * 10^9Probablility(grid has 18):  (17.69 +/- 0.24)%Total grids with an 18   : (0.9683 +/- 0.0129) * 10^9Avg. Puzzles per "grid with an 18":  1.9972 +/- 0.0403`
blue

Posts: 894
Joined: 11 March 2013

### Re: Solution grids with higher potential to have 17-clue puz

Speaking of spending too much time on things ...

I've completed 17-clue testing for the 1,239,360 grids with "MCB=9" (bands & stacks partitioning method) ... and nothing new came of it.
blue

Posts: 894
Joined: 11 March 2013

### Re: Solution grids with higher potential to have 17-clue puz

blue wrote:About 5 years ago now, I ran a modified version of Gary McGuire's "checker16" code, to try to get an estimate for 18's ...

Good work.
A possible continuation of this work is finding a distribution law as well as its parameters and assumptions so that it fits the raw data and predicts 46301 grids each having 64 18s that differ by a single given.
blue wrote:I've completed 17-clue testing for the 1,239,360 grids with "MCB=9"

Hmm, this smells to processing more than one grid at a time. Did you use the non-McGuire's method?
dobrichev
2016 Supporter

Posts: 1827
Joined: 24 May 2010

### Re: Solution grids with higher potential to have 17-clue puz

dobrichev wrote:A possible continuation of this work is finding a distribution law as well as its parameters and assumptions so that it fits the raw data and predicts 46301 grids each having 64 18s that differ by a single given.

Yeah ...
That reminds me though, what I listed as "ED puzzles", were the non-minimal puzzles only.
One of the 100,000 grids, had a 17 (and no doubt, some minimal 18's too).

dobrichev wrote:
blue wrote:I've completed 17-clue testing for the 1,239,360 grids with "MCB=9"

Hmm, this smells to processing more than one grid at a time. Did you use the non-McGuire's method?

Yes, non-McGuire method ... yes and no, on more then one grid at a time.

I made the list of "27+x+y" inputs that would cover the MCB<=9 and MC54<=9 grids, planning to run the both passes on them [ (x+y<=10) and {x,y}={5,6} ]. It was ~6M inputs, instead of ~7.6M, so some of the inputs covered (parts of) more than one grid. Also, some grids, not in the original list, would be gettting partial coverage.
The (x+y<=10) pass went off OK, producing ~1900 17's ... all known. The {5,6} pass was going to take about twice as long as running the original list of grids, in "single grid mode" ... ~20 days with 3 cores running. I went with single grid mode, and only ran the MCB=9 cases (minus the 250 grids with known 17's).
I've been thinking now, that due to "transposes", the {5,6} mode probably didn't need all 6M inputs to cover the grids that were of interest.
I might look into that, and think about trying it again. It still seems like another 10+ days, though.
blue

Posts: 894
Joined: 11 March 2013

### Re: Solution grids with higher potential to have 17-clue puz

20 days * 3 cores / 1,239,360 grids = 4.18 seconds per grid on Earth or 1016 sec/grid on Venus. You mentioned cooling problems...

Or, do you achieved such performance in single grid mode by adding a filter for ignoring distributions different than 6+6+5 clues in both bands and stacks?
dobrichev
2016 Supporter

Posts: 1827
Joined: 24 May 2010

### Re: Solution grids with higher potential to have 17-clue puz

Late sleepers there too, on Venus ... "first thing in the morning" ... right.

dobrichev wrote:Or, do you achieved such performance in single grid mode by adding a filter for ignoring distributions different than 6+6+5 clues in both bands and stacks?

There's some code that keeps an eye out for that, but it only saves a percent or two on the timing.

Actually, the 20 days would have been for the non-single-grid mode.
The single grid timing (for MCB=9 grids) was ~2.59s/g ... ~8.2 times as long as for random grids.

I had been running the {5,6} part of the single grid mode, on and off in the background, over a couple of weeks, and had about 20% of it covered, and really no plans to let it finish. I never got around to it, but I was thinking I'ld run the (x+y<=10) mode for a while too, just to see if anything new came.
It wasn't until I finished the "5+4 boxes" job, that I started thinking about merging things up, and running in the normal mode.
At that point, it was going to take 10 days to finish the 6/5 part for MCB=9, in single grid mode, and 20 if I started over in the normal mode.
For "x+y<=10" mode, the situation was reversed -- 5 days in single grid mode -vs- 3.8 in the normal mode, with the "bonus" partial coverage for other grids. I checked that bit first, and had high hopes (for a short time) ... that the 6/5 mode would be similar.

Blah blah blah ... sometimes I talk too much.
Cheers.
blue

Posts: 894
Joined: 11 March 2013

### Re: Solution grids with higher potential to have 17-clue puz

Are you saying that you improved the universal single grid scan for 17s method so that it takes 0.35 seconds per grid in average?
This is 61 CPU years for the entire catalog. And all these topics are obsolete.
dobrichev
2016 Supporter

Posts: 1827
Joined: 24 May 2010

### Re: Solution grids with higher potential to have 17-clue puz

About 0.315s for the 2x(6/6/5) part, and 0.141s for the other part -- for ~79 years total.
blue

Posts: 894
Joined: 11 March 2013

### Re: Solution grids with higher potential to have 17-clue puz

I am confused.
Is "2x(6/6/5) part" actually 2x[(6/6/5)+(6/5/6)+(5/6/6)]?
And same for the "other" part?
Could you confirm that these timings are for per-grid processing - if I take 1000 random grids and check them is it expected the process would take about 1000*(0.315+0.141)=456 seconds?
dobrichev
2016 Supporter

Posts: 1827
Joined: 24 May 2010

Next