The New Sudoku Players' Forum

[Mathimagics]

.
Hi blue,

Find10C is on hold, 102,763 grids (16.8% of the pool) have been checked. I will resume this job when current 11C (3CB) search finishes.

Sadly my old PC, on which I could resume the job now, has cooling issues when placed under load, so I don't currently have any spare processes.

But since coloin's spare PC is now available (having finished the 11C jobs I gave him), I might be able to give it to him ... I will look into that.

Thanks for the prompt!

[Mathimagics]

We have checked 45% of the pool, no cigar!

I'm running only 3 jobs at a time, owing to my diversion of resources to the 12C search ...

In the table below, C is a completed job (see here for details of the job organisation), R is a running job. gtm is average time spent per grid, etc is estimated job completion time based on gtm.

Find11C Status 18 July 2018

Hidden Text: Show

Code: Select all


Job10: C NG =  2077 /   2077 (100%), gtm = 1734.25s
Job11: C NG =  1735 /   1735 (100%), gtm =  444.16s
Job12: C NG =  2804 /   2804 (100%), gtm =  301.98s
Job21: R NG = 16791 /  30151  (55%), gtm =   39.71s, etc = 24/07 11:27:19
Job22: R NG = 19871 /  33326  (59%), gtm =   33.55s, etc = 23/07 13:29:46
Job23: C NG = 34819 /  34819 (100%), gtm =   34.43s
Job24: C NG = 35711 /  35711 (100%), gtm =   32.23s
Job25: C NG = 35447 /  35447 (100%), gtm =   29.95s
Job26: R NG = 31803 /  35109  (90%), gtm =   25.58s, etc = 19/07 07:35:26
Job27: C NG = 33103 /  33103 (100%), gtm =   24.96s
Job37: C NG = 10400 /  10400 (100%), gtm =   15.53s
Job38: C NG =  8829 /   8829 (100%), gtm =   15.02s
Job39: C NG =  7292 /   7292 (100%), gtm =   15.15s
Job40: C NG =  6163 /   6163 (100%), gtm =   14.95s
Job41: C NG = 25564 /  25564 (100%), gtm =   15.33s

Jobs   =       12 complete, 3 running, 17 pending
Grids  =   272409   (44.70%)


[Mathimagics]

I see an example where focusing on a single task gives better result. At least for men.

I am vaguely familiar with this theory, but unable to apply it. I have ADHD, it's a wonder I get anything done!

And some doubts arise on what method are you using for 11-clue search.

The 10-clue Search

As I explained to blue above, I have put the Find10C jobs on hold. I was running them on my old PC, but it has cooling problems, and I need to find a PC guy to come and replace the fans and/or power supply.

Testing for each grid takes about 1 minute (at 4.77GHz), so we have about 500,000 minutes to go. We do have coloin's spare PC available, but it's only got 2 cores and they are 2.77GHz. My old PC has 4 x 2.77GHz so between us we could complete the job but we would need all 2 + 4 processes running for 3 months in order to complete.

I am fully aware of the relative iportance of completing this work, because it is a rigorous test, ie: we can establish beyond reasonable doubt that there are NO 10-clue puzzles.


The 11-clue Search

To do the equivalent rigorous search for 11-clue puzzles, even if we consider only the 10C grid pool, is quite simply beyond reach. It takes an order of magnitude longer for 11C HSet enumeration/testing than for 10C.

About the 10C grid pool. The chances of an 11-clue puzzle existing in a grid with minimum HSet size 11 is, in my opinion, very close to zero. Mere satisfaction of UA's does not a valid puzzle make! The MHS for the known 11C grids is 5 to 7. For 12C grids MHS is typically < 10.

Note also that 97% of 12-clue puzzles found come from grids in the 10C pool.

But, a rigorous search for 11C puzzles (ie: using full HSet enumeration) on the pool grids would take a total of 3 to 6 million minutes.

So we have dropped the rigour, and opted instead for coloin's suggestion of a reduced test, one that will detect any 11-clue puzzle with 3 clues in a box (3CB). 80% of known cases have this property, so if there are other 11-clue puzzles out there, we have a very good chance of finding them.

If we fail to find any, which is looking likely, AND we don't find any NEW reducible 12-clue puzzles, I think we can safely say that in all probability we already have them all.

And if there is some sneaky 2CB 11-clue puzzle unknown to us out there, it's going to be really, really hard to find.

[blue]

As I explained to blue above, I have put the Find10C jobs on hold. I was running them on my old PC, but it has cooling problems, and I need to find a PC guy to come and replace the fans and/or power supply.

If you're running Windows 10, there are some system settings that might help ... at the cost of reduced processing power.
[ I have my system set up this way ... due to my extreme dislike of excessive fan noise, and my worries about overheating the CPU. ]

