The New Sudoku Players' Forum

by **Mathimagics** » Fri Nov 22, 2019 5:58 am

Hi Serg,

Serg wrote:Do you mean that each line in the table above represents number of ED grids, for which minimal number of clues in valid puzzles is equal to 17C, 18C, etc?

Not exactly. Let's look at the current grid status table, adding column KM = "Known Min" (ie. there is no puzzle with less clues):

Code: Select all: Grids Known Min --------------------------- 17C: 46301 46301 18C: 219375245 19C: 5253040692 59242 20C: 268296 268296 21C: 4 4 ---------------------- 5472730538 373843

The status for each category:

17C: all are KM, since it is known that there are no 16C puzzles

18C: we can't know for sure that any of these are KM until such time as we complete LCT-17 (blue's rigorous 17C search)

19C: we know that 59242 are KM because they have been tested with blue's rigorous Find18C function. The number is small because this is an expensive test (~4s per grid). But for all other grids we don't yet know the KM status.

20C: we know that every one of these grids has no 19C or less puzzle

21C: we know that every one of these grids has no 20C or less puzzle

For 19C grids, we keep a KM status indicator, that gets set whenever we explicitly test that grid with Find18C and find no 18C. If we do find an 18C puzzle, the 19C catalog record is converted into an 18C entry.

We don't have a KM flag for 18C grids, because we don't have an explicit Find17C test. But LCT-17, on completion, will have identified any remaining 17C's. Then we can say that any catalog entry of type 18C is definitely KM.

The big "black hole" we are left with after LCT-17 completes will be the ~5 billion 19C grids for which we can't be sure are KM until such time as they are explicitly tested, OR we come up with an efficient way to identify ALL 18C grids.

Cheers,
Jim

by **Serg** » Fri Nov 22, 2019 9:04 am

Hi, Mathimagics!
Thank you for clarification. Very complicated project, very ambitious goals! And great results already found! I mean exhaustive searches for 21C and 20C.
Well done!

Serg

by **Mathimagics** » Sun Nov 24, 2019 1:47 pm

Results for recent batches produced by LCT-18 workers:

Code: Select all: Date Batches ED grids New grids Yield Total 18C -------------------------------------------------------------------------- 22 Nov 2019 81 - 96 15,674,304 5,359,776 34.19% 23 Nov 2019 97 - 112 15,563,744 5,379,546 34.56% 23 Nov 2019 113 - 128 15,740,306 5,202,150 33.05% 24 Nov 2019 129 - 144 15,667,837 5,061,052 32.30% 236,494,782 25 Nov 2019 (Colin) 3,687,978 1,157,767 31.39% 237,652,549 25 Nov 2019 145 - 160 15,623,621 4,941,106 31.63% 242,593,655

[EDIT] this means we have found ~25% of the predicted 968 million (+/- 13 million) 18C grids.

by **Mathimagics** » Sat Dec 07, 2019 9:19 am

Results for recent batches produced by LCT-18 workers:

Code: Select all: Date Batches ED grids New grids Yield ------------------------------------------------------------- 25 Nov 2019 161 - 176 15,667,897 4,692,544 29.95% 26 Nov 2019 177 - 192 15,737,238 4,565,802 29.01% 28 Nov 2019 193 - 208 15,673,691 4,348,479 27.74% 28 Nov 2018 209 - 224 15,685,814 4,480,898 28.57% 29 Nov 2019 225 - 240 15,562,115 4,183,054 26.88% 30 Nov 2019 241 - 256 15,761,383 4,291,692 27.23% 01 Dec 2019 257 - 272 15,751,756 4,246,077 26.96% 02 Dec 2019 273 - 288 15,701,212 4,020,863 25.61% 02 Dec 2019 289 - 304 15,660,397 3,864,569 24.68% 03 Dec 2019 305 - 320 15,668,936 3,888,474 24.82% 04 Dec 2019 321 - 336 15,689,167 3,617,314 23.06% 05 Dec 2019 337 - 352 15,578,272 3,674,002 23.58% 05 Dec 2019 353 - 368 15,703,846 3,610,967 22.99% 06 Dec 2019 369 - 384 15,622,537 3,521,177 22.54% 07 Dec 2019 385 - 400 15,791,640 3,512,622 22.24%

Total 18C grids found = 310,062,298

by **Mathimagics** » Tue Dec 31, 2019 7:31 am

Batches produced by Gen18H since the last post:

Hidden Text: Show

Together with coloin's contributions for the same period (~25 million new grids), the total 18C grid count is now 402,552,192.

by **Mathimagics** » Sat Feb 01, 2020 7:30 am

Batches/yields for the past month:

Hidden Text: Show

Net yields are now down to ~9%. And I have had to cut down the number of worker processes from 22 to 16, due to the alarming power consumption revealed by our recent electricity bills!

The total grid count is now 466,504,364, so we have about 48% of blue's estimate of 968 million.

coloin has made a very interesting discovery, namely that, for an 18C puzzle, a fast way to run a limited search of the {-2, +2} vicinity is this:

choose the clue with the least # of 17C solutions (ie # of solutions with that clue removed)

search this 17C puzzle with {-1, +2}

This procedure will generally identify the clue with the highest {-2, +2} yield (or close), but is 15 times faster than the full {-2, +2} search.

Can this lead to a Gen18C process with a better yield? We are investigating this ...

by **Mathimagics** » Wed Feb 05, 2020 9:08 am

I have completed the initial round of tests of Gen18Z, which is a worker process that is based on coloin's "selective {-2, +2}" search method, as outlined above.

First a quick review of the existing process, Gen18H. This uses random morphing of 19C puzzles, "Harvesting" any puzzles with redundant clues which gives us 18C puzzles. This has been the main source of new 18C grids over the past few months.

