The New Sudoku Players' Forum

[Mathimagics]

Over 48 hours, the modified Gen18Z ("propagate new grids only") produced just over 5 million new grids:

Code: Select all

Date              Batches     ED grids     New grids   Yield     Total 18C
--------------------------------------------------------------------------
14 Feb 2020     420 -  525    3,254,665    2,353,494   72.31%  482,120,866   NPH =  6129
15 Feb 2020     526 -  671    3,031,685    2,789,058   92.00%  484,909,924   NPH =  7263
16 Feb 2020     672 -  827    3,143,887    2,829,749   90.01%  487,739,673   NPH =  7369
17 Feb 2020     828 - 1033    3,308,208    3,043,139   91.99%  490,782,812   NPH =  7925
18 Feb 2020    1034 - 1228    3,133,941    2,951,931   97.00%  493,734,743   NPH =  7687
19 Feb 2020    1229 - 1413    2,739,329    2,609,664   95.27%  496,344,407   NPH =  6796
20 Feb 2020    1414 - 1637    3,048,216    2,890,944   94.84%  499,235,351   NPH =  7528


For obvious reasons we shall keep these workers employed ...

For coloin:

ExtractSPC.zip

(66.91 KiB) Downloaded 210 times

[Mathimagics]

.
We have found 18C puzzles for 517 million grids.