First follow of one of these paths to bring up the "power settings" dialog box:

Settings -> System -> Power & Sleep -> "Related Settings / Additional power settings"
Start Menu -> Windows System -> Control Panel -> Power Options

Then either create a new "power plan", or (like me) just modify the default "Balanced" plan.
After you decide ... click on "Change plan settings", and "Change advanced power settings".
Another dialog box comes up.

Scroll down to "Processor power management", and click on the "+" to see the settings ... then:

Set the "System cooling policy" to "Passive" mode ... "Slow the processor before increasing fan speed".
Set the "Maximum processor state" to 99%. This disables "Turbo Boost", from what I can tell.

I need to do both of those, to see & hear a real difference in the behavior.
With things set that way, and with 4 cores running, the "Performance Monitor" shows the CPU (always) at 3.59GHz, on a supposed "3.6GHz" machine ... that, and the fan still speeds up & slows down.

I'm disappointed with Microsoft, that it doesn't do what is claimed.
All in all though, it's a big improvement over the CPU running at 3.79Ghz, and the fan running absolutely wild.

Good luck,
Blue.

P.S.: I mentioned being disappointed with Microsoft, above ... but for all I know, it could be my OEM (Asus), that's at fault.

[Mathimagics]

.
My new system (4cores x 2 threads) is running Win 10 , but it's quiet and cool despite having been running at 90-100% CPU for weeks now.

It's my old PC (6 cores), running Win 7, that has the problem. When I ordered it all those years ago, I hadn't considered cooling capacity, so probably got the cheapest fans by default. It's only now I want to load it up that it gets heartburn. Literally ...

[blue]

Hi Mathimagics,

Since the 12 clue search is "more fun", and since a 10 clue result seems farther off than your recent posts suggested ... let me ask you a hypothetical question (or two).

Suppose that I had completed the full testing for 11 clue puzzles.
Would you want want me to tell you now, or maybe at some later time, what it impled for 10 clue puzzles ?
If yes (at some time), then what about the end result for 11 clue puzzles ?

[Mathimagics]

.
Struth!

I guess it depends on the nature of your "full search". If you feel certain that you have found all 11-clue puzzles, by all means put us out of our misery!

Seems to me that 10-clue implications (presumably confirming the expected non-existence of such) might only be valid if you HAD found all 11-clue puzzles in some sort of rigorous manner. Am I missing something here?

In any case, I'm game! Let's see your hand!

[blue]

Seems to me that 10-clue implications (presumably confirming the expected non-existence of such) might only be valid if you HAD found all 11-clue puzzles in some sort of rigorous manner. Am I missing something here?

No, you're right.
The end result was that we have all of the 11's, and (so) there are no 10's.

So that champagne doesn't get angry with me, the search only took 1250 core hours, or just over 13 days, with 4 threads running.

Cheers,
Blue.

[dobrichev]

• these 611,502 grids at some point hit all known UA by known <=10 clues but you forgot to call the solver at this point to prove/disprove the uniqueness of puzzle(s) solution?

This is sort of correct, but we did NOT forget to call the solver. We simply asked the question for each grid:

• does there exist a HSet of size <= 10 clues?

'The answer was YES for 611,502 grids, and that is our pool of "candidates". These are the only grids that might possibly have 10-clue puzzles.

This question is considerably easier to answer than "Does this grid have a 10-clue puzzle?"

To answer the main question (is there a 10-clue puzzle?) we need to enumerate, for each grid, all Hsets of size <= 10, and test-solve all the possible puzzles for each HSet.

Assuming HSet is abbreviation of "Hitting Set" which itself is synonym of "set of Sudoku givens that resolves all UA sets for this particular grid", and then applying my limited knowledge in English and logic, the only difference I can between "does there exist" and "enumerate all" is whether we stop on first 10-clue found or continue enumeration until all puzzles are found.

Under assumption that HSet is "set of Sudoku givens that resolves those UA sets we choose to use for this particular grid", which seems to be correct for your case, the difference is in calling the solver to prove/disprove validity for this Hset against ALL UA sets.
For HSet of size 10 you must call the solver once.
For HSet of size 9 you must loop over the rest non-givens and call the solver 81-9=72 times.
For HSet of size 8 you must do 2 nested loops over the non-givens so that the inner loop index > outer loop index, etc.

If you realize the above but still choose not to call the solver, this is a sign that your UA sets are of low quality, produce too much false positives and move the load from hitting UA logic to the solver. This is resolvable by improving initial UA quantity and quality or/and by implementing a secondary-level cache of UA generated on previous calls to the solver. Blue maybe does both (as well as chain of other improvements).