16 worker processes are running on JACK (my 16-core PC), and currently their output is a steady 15.5 million ED grids every 22 hours on average. The percentage of these grids that are found to be new (ie: no 18C already found) is currently about 9%, and this %yield is slowly decreasing. We have found about half of the likely total of 18C grids so far.

Averaging by worker-hours, the current Gen18H workers thus produce about 44,000 ED grids/hour (GPH), of which ~4,000 are new grids (NPH). So absolute progress is measured by NPH, the number of new grids per worker-hour. But the %yield (NPH v GPH) is still of interest, since any method that provides higher %yields, even at lower production levels (NPH), is of interest when we consider the task ahead (the 50% of 18C grids that are not yet found).

An overview of Gen18Z:

Seed generation: select a random grid from the catalog, one for which 19-clues is the best known result. Use blue's Find18C function to test it for 18C. If this function fails, mark the grid as "No 18C" (so it doesn't get selected again) and try another grid.

List propagation: use the selective {-2,+2} method to enumerate new 18C puzzles. Collect any new puzzles for list propagation in a subsequent pass. Repeat this process until no new puzzles found (closure), or until some operational limit is reached.

List reduction: reduce the collection to one puzzle per ED grid, save this list as a new batch.

The cost of selective {-2,+2} enumeration is still relatively expensive - on average 2s per puzzle (full {-2,+2} enumeration costs 40-60s per puzzle). The main parameter used to limit the list propagation is a limit on the number of puzzles to be {-2,+2} tested (NTEST). Evidence suggests that, when the list propagation is self-sustaining, pursuing additional passes leads ultimately to diminishing new grid yields.

The first round of tests was done with NTEST = 2000, but this was applied within each propagation pass, so the batch times (where propagation was self-sustaining) vary from 1 to 3 hours. In future tests NTEST will specify the absolute total limit, and the batch times should then be fairly constant.

The first test results are shown below. Each batch corresponds to a single seed grid, and the entry lists the time (in minutes), the #of ED grids (ed), and the # of new grids (ng). For grids with sustained propagation, the %yield and approximate NPH value are shown.

Hidden Text: Show

Code: Select all: Batch 6: 72.17m, ed = 30505, ng = 2773 9.09%, nph = 2305 Batch 7: 72.58m, ed = 15688, ng = 2541 16.20%, nph = 2100 Batch 8: 0.95m, ed = 1, ng = 1 Batch 9: 3.43m, ed = 6, ng = 5 Batch 10: 88.02m, ed = 27553, ng = 5019 18.22%, nph = 3421 Batch 11: 72.48m, ed = 21985, ng = 4534 20.62%, nph = 3753 Batch 12: 81.02m, ed = 32247, ng = 1741 5.40%, nph = 1289 Batch 13: 89.85m, ed = 17804, ng = 3549 19.93%, nph = 2370 Batch 14: 0.52m, ed = 2, ng = 2 Batch 15: 1.62m, ed = 1, ng = 1 Batch 16: 4.23m, ed = 1, ng = 1 Batch 17: 62.02m, ed = 30106, ng = 1274 4.23%, nph = 1233 Batch 18: 0.40m, ed = 2, ng = 1 Batch 19: 87.97m, ed = 22280, ng = 4605 20.67%, nph = 3141 Batch 20: 0.53m, ed = 1, ng = 1 Batch 21: 149.50m, ed = 42468, ng = 5435 12.80%, nph = 2181 Batch 22: 0.28m, ed = 1, ng = 1 Batch 23: 150.08m, ed = 13952, ng = 3575 25.62%, nph = 1429 Batch 24: 102.67m, ed = 31270, ng = 4931 15.77%, nph = 2882 Batch 25: 0.53m, ed = 1, ng = 1 Batch 26: 1.45m, ed = 3, ng = 1 Batch 27: 26.53m, ed = 7738, ng = 1357 17.54%, nph = 3069 Batch 28: 111.70m, ed = 36821, ng = 4761 12.93%, nph = 2557 Batch 29: 88.75m, ed = 23078, ng = 3303 14.31%, nph = 2233 Batch 30: 90.95m, ed = 34722, ng = 2971 8.56%, nph = 1960 Batch 31: 109.37m, ed = 34143, ng = 4979 14.58%, nph = 2732 Batch 32: 138.78m, ed = 28961, ng = 4914 16.97%, nph = 2124 Batch 33: 0.45m, ed = 1, ng = 1 Batch 34: 67.65m, ed = 29880, ng = 2274 7.61%, nph = 2017 Batch 35: 74.35m, ed = 25248, ng = 2796 11.07%, nph = 2256 Batch 36: 18.23m, ed = 6068, ng = 852 14.04%, nph = 2804 Batch 37: 0.08m, ed = 1, ng = 1 Batch 38: 59.48m, ed = 21516, ng = 2459 11.43%, nph = 2480 Batch 39: 0.35m, ed = 1, ng = 1 Batch 40: 68.98m, ed = 16019, ng = 2444 15.26%, nph = 2126 Batch 41: 118.82m, ed = 24434, ng = 5900 24.15%, nph = 2979 Batch 42: 65.78m, ed = 38504, ng = 1962 5.10%, nph = 1790 Batch 43: 0.20m, ed = 1, ng = 1 Batch 44: 0.97m, ed = 1, ng = 1 Batch 45: 0.42m, ed = 1, ng = 1 Batch 46: 0.40m, ed = 1, ng = 1 Batch 47: 1.98m, ed = 1, ng = 1 Batch 48: 98.65m, ed = 26657, ng = 5507 20.66%, nph = 3349 Batch 49: 108.95m, ed = 27484, ng = 5900 21.47%, nph = 3249 Batch 50: 0.77m, ed = 1, ng = 1 Batch 51: 92.22m, ed = 28282, ng = 4257 15.05%, nph = 2770 Batch 52: 73.95m, ed = 15872, ng = 3704 23.34%, nph = 3005 Batch 53: 71.78m, ed = 21817, ng = 2483 11.38%, nph = 2075 Batch 54: 92.82m, ed = 28393, ng = 3639 12.82%, nph = 2352 Batch 55: 93.12m, ed = 14793, ng = 4232 28.61%, nph = 2727 ------------------------------------------------------------------ Total : 2718.78m, ed = 776316, ng = 110695 14.26%, nph = 2443