JACK crashed while I slept, and I took advantage of the break to try out a new program, Gen18ZB. Instead of finding a brand new 18C seed (using blue's Find18C function on 19C grids in the catalog), I take a bunch of randomly selected known 18C grids, and use them to generate new puzzles via the "partial {-2,+2}" method, as for Gen18Z.

It appears that this is just as effective, ie the propagation process is self-sustaining. The yields appear to be similar to Gen18Z - a full days processing will be needed to be sure.

[Mathimagics]

Meanwhile, the 18C grid count has reached 554,119,210 .

Daily yields are currently 2 to 2.4 million, so we would hope to hit the 600 million mark by the end of March.

[Mathimagics]

The 18C grid count has reached 600 million.

Daily yields are currently ~1.35 million (16 worker processes).

[Mathimagics]

We moved house recently, and now that things have finally settled (and the cable guy finally came!), we are fully operational again.

Current status:

• the 18C grid count is now 629,887,891

• Gen18Z yields have dwindled, now down to ~500K new grids per day

• PC "JACK" (16-core) is currently being used to assist with champagne's 17C search process. I feel that this is the best use for JACK at this stage, since the 17C project is definitive (rigorous search) and completion times can be fairly accurately predicted.

• LCT-18 is non-rigorous, we are just trying to identify as many 18C grids as possible of the estimated 960 million. A definitive (rigorous) search is out of the question, because the best explicit grid 18C test function we have takes ~10 seconds.

• the 18C search will continue, in a reduced form, on PC "JILL" (6-core), which usually has at least 4 cores available. On current Gen18Z performance that would reduce overall yields to ~125K per day. But I have thought of a way to improve these yields, and we will see over the coming week how that pans out

• finally, I urge anybody with spare processing capacity to contribute to champagne's 17C search. The end is in sight, but we need more cores!!!

[Mathimagics]

Some recent LCT-18 developments:

• I now have an SSD drive for JILL (i7700K, 4-core x 2-threads PC), so the old problem of slow access to the catalog is eliminated. In fact, it turns out that JILL now has even faster access times than JACK (the 16x2 AMD Ryzen PC).

• I have a new "random morph walker" 18C search function, that employs colin's "subpuzzle solution counts" idea to find 18C puzzles. This can find new 18C's much faster than any previous method, and is not restricted to puzzles in the immediate {+2,-2} vicinity.

• Much of the grunt work involves canonicalising grids/puzzles, and I have found Michael Deverin (holdout)'s Minlex Form via Chaining method is 8x faster than the existing function. If I can get it to transform a puzzle alongside the solution grid, then all things related to LCT-18 will be faster.

[Mathimagics]

Ok, the search for new grids with 18C puzzles is now resumed, albeit with only 4 cores (JILL), as JACK is busy helping champagne with the 17C search.

I have rewritten the Gen18C process completely, and it is much simpler, and more efficient, I think. It looks to be achieving an NPH of ~3000 (new grids found per core-hour), which is quite good.

The current 18C grid count is 635,256,482.

Cheers
MM

[Mathimagics]

Hi debblez!

The LCT project is still active, you will be pleased to know.

champagne has been working hard on building a version of the code that we used to finalise the 17C puzzle count, for use with finding 18C puzzles.

It is hoped that this revised version will be ready for "beta" testing sometime soon.

At this stage, I would guess that we will have the code ready to begin the search sometime in March.

The search will require many cores, over many years (like the 17C search, but longer than that).

Cheers
MM

[Mathimagics]

.
Thanks Mladen for your moral support!

And thanks Colin for your succinct observations regarding the "state of play" (not to mention the millions of puzzles you contributed to the initial vicinity search)!

I think blue and Afmob independently estimated ... that there were about

Supersets method - Afmob: 1.9 billion 18C
Grid sampling method - blue: 1.91 billion 18C

Total grids with an 18C : (0.9683 +/- 0.0129) * 10^9 = estimated 0.97 billion

However, it has to be accepted that the initial generation approach is doomed to only find perhaps 95% of puzzles and never knowingly complete.

The problem lies in that there are many 18C puzzles which are {-2+2} remote of another 18C - so even if we could do a complete {-2+2} we wouldnt find these.

Pretty sure that is why mathimagics has regrouped on the project !

Exactly! It is only with a systematic comprehensive approach that we can locate the missing 18's, and be able to make a claim to completeness of the results.

There are two possible approaches that we can take:

• plan B: use blue's DLL to test every grid

• plan C: use champagne's code to enumerate all the 18C's

We believe that plan C will take less time than plan B. champagne's code should be faster overall, but to what extent remains to be seen. The time comparisons will become more clear when we do production testing in March.

Finally, I should note (again), blue's DLL remains the only method to test a grid explicitly for having an 18C. Without it, we would be totally in the dark - we would have no way to verify that champagne's code is correct. This project would probably be dead in the water without blue's contribution.

Cheers
MM

[qiuyanzhe]

I didn't find it easy to prove that
all N's for a specific solution grid, such that it has a minimal N-clue puzzle
forms a region(i.e. a consecutive set of numbers).
Though it is very likely to be true, there are counterexamples for non-sudoku structures. So I would rather express HCT as
Find the largest of N for which every solution grid has a minimal puzzle with at least N clues.

Admittedly, this would still be tougher than LCT drastically, and even more complex than the previous version..

[Serg]

Hi, Mathimagics!

LCT-19 Final Report!

After 16 days (+ 1.5h) LCT-19X has finished. Both PC-Jack and PC-Jill agree that the number of grids with a 20C puzzle but no 19C puzzle is 268,296.

Are you sure that grids with 21-clue valid puzzles, but no 20-clue valid puzzles don't exist?

Serg

[Serg]

Hi, Mathimagics!

We have already established (in the first phase of this project) that there are only 4 grids which do not have a 20C puzzle ...

I looked through first pages of this thread and didn't find a post about exhaustive search of grids which do not have 20-clue puzzles. Was this exhaustive search done? Can we be sure that grids having 22-clue puzzles, but not 17,18,19,20,21-clue puzzles don't exist?

Serg

[Edited. I corrected some typos.]

[Serg]

Hi, Mathimagics!

Code: Select all

     17C:      46300
     18C:   10658721
     19C:  133785077
     20C: 5328240436 (*)
     21C:          4
          ----------
 Puzzles: 5472730538

So, the bottom line is that there are absolutely NO grids which do not have a 21-clue puzzle, and just 4 that don't have a 20-clue puzzle.

Thank you for clarification! The last question. 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? For example, can we be sure that there are 133785077 ED grids, not having 17-clue and 18-clue valid puzzles, but having 19-clue puzzles. Right?

Serg

[Serg]

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