@Blue: Congratulations for your full enumeration of 11-clue puzzles!

Is this a toy project for testing the 17-clue search, and now you are waiting for confirmation that your method gave the correct result?
Hope the 17-clue enumeration is ongoing and these 13 cpu-days you spent for this branch is worth it.

[Serg]

Hi, blue!
Congratulations on finding all possible (14) 11-clue SudokuP puzzles!
Congratulations on the proof of 10-clue SudokuP puzzles non-existance!

Serg

[Mathimagics]

If you realize the above but still choose not to call the solver, this is a sign that your UA sets are of low quality, produce too much false positives and move the load from hitting UA logic to the solver.

With SudokuP we can only work with what is available. Most UA sets that apply when the grid is considered as a standard Sudoku grid do not qualify as UA's for SudokuP.

For example, try and find some "high quality" UA sets in these grids:

Code: Select all

123456789564897231978312645647938512389125476251764893895271364712643958436589127 # 53666688
123456789456897231978312456247968315589173624631524897894631572312745968765289143 # 23199968
123456789456897231978312456564978312789123564231564897897231645312645978645789123 # 23199970
123456789457918362896237154671894235589723641342561978968342517234175896715689423 # 53664625
123456789457298613869371452594837261382169574716524938678912345931745826245683197 # 53577383
123456789564897231978312645645978312789123456231564897897231564312645978456789123 # 53666687


[coloin]

Only blue knows how hard he tried to generate a new puzzle - but it is always possible that one will be found ....

Well done blue !

Considering Mathmagics valient efforts I'm sure a brief outline how you did it in 13 days would be informative.

It has been been a good exercise and thanks for letting myself and Mathimagics have a good try at it.
I think the lack of new non-minimal 12C puzzles was an indicator that the 10C search was only going one direction !

[Mathimagics]

Yes, blue, well done!

I have no doubt that your 11C enumeration will constitute a proof of the non-existence of 10C puzzles, but technically it will only do so if you give details of the enumeration method, enough to satisfy us of the algorithm's completeness.

[blue]

For example, try and find some "high quality" UA sets in these grids:

Code: Select all

123456789564897231978312645647938512389125476251764893895271364712643958436589127 # 53666688
123456789456897231978312456247968315589173624631524897894631572312745968765289143 # 23199968
123456789456897231978312456564978312789123564231564897897231645312645978645789123 # 23199970
123456789457918362896237154671894235589723641342561978968342517234175896715689423 # 53664625
123456789457298613869371452594837261382169574716524938678912345931745826245683197 # 53577383
123456789564897231978312645645978312789123456231564897897231564312645978456789123 # 53666687


Wow ... what a nice selection

Except for #53577383 ... these grids took the "top 5" times, in my 11-clue search (discounting the 12 grids with known 11's).

The top one, had the #1 time -- 7.2 hours -- longer than the combined time for all 12 of the grids with 11's.
The last one in the list, has 252 (minimal) UA's at size 18 ... nothing smaller, and nothing again until another 648 appear at size 28.
It was #3 in my list (or #4, if you count the grids with 11's).

[blue]

Hi Mladen & Mathimagics,

(...)

This is resolvable by improving initial UA quantity and quality or/and by implementing a secondary-level cache of UA generated on previous calls to the solver. Blue maybe does both (as well as chain of other improvements).

I have no doubt that your 11C enumeration will constitute a proof of the non-existence of 10C puzzles, but technically it will only do so if you give details of the enumeration method, enough to satisfy us of the algorithm's completeness.

It's nothing special ... a re-modified version of the McGuire group's code.
It has the "secondary-level" UA cache that Mladen mentioned, and new code to find (SudokuP) UAs.

The UA code, starts at N=16, and finds all UA's with size <= N, all with size <= N+1, and so on, until it has some minimum number of them.
For all but ~460000 grids (the ones that I knew had 12's, and the grids with non-trivial automorphisms) ... it moved to the hitting set enumeration, as soon as it had >= 100 UAs. For those (~52M) grids, the average time was ~77ms/g, and the longest times were under a minute.

The number 100, was arrived at by experimentation ... trying to achive the fastest throughput rate. The story was that the secondary-level cache, could cover well, for what might seem to be a poor selection of UA's to be used in the hitting set enumeration. Pushing the number too high, caused more time to be spent finding the UA's, than was saved by having the secondary cache. Having it too low, meant that more hitting sets would be found, than could be "covered for" by having the secondary cache.

For the grids with 12's, I used looked for >= 512 UA's, limiting the UA size at 24.
For the rest ... grids with automorphisms ... I used ">= 100 UA's", and a "0.66s" timeout.
The grids that timed out, I ran again, using ">= 512 UAs".