As you can see, 1 in every 3 grids "failed", ie didn't result in any sustained {-2,+2} propagation. The selective {-2,+2} enumeration tends to favour the most productive cases, but this is by no means guaranteed. In the next round of tests I will make a complete {-2,+2} enumeration of the initial seed puzzle, and we will see if that reduces the "failed" cases.

On the surface, it would appear that the NPH rates (average ~2200) are much less than the current Gen18H workers. But encouragement is found in the incidence of %yields that are often much higher. This (hopefully) suggests that this method will ultimately be more effective in finding "remote" 18C grids.

by **Mathimagics** » Wed Feb 05, 2020 6:01 pm

Mathimagics wrote:As you can see, 1 in every 3 grids "failed", ie didn't result in any sustained {-2,+2} propagation. The selective {-2,+2} enumeration tends to favour the most productive cases, but this is by no means guaranteed. In the next round of tests I will make a complete {-2,+2} enumeration of the initial seed puzzle, and we will see if that reduces the "failed" cases.

There were 19 cases in the initial test set that failed to propagate. After re-running them with full {-2,+2} enumeration (for the seed puzzle) worked for 13 of them:

Code: Select all: Batch 56: 0.37m, ed = 3, ng = 2 Batch 57: 61.58m, ed = 27103, ng = 2342 8.64%, nph = 2282 Batch 58: 61.95m, ed = 16404, ng = 851 5.19%, nph = 824 Batch 59: 59.55m, ed = 13365, ng = 2777 20.78%, nph = 2798 Batch 60: 68.88m, ed = 15830, ng = 2577 16.28%, nph = 2245 Batch 61: 0.35m, ed = 1, ng = 1 Batch 62: 0.38m, ed = 4, ng = 4 Batch 63: 0.47m, ed = 3, ng = 1 Batch 64: 0.42m, ed = 2, ng = 2 Batch 65: 56.50m, ed = 30360, ng = 2180 7.18%, nph = 2315 Batch 66: 59.58m, ed = 33299, ng = 981 2.95%, nph = 988 Batch 67: 61.07m, ed = 22795, ng = 2821 12.38%, nph = 2772 Batch 68: 65.42m, ed = 21196, ng = 1581 7.46%, nph = 1450 Batch 69: 61.23m, ed = 31343, ng = 2054 6.55%, nph = 2013 Batch 70: 64.28m, ed = 15176, ng = 1986 13.09%, nph = 1854 Batch 71: 71.83m, ed = 30011, ng = 2652 8.84%, nph = 2215 Batch 72: 0.35m, ed = 1, ng = 1 Batch 73: 73.45m, ed = 11693, ng = 2516 21.52%, nph = 2055 Batch 74: 56.88m, ed = 26949, ng = 2033 7.54%, nph = 2144 ------------------------------------------------------------------ Total : 824.55m, ed = 295538, ng = 27362 9.26%, nph = 1991

by **coloin** » Thu Feb 06, 2020 7:12 pm

Pretty good ....we are half way !!
An excellent effort I think !!

But the fast gen19c continues for now on my PC ...
Interesting that some of the yields are up [24% wow !] , and i suppose that when you get into "non-remote / already found" territory thats when the yield will plummet....

I mentioned that perhaps a selective selective {-1,-1+2}might be the way.
When one removes the best [least sol] clue of the 18 - the number of sols determines the remoteness to an extent .
Instead of trying to process every seed - if we are selective and only process those seeds which have a highish eg 100 sol - maybe this will tend to keep us out of the non-remote/already found territory.
There wont be so many puzzles made however ...

by **Mathimagics** » Fri Feb 07, 2020 8:49 am

coloin wrote:Instead of trying to process every seed - if we are selective and only process those seeds which have a highish eg 100 sol - maybe this will tend to keep us out of the non-remote/already found territory.
There wont be so many puzzles made however ...

This might work, the trouble is that testing it is tricky and time-consuming. Perhaps an option to keep up our sleeve for when the search really gets difficult ...

Meanwhile, some good news, I think!

I have found a bug in blue's PM1 code. He only searched 1/2 of the possible puzzles. Even with this fixed, it is still 4x faster than my version.

For current workers (Gen18H) the impact will be slightly slower morph test times, but higher yields ultimately ... we will see in a few days time when the new version has generated a few batch sets.

For Gen18Z this could also be significant - if I can make a {-1,+2} version of blue's PM1 code, it should be much faster than the current version!

by **Mathimagics** » Fri Feb 07, 2020 12:30 pm

Results for a full days work for 4 workers running Gen18Z. Note in particular the results for batches #1010, #1046 and #1075.

Hidden Text: Show

Code: Select all: Batch 1001: 59.08m, ed = 16920, ng = 3259 19.26%, nph = 3310 Batch 1002: 0.67m, ed = 4, ng = 3 Batch 1003: 62.55m, ed = 30280, ng = 1733 5.72%, nph = 1662 Batch 1004: 63.67m, ed = 29866, ng = 1933 6.47%, nph = 1822 Batch 1005: 68.37m, ed = 10541, ng = 2890 27.42%, nph = 2536 Batch 1006: 61.43m, ed = 20340, ng = 2297 11.29%, nph = 2243 Batch 1007: 63.80m, ed = 20929, ng = 2979 14.23%, nph = 2802 Batch 1008: 62.40m, ed = 13572, ng = 2535 18.68%, nph = 2437 Batch 1009: 73.37m, ed = 11542, ng = 2768 23.98%, nph = 2264 Batch 1010: 65.45m, ed = 11528, ng = 3923 34.03%, nph = 3596 ** Batch 1011: 70.12m, ed = 15763, ng = 2799 17.76%, nph = 2395 Batch 1012: 63.97m, ed = 30717, ng = 1685 5.49%, nph = 1581 Batch 1013: 68.75m, ed = 14773, ng = 4078 27.60%, nph = 3559 Batch 1014: 61.05m, ed = 25847, ng = 2318 8.97%, nph = 2278 Batch 1015: 63.85m, ed = 26679, ng = 2114 7.92%, nph = 1987 Batch 1016: 64.90m, ed = 14304, ng = 2020 14.12%, nph = 1867 Batch 1017: 70.27m, ed = 20854, ng = 2209 10.59%, nph = 1886 Batch 1018: 72.07m, ed = 23015, ng = 1858 8.07%, nph = 1547 Batch 1019: 73.08m, ed = 7568, ng = 2630 34.75%, nph = 2159 Batch 1020: 84.33m, ed = 21352, ng = 3201 14.99%, nph = 2277 Batch 1021: 90.77m, ed = 23804, ng = 2870 12.06%, nph = 1897 Batch 1022: 64.30m, ed = 47674, ng = 993 2.08%, nph = 927 Batch 1023: 59.53m, ed = 13135, ng = 3350 25.50%, nph = 3376 Batch 1024: 70.25m, ed = 19441, ng = 3440 17.69%, nph = 2938 Batch 1025: 2.68m, ed = 1, ng = 1 Batch 1026: 74.27m, ed = 16160, ng = 2887 17.87%, nph = 2332 Batch 1027: 58.82m, ed = 19746, ng = 1751 8.87%, nph = 1786 Batch 1028: 56.75m, ed = 19654, ng = 2143 10.90%, nph = 2266 Batch 1029: 0.38m, ed = 2, ng = 2 Batch 1030: 61.58m, ed = 22378, ng = 2796 12.49%, nph = 2724 Batch 1031: 67.88m, ed = 15049, ng = 1895 12.59%, nph = 1675 Batch 1032: 60.55m, ed = 12082, ng = 2775 22.97%, nph = 2750 Batch 1033: 65.12m, ed = 15908, ng = 2930 18.42%, nph = 2700 Batch 1034: 67.50m, ed = 24119, ng = 2099 8.70%, nph = 1866 Batch 1035: 71.18m, ed = 18125, ng = 2010 11.09%, nph = 1694 Batch 1036: 61.35m, ed = 18588, ng = 1894 10.19%, nph = 1852 Batch 1037: 64.65m, ed = 13693, ng = 2027 14.80%, nph = 1881 Batch 1038: 60.50m, ed = 20083, ng = 2563 12.76%, nph = 2542 Batch 1039: 1.60m, ed = 1, ng = 1 Batch 1040: 0.70m, ed = 4, ng = 3 Batch 1041: 64.88m, ed = 14322, ng = 2139 14.94%, nph = 1978 Batch 1042: 59.75m, ed = 21896, ng = 1491 6.81%, nph = 1497 Batch 1043: 59.95m, ed = 26806, ng = 2277 8.49%, nph = 2279 Batch 1044: 62.00m, ed = 16952, ng = 2232 13.17%, nph = 2160 Batch 1045: 66.87m, ed = 28922, ng = 2395 8.28%, nph = 2149 Batch 1046: 65.85m, ed = 13883, ng = 4455 32.09%, nph = 4059 ** Batch 1047: 57.12m, ed = 28021, ng = 1737 6.20%, nph = 1825 Batch 1048: 62.85m, ed = 18968, ng = 2459 12.96%, nph = 2347 Batch 1049: 61.78m, ed = 18244, ng = 4362 23.91%, nph = 4236 Batch 1050: 67.02m, ed = 14123, ng = 3129 22.16%, nph = 2801 Batch 1051: 59.77m, ed = 19337, ng = 2549 13.18%, nph = 2559 Batch 1052: 59.30m, ed = 10634, ng = 3479 32.72%, nph = 3520 Batch 1053: 61.68m, ed = 30788, ng = 1334 4.33%, nph = 1298 Batch 1054: 64.32m, ed = 22325, ng = 1828 8.19%, nph = 1705 Batch 1055: 63.37m, ed = 23236, ng = 2100 9.04%, nph = 1988 Batch 1056: 57.90m, ed = 20702, ng = 1838 8.88%, nph = 1905 Batch 1057: 61.27m, ed = 18394, ng = 3496 19.01%, nph = 3424 Batch 1058: 63.65m, ed = 27558, ng = 1907 6.92%, nph = 1798 Batch 1059: 61.62m, ed = 15268, ng = 3512 23.00%, nph = 3420 Batch 1060: 60.45m, ed = 27807, ng = 2125 7.64%, nph = 2109 Batch 1061: 61.17m, ed = 17146, ng = 2530 14.76%, nph = 2482 Batch 1062: 1.47m, ed = 2, ng = 2 Batch 1063: 63.37m, ed = 18771, ng = 3108 16.56%, nph = 2943 Batch 1064: 58.15m, ed = 16950, ng = 3260 19.23%, nph = 3364 Batch 1065: 65.28m, ed = 15011, ng = 2336 15.56%, nph = 2147 Batch 1066: 71.33m, ed = 24450, ng = 2958 12.10%, nph = 2488 Batch 1067: 72.12m, ed = 16644, ng = 2719 16.34%, nph = 2262 Batch 1068: 66.08m, ed = 23515, ng = 2376 10.10%, nph = 2157 Batch 1069: 71.47m, ed = 20407, ng = 2442 11.97%, nph = 2050 Batch 1070: 59.93m, ed = 21242, ng = 2579 12.14%, nph = 2582 Batch 1071: 58.95m, ed = 16445, ng = 2988 18.17%, nph = 3041 Batch 1072: 0.43m, ed = 2, ng = 1 Batch 1073: 67.63m, ed = 23913, ng = 2379 9.95%, nph = 2110 Batch 1074: 65.97m, ed = 9443, ng = 2984 31.60%, nph = 2714 Batch 1075: 57.95m, ed = 14226, ng = 4454 31.31%, nph = 4612 *** Batch 1076: 1.03m, ed = 2, ng = 2 Batch 1077: 65.28m, ed = 13405, ng = 1975 14.73%, nph = 1815 Batch 1078: 0.75m, ed = 2, ng = 2 Batch 1079: 57.00m, ed = 16929, ng = 2411 14.24%, nph = 2538 Batch 1080: 2.10m, ed = 7, ng = 6 Batch 1081: 58.88m, ed = 14224, ng = 2280 16.03%, nph = 2323 Batch 1082: 58.22m, ed = 13671, ng = 3374 24.68%, nph = 3477 Batch 1083: 58.57m, ed = 17531, ng = 3227 18.41%, nph = 3306 Batch 1084: 73.47m, ed = 20985, ng = 1391 6.63%, nph = 1136 Batch 1085: 69.27m, ed = 13139, ng = 3038 23.12%, nph = 2632 Batch 1086: 0.80m, ed = 1, ng = 1 Batch 1087: 73.58m, ed = 24306, ng = 1344 5.53%, nph = 1096 Batch 1088: 71.98m, ed = 16619, ng = 2038 12.26%, nph = 1699 Batch 1089: 74.90m, ed = 26037, ng = 2135 8.20%, nph = 1710 Batch 1090: 74.48m, ed = 33400, ng = 1458 4.37%, nph = 1174 Batch 1091: 67.58m, ed = 21166, ng = 3014 14.24%, nph = 2676 Batch 1092: 71.38m, ed = 27184, ng = 2736 10.06%, nph = 2300 Batch 1093: 65.72m, ed = 19549, ng = 1887 9.65%, nph = 1723 ------------------------------------------------------------------ Total : 5361.22m, ed =1620551, ng = 207941 12.83%, nph = 2327

If we can reduce the cost of doing the {-1,+2} tests, this could be really prove to be a gun method!

by **coloin** » Fri Feb 07, 2020 3:29 pm

Well that is progress !!!
Is each batch from a single 17C subpuzzle ?

by **Mathimagics** » Fri Feb 07, 2020 4:07 pm

Each batch begins with single 18C seed puzzle. This is always a new grid - I use Blue's Find18C function to get this puzzle, and only look at grids that aren't already known to have an 18C, or known NOT to have one.

For the seed puzzle I do a complete enumeration of {-2, +2}. As I explained above, although this takes 40-60 seconds, it is worth the effort because it picks up many cases where the selective ("best 17C subpuzzle") enumeration would not otherwise find anything to propagate.

All of the {-2, +2} tests except for this first one are done in selective mode (ie via the "best17C subpuzzle").

========================================

ListSPC.zip: (65.87 KiB) Downloaded 221 times

Sub-Puzzle Count tool: a sub-puzzle is a given puzzle with 1 clue removed. This tool takes a puzzle, and removes the clue with the lowest subpuzzle solution count.

Code: Select all: > ListSPC 1.3........6.....2.....254.......6....7..8........4..5.9..6.....7.....2.....1.3.. 1.3........6.....2.....254.......6.......8........4..5.9..6.....7.....2.....1.3..

A file of puzzles can be used:

Code: Select all: > ListSPC Test18C.txt

The tool can also list all sub-puzzle solution counts for a given puzzle. Example:

Code: Select all: c:> ListSPC -x 1.3........6.....2.....254.......6....7..8........4..5.9..6.....7.....2.....1.3.. Puzzle has 18 clues Clue 01 = 1: solns = 22468 Clue 03 = 3: solns = 52738 Clue 12 = 6: solns = 92137 Clue 18 = 2: solns = 1147 Clue 24 = 2: solns = 187609 Clue 25 = 5: solns = 5944 Clue 26 = 4: solns = 158243 Clue 34 = 6: solns = 35139 Clue 39 = 7: solns = 45 Clue 42 = 8: solns = 17870 Clue 51 = 4: solns = 38394 Clue 54 = 5: solns = 788 Clue 56 = 9: solns = 1677 Clue 59 = 6: solns = 110334 Clue 65 = 7: solns = 5249 Clue 71 = 2: solns = 5047 Clue 77 = 1: solns = 7598 Clue 79 = 3: solns = 3523

by **Mathimagics** » Sun Feb 09, 2020 9:33 am

Ok, one more day of batch testing for the new Gen18Z process.

I finally understand exactly what blue's {-1,+1} code does, and the principle is quite simple. For each subpuzzle ie {-1}, we test all the {+1} candidates, in the usual fashion. But we also keep a list of distinct solutions, and by using clever bitmasking, we can ask whether a value D has occurred in cell CN in some solution already found, and whether this has occurred twice.

So when we come to testing CN = D, we can skip this solver call if we know that CN = D has occurred twice in the solution list for this {-1} subpuzzle. This reduces the solver calls by roughly half.

When blue first gave me this code, the puzzle generation time was in fact reduced by a factor of ~4, not 2. It turns out he had a bug in the outer loop, he only added clue values to the right of the {-1} clue, and ignored the possibilities to the left. I only found this by comparing his code with mine on a per-puzzle basis, and noticed that I was finding more {-1,+1} puzzles.

And what about the impact of this on Gen18H yields? Fixing the bug certainly had the expected slowdown of the process, as it takes on average of 31 hours to produce a batch in "full-search mode", compared to just 22 hours previously. Sadly, however, this didn't translate to any noticable increased grid %yield, so the absolute yield (NPH) is greatly reduced!

The bottom line is that Gen18H, which is basically {-1,+1} processing throughout, runs best in "half-search mode"!

===============================================

Ok, we will return to this issue later on. For Gen18Z we take a 17-clue puzzle and do a {-1, +2} search. For each {-1} we need to add 2 clues at a time, and it is not a simple matter to translate blue's method into 2 clue mode. But we can use it in a simple outer loop as follows:

for each possible 18c puzzle corresponding to the 17-clue base puzzle plus 1 added clue, do a (blue) {-1, +1} search

Using this approach has the desired effect, reducing batch generation time by ~40%, and thus to improved NPH results. This set of batch results shows avg NPH = 3880 over a day's work. (A couple of batches, 1201 + 1202, show %yields of 50% !!)

Hidden Text: Show

Code: Select all: Batch 1102: 38.77m, ed = 27473, ng = 2626 9.56%, nph = 4064 Batch 1103: 43.67m, ed = 19627, ng = 1649 8.40%, nph = 2266 Batch 1104: 46.15m, ed = 19737, ng = 2981 15.10%, nph = 3876 Batch 1105: 46.53m, ed = 19737, ng = 2981 15.10%, nph = 3844 Batch 1106: 0.78m, ed = 3, ng = 2 Batch 1107: 0.65m, ed = 3, ng = 2 Batch 1108: 44.73m, ed = 14982, ng = 4845 32.34%, nph = 6499 Batch 1109: 42.68m, ed = 19845, ng = 2507 12.63%, nph = 3524 Batch 1110: 42.78m, ed = 19845, ng = 2507 12.63%, nph = 3516 Batch 1111: 46.63m, ed = 12294, ng = 3490 28.39%, nph = 4490 Batch 1112: 40.48m, ed = 49518, ng = 1136 2.29%, nph = 1684 Batch 1113: 40.02m, ed = 20755, ng = 1930 9.30%, nph = 2894 Batch 1114: 0.45m, ed = 2, ng = 1 Batch 1115: 42.27m, ed = 18436, ng = 3010 16.33%, nph = 4273 Batch 1116: 42.50m, ed = 18436, ng = 3010 16.33%, nph = 4249 Batch 1117: 42.30m, ed = 14262, ng = 4058 28.45%, nph = 5756 Batch 1118: 46.57m, ed = 49412, ng = 1930 3.91%, nph = 2487 Batch 1119: 54.63m, ed = 18118, ng = 3708 20.47%, nph = 4072 Batch 1120: 55.03m, ed = 18118, ng = 3708 20.47%, nph = 4043 Batch 1121: 50.13m, ed = 29112, ng = 4088 14.04%, nph = 4893 Batch 1122: 41.20m, ed = 14909, ng = 3545 23.78%, nph = 5163 Batch 1123: 42.53m, ed = 12517, ng = 2995 23.93%, nph = 4225 Batch 1124: 47.33m, ed = 22620, ng = 3443 15.22%, nph = 4364 Batch 1125: 99.18m, ed = 30828, ng = 2093 6.79%, nph = 1266 Batch 1126: 99.22m, ed = 30828, ng = 2093 6.79%, nph = 1266 Batch 1127: 37.73m, ed = 17562, ng = 2233 12.71%, nph = 3551 Batch 1128: 46.45m, ed = 9824, ng = 2301 23.42%, nph = 2972 Batch 1129: 43.05m, ed = 26903, ng = 2974 11.05%, nph = 4145 Batch 1130: 43.13m, ed = 26903, ng = 2974 11.05%, nph = 4137 Batch 1131: 43.57m, ed = 16413, ng = 3145 19.16%, nph = 4331 Batch 1132: 45.92m, ed = 10777, ng = 3965 36.79%, nph = 5181 Batch 1133: 0.53m, ed = 1, ng = 1 Batch 1134: 46.67m, ed = 16468, ng = 3810 23.14%, nph = 4899 Batch 1135: 46.60m, ed = 16468, ng = 3810 23.14%, nph = 4906 Batch 1136: 0.70m, ed = 3, ng = 3 Batch 1137: 0.72m, ed = 3, ng = 3 Batch 1138: 44.80m, ed = 17768, ng = 1674 9.42%, nph = 2242 Batch 1139: 50.90m, ed = 31882, ng = 2305 7.23%, nph = 2717 Batch 1140: 1.38m, ed = 1, ng = 1 Batch 1141: 49.12m, ed = 10235, ng = 3828 37.40%, nph = 4676 Batch 1142: 49.08m, ed = 10235, ng = 3828 37.40%, nph = 4679 Batch 1143: 44.15m, ed = 20928, ng = 4882 23.33%, nph = 6635 Batch 1144: 43.57m, ed = 36640, ng = 2552 6.97%, nph = 3515 Batch 1145: 43.80m, ed = 21311, ng = 2108 9.89%, nph = 2888 Batch 1146: 43.85m, ed = 21311, ng = 2108 9.89%, nph = 2884 Batch 1147: 40.03m, ed = 13503, ng = 776 5.75%, nph = 1163 Batch 1148: 48.37m, ed = 23461, ng = 2441 10.40%, nph = 3028 Batch 1149: 43.77m, ed = 40100, ng = 1672 4.17%, nph = 2292 Batch 1150: 43.88m, ed = 40100, ng = 1672 4.17%, nph = 2286 Batch 1151: 41.80m, ed = 15418, ng = 2968 19.25%, nph = 4260 Batch 1152: 0.58m, ed = 2, ng = 2 Batch 1153: 44.22m, ed = 28115, ng = 2414 8.59%, nph = 3276 Batch 1154: 43.98m, ed = 51994, ng = 854 1.64%, nph = 1165 Batch 1155: 44.10m, ed = 51994, ng = 854 1.64%, nph = 1162 Batch 1156: 37.55m, ed = 15035, ng = 3890 25.87%, nph = 6216 Batch 1157: 44.37m, ed = 14198, ng = 2933 20.66%, nph = 3966 Batch 1158: 0.95m, ed = 1, ng = 1 Batch 1159: 41.52m, ed = 25996, ng = 2733 10.51%, nph = 3950 Batch 1160: 41.48m, ed = 25996, ng = 2733 10.51%, nph = 3953 Batch 1161: 36.15m, ed = 4084, ng = 1958 47.94%, nph = 3250 Batch 1162: 49.20m, ed = 26194, ng = 1949 7.44%, nph = 2377 Batch 1163: 53.18m, ed = 12820, ng = 4490 35.02%, nph = 5065 Batch 1164: 53.17m, ed = 12820, ng = 4490 35.02%, nph = 5067 Batch 1165: 39.40m, ed = 11782, ng = 3742 31.76%, nph = 5698 Batch 1166: 49.52m, ed = 12097, ng = 3332 27.54%, nph = 4037 Batch 1167: 39.57m, ed = 21970, ng = 2315 10.54%, nph = 3511 Batch 1168: 39.75m, ed = 21970, ng = 2315 10.54%, nph = 3494 Batch 1169: 39.35m, ed = 18897, ng = 3616 19.14%, nph = 5514 Batch 1170: 40.75m, ed = 57824, ng = 584 1.01%, nph = 860 Batch 1171: 0.78m, ed = 2, ng = 1 Batch 1172: 35.93m, ed = 36391, ng = 1947 5.35%, nph = 3251 Batch 1173: 40.00m, ed = 18790, ng = 3798 20.21%, nph = 5697 Batch 1174: 40.22m, ed = 18790, ng = 3798 20.21%, nph = 5666 Batch 1175: 1.40m, ed = 1, ng = 1 Batch 1176: 1.43m, ed = 1, ng = 1 Batch 1177: 37.73m, ed = 10474, ng = 3409 32.55%, nph = 5421 Batch 1178: 44.93m, ed = 20623, ng = 2538 12.31%, nph = 3389 Batch 1179: 44.93m, ed = 20623, ng = 2538 12.31%, nph = 3389 Batch 1180: 40.85m, ed = 20913, ng = 3648 17.44%, nph = 5358 Batch 1181: 0.60m, ed = 2, ng = 2 Batch 1182: 56.45m, ed = 30904, ng = 2093 6.77%, nph = 2225 Batch 1183: 40.65m, ed = 36996, ng = 1583 4.28%, nph = 2337 Batch 1184: 40.75m, ed = 36996, ng = 1583 4.28%, nph = 2331 Batch 1185: 40.03m, ed = 17304, ng = 3195 18.46%, nph = 4789 Batch 1186: 38.60m, ed = 28927, ng = 2945 10.18%, nph = 4578 Batch 1187: 35.60m, ed = 34878, ng = 1310 3.76%, nph = 2208 Batch 1188: 0.70m, ed = 2, ng = 2 Batch 1189: 38.80m, ed = 22652, ng = 3577 15.79%, nph = 5531 Batch 1190: 38.87m, ed = 22652, ng = 3577 15.79%, nph = 5522 Batch 1191: 37.93m, ed = 19550, ng = 3617 18.50%, nph = 5721 Batch 1192: 39.45m, ed = 18764, ng = 3676 19.59%, nph = 5591 Batch 1193: 41.37m, ed = 20425, ng = 3065 15.01%, nph = 4446 Batch 1194: 41.50m, ed = 20425, ng = 3065 15.01%, nph = 4431 Batch 1195: 44.00m, ed = 24719, ng = 2734 11.06%, nph = 3728 Batch 1196: 42.35m, ed = 10612, ng = 3866 36.43%, nph = 5477 Batch 1197: 37.15m, ed = 40565, ng = 1100 2.71%, nph = 1777 Batch 1198: 49.13m, ed = 24069, ng = 3239 13.46%, nph = 3955 Batch 1199: 48.93m, ed = 24069, ng = 3239 13.46%, nph = 3972 Batch 1200: 36.10m, ed = 22853, ng = 2015 8.82%, nph = 3349 Batch 1201: 38.35m, ed = 20712, ng = 2805 13.54%, nph = 4389 Batch 1202: 39.95m, ed = 6884, ng = 3530 51.28%, nph = 5302 Batch 1203: 39.92m, ed = 6884, ng = 3530 51.28%, nph = 5306 Batch 1204: 41.25m, ed = 20915, ng = 3411 16.31%, nph = 4961 Batch 1205: 38.20m, ed = 15449, ng = 3139 20.32%, nph = 4930 Batch 1206: 41.63m, ed = 15600, ng = 3004 19.26%, nph = 4329 Batch 1207: 41.57m, ed = 15600, ng = 3004 19.26%, nph = 4336 Batch 1208: 42.45m, ed = 26396, ng = 2177 8.25%, nph = 3077 Batch 1209: 41.80m, ed = 19486, ng = 1833 9.41%, nph = 2631 Batch 1210: 41.18m, ed = 33083, ng = 2301 6.96%, nph = 3352 Batch 1211: 41.20m, ed = 33083, ng = 2301 6.96%, nph = 3351 Batch 1212: 41.32m, ed = 23680, ng = 2865 12.10%, nph = 4161 Batch 1213: 40.45m, ed = 23683, ng = 2670 11.27%, nph = 3960 Batch 1214: 0.37m, ed = 1, ng = 1 Batch 1215: 1.77m, ed = 3, ng = 2 Batch 1216: 50.53m, ed = 20133, ng = 3842 19.08%, nph = 4562 Batch 1217: 50.53m, ed = 20133, ng = 3842 19.08%, nph = 4562 Batch 1218: 0.63m, ed = 3, ng = 3 Batch 1219: 0.62m, ed = 3, ng = 3 Batch 1220: 39.75m, ed = 16861, ng = 2896 17.18%, nph = 4371 Batch 1221: 47.47m, ed = 20455, ng = 2178 10.65%, nph = 2753 Batch 1222: 43.68m, ed = 16100, ng = 2346 14.57%, nph = 3222 Batch 1223: 43.68m, ed = 16100, ng = 2346 14.57%, nph = 3222 Batch 1224: 41.05m, ed = 33109, ng = 1999 6.04%, nph = 2922 Batch 1225: 38.60m, ed = 20668, ng = 2515 12.17%, nph = 3909 Batch 1226: 43.00m, ed = 12315, ng = 4404 35.76%, nph = 6145 Batch 1227: 43.00m, ed = 12315, ng = 4404 35.76%, nph = 6145 Batch 1228: 46.95m, ed = 22639, ng = 1924 8.50%, nph = 2459 Batch 1229: 44.00m, ed = 14463, ng = 3579 24.75%, nph = 4880 Batch 1230: 0.62m, ed = 7, ng = 6 Batch 1231: 0.40m, ed = 1, ng = 1 Batch 1232: 42.50m, ed = 16701, ng = 3289 19.69%, nph = 4643 Batch 1233: 42.63m, ed = 16701, ng = 3289 19.69%, nph = 4629 Batch 1234: 0.58m, ed = 3, ng = 2 Batch 1235: 0.48m, ed = 3, ng = 2 Batch 1236: 41.70m, ed = 18410, ng = 2286 12.42%, nph = 3289 Batch 1237: 42.07m, ed = 25948, ng = 3571 13.76%, nph = 5093 Batch 1238: 44.75m, ed = 33487, ng = 2445 7.30%, nph = 3278 Batch 1239: 44.88m, ed = 33487, ng = 2445 7.30%, nph = 3268 Batch 1240: 45.97m, ed = 13315, ng = 3163 23.76%, nph = 4129 Batch 1241: 42.78m, ed = 21133, ng = 3973 18.80%, nph = 5572 Batch 1242: 0.42m, ed = 1, ng = 1 Batch 1243: 40.40m, ed = 16132, ng = 4251 26.35%, nph = 6313 Batch 1244: 40.27m, ed = 16132, ng = 4251 26.35%, nph = 6334 Batch 1245: 38.80m, ed = 24502, ng = 1869 7.63%, nph = 2890 Batch 1246: 38.12m, ed = 19783, ng = 2607 13.18%, nph = 4104 Batch 1247: 51.30m, ed = 27142, ng = 2026 7.46%, nph = 2370 Batch 1248: 51.40m, ed = 27142, ng = 2026 7.46%, nph = 2365 Batch 1249: 38.77m, ed = 16799, ng = 1476 8.79%, nph = 2284 Batch 1250: 37.23m, ed = 19808, ng = 3730 18.83%, nph = 6011 Batch 1251: 36.53m, ed = 15054, ng = 4091 27.18%, nph = 6719 Batch 1252: 37.42m, ed = 14904, ng = 3006 20.17%, nph = 4820 Batch 1253: 46.92m, ed = 47748, ng = 1584 3.32%, nph = 2026 Batch 1254: 47.02m, ed = 47748, ng = 1584 3.32%, nph = 2021 ------------------------------------------------------------------ Total : 5735.62m, ed =2942927, ng = 370870 12.60%, nph = 3880

So Gen18Z is now roughly on a par with Gen18H (in "half-search" mode), but is actually running in "full-search" mode, so maybe it can do even better. Another round of tests is scheduled!

by **Mathimagics** » Sun Feb 09, 2020 1:03 pm

More good news, it seems!

I tested the same 3 seed grids with some parameter changes. NTEST is the limit on number of {-2,+2} tests done for each seed, ie batch, and HS is an option to operate in "half-search mode" (see above).

a) with NTEST = 2000 (the current default)

Code: Select all: Batch 1239: 44.88m, ed = 33487, ng = 2445 7.30%, nph = 3268 Batch 1240: 45.97m, ed = 13315, ng = 3163 23.76%, nph = 4129 Batch 1241: 42.78m, ed = 21133, ng = 3973 18.80%, nph = 5572

b) with NTEST = 3000

Code: Select all: Batch 1239: 62.63m, ed = 54107, ng = 3808 7.04%, nph = 3648 Batch 1240: 63.32m, ed = 19023, ng = 4592 24.14%, nph = 4351 Batch 1241: 59.25m, ed = 31485, ng = 6051 19.22%, nph = 6128

c) with NTEST = 3000 + HS

Code: Select all: Batch 1239: 36.68m, ed = 41685, ng = 2991 7.18%, nph = 4892 Batch 1240: 36.35m, ed = 14593, ng = 3362 23.04%, nph = 5549 Batch 1241: 34.92m, ed = 27676, ng = 5133 18.55%, nph = 8820

d) with NTEST = 5000 + HS

Code: Select all: Batch 1239: 62.08m, ed = 64034, ng = 4529 7.07%, nph = 4377 Batch 1240: 60.45m, ed = 20068, ng = 4839 24.11%, nph = 4803 Batch 1241: 58.62m, ed = 41971, ng = 8050 19.18%, nph = 8240

Test (b) indicates that we can increase NTEST without yield loss, in fact in all cases the NPH was actually increased.

Test (c) suggests that "half-search mode" finds fewer grids, which you would expect, but is much faster and produces even higher NPH. That's really good news!

Test (d) hints at diminishing returns for increased NTEST settings, but these are still very good yields.

The New Sudoku Players' Forum

Low/Hi Clue Thresholds

Re: LCT Project Review

Re: Low/Hi Clue Thresholds

LCT-18 Progress

LCt-18 Progres

LCT-18 Progress

LCT-18 Progress

LCT-18 Progress

Re: LCT-18 Progress

Re: Low/Hi Clue Thresholds

Re: Low/Hi Clue Thresholds

Gen18Z Testing

Re: Low/Hi Clue Thresholds

Re: Low/Hi Clue Thresholds

Gen18Z Tests

Re: Low/Hi Clue Thresholds