The New Sudoku Players' Forum

[dobrichev]

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

*** *** ***
*** *** ***
*** *** ***

Sources:

• The catalog of 5472730538 solution grids was generated by Glenn Fowler's tool. http://gsf.cococlyde.org/.
• The catalog of known 17-clue puzzles, collected by Gordon Royle. The original database is now dead, my mirror is https://sites.google.com/site/dobrichev/sudoku-puzzle-collections
• UA statistics are my own work from 2010. They were previously published in the now dead Sudoku Programmers Forum. Some of the data as well as the software used are in https://sites.google.com/site/dobrichev/sudokugrids
• Types of UA6 are from Gary McGuire's source of the old version of checker, http://www.math.ie/checkerold.html
• Bands processing is Blue's work published in http://forum.enjoysudoku.com/post268200.html#p268200
• Templates processing is my own work published in http://forum.enjoysudoku.com/post268759.html#p268759
• Boxes 12347+5689 processing is Blue's work, see the next post http://forum.enjoysudoku.com/post268774.html#p268774

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 2490 times

[blue]

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:   879381
6: 12332250
7:  4822691
8:   258236
9:     3449

B5689 MinClues distribution (for the 5699915 canonical forms)
2:       44
3:   553591
4:  4603035
5:   527258
6:    15701
7:      284
8:        1
9:        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.

[dobrichev]

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.

[blue]

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.

[dobrichev]

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.

[coloin]

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 forms
B5689  -  5699915 canonical forms

[blue]

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.0086
Total puzzles        : (1.9340 +/- 0.0468) * 10^9

Probablility(grid has 18):  (17.69 +/- 0.24)%
Total grids with an 18   : (0.9683 +/- 0.0129) * 10^9

Avg. Puzzles per "grid with an 18":  1.9972 +/- 0.0403

[blue]

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.

[dobrichev]

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.

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?

[blue]

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

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.

[dobrichev]

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?

[blue]

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

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.

[dobrichev]

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.

[blue]

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

[dobrichev]

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?