The New Sudoku Players' Forum

by **Mathimagics** » Sat Jun 16, 2018 7:56 pm

.
Phase 2.2 has completed!

We have now eliminated 98.86% of the 53,666,689 SudokuP grids, and have 611,502 grids remaining. (Thanks to coloin for his CPU contribution!)

This is still a lot more grids than I had hoped for. Phase 3 processing, which is the final stage, requires full enumeration of HSets and test solving for each grid. I have not yet processed a representative sample, but I do know some grids require hours of processing.

So, if the average time (on my system) required was, say, 30 minutes, then that would require over 4 years non-stop processing, using 8 parallel processes. If that turns out to be the case, then I am going to need some serious assistance.

I will conduct some serious testing over the next couple of weeks so as to get a more accurate estimate of the average time required.

Another consideration is the identification of 11-clue cases - it seems to me that these are mostly to be found in the same set of 611,502 grids. This is based on the observation that the minimum number of clues is typically greater than the minimum HSet size. Thus, all the grids eliminated so far (as 10-clue candidates) have HSet size of 11 or more, and so they are highly unlikely to yield any 11-clue puzzles.

I am thinking then of combining 10-clue and 11-clue processing for Phase 3. This would kill two zebras with the same assegai, so to speak. We would get confirmation of the existence (or otherwise) of 10-clue puzzles, and a probably complete set of 11-clue puzzles. The downside is that this would considerably increase processing time per grid.

by **Mathimagics** » Thu Jun 21, 2018 4:16 pm

.
Ok, I've done further testing, and as a result:

the idea for combining 10-clue and 11-clue processing is a dud! We can't assume that 11C solutions will turn up from HSets of size 10 or less. And there is every indication that HSets enumeration takes about 4 times longer for 11C than for 10C. So keeping the jobs totally separate is the only way to go.

but it looks like the remaining 10C grid pool (611,502) can in fact be checked in (relatively) good time. The grids that concerned me (taking hours to process) turn out to be exceptional cases. Average grid times look like being in the range 30-60 seconds, so I am hopeful that the 10C question can be fully resolved in about 8 weeks. We have already done 5.5% of the grids in 2 days, running 6 processes, and the average time per grid so far is 30s.

==================================
Attachment for Colin:

by **Mathimagics** » Sun Jun 24, 2018 9:31 pm

.
While I'm waiting for the 10-clue checker to complete, I've been looking at the 11-clue enumeration problem.

Starting with what we know already, here is a list of the 12 known cases of SudokuP grids with MNC = 11. I've tagged with with their index numbers in my database of ED-grids (CF lex ordered).

Hidden Text: Show

The grids posted by Leren above reduce to just 3 ED grids, while the 9 posted by blue are all ED.

I used this set to road-test my HS-based 11-clue enumeration program (and it works just fine), and also hoping to get some clues regarding which grids are more or less likely to yield 11-clue puzzles.

Every one of these grids appears in my reduced pool of potential 10-clue candidates (611,502 grids), which tends to support the idea that these are the grids most likely to yield 11-clue cases.

One potential clue was that most of the 11-clue known cases have unusually low "small UA" counts. I counted the UA's of different sizes for all grids in the 10-clue pool. I define "small UA" (aka UA12's) as being UA's of size 4 to 12. Here is the list of values for the 12 grids above, along with # of HSets of size 8-11, and the time it took my HS enumerator to check each grid:

Code: Select all: Grid # # of UA12 HS8 HS9 HS10 HS11 11C tm(s) =========================================================================== 53658889 2 216 182298 22999443 845563259 running 53658890 3 pending 53541837 5 - 7196 3576465 419157411 35788 23201464 6 1 2799 1252871 159090243 15393 53557072 6 36 32691 11018148 1008867556 63382 22979593 7 9 11440 2667235 235639011 17830 53624261 10 1 2941 1407989 171056472 13103 23201702 11 - 1305 467056 53249139 5138 53380826 14 - 339 226631 40782013 7426 22504781 16 - 15 14003 4019288 1657 23068647 16 - 2520 841573 97463945 8028 15449135 25 - - 917 459665 284

Some of those run times are pretty scary, although the good news is that only 2100 of the pool grids have 10 or fewer UA12's (some have none at all!). But if they are also more likely to produce 11-clue puzzles, it makes sense to bite the bullet and do them first.

So while I am running 6 jobs to do the 10-clue job, I am using my remaining 2 process threads to check these grids for 11-clue puzzles. Hopefully coloin can handle much of this load. Average grid processing time looks like 1-2 hours, so this sub-job is unlikely to finish for some weeks!

There are then about 24,000 grids (in the pool) with 11 to 15 UA12's, and 96,000 with 16 to 20 UA12's. By this stage we will be processing the grids a lot more quickly, and with more processor threads, and so make better progress.

An encouraging sign is the existence of an 11-clue puzzle for a grid that doesn't have low UA12's like the others, and you can see it took only a few minutes to process (compare that with the 18-hour monster).

Here are the puzzles I found for the 12 known grids:

Hidden Text: Show

by **blue** » Mon Jun 25, 2018 7:28 pm

Hi Mathimagics,

We have now eliminated 98.86% of the 53,666,689 SudokuP grids, and have 611,502 grids remaining. (Thanks to coloin for his CPU contribution!)[/b]

I have been trying to "verify" (in some sense), your (implied) claim that "98.86% of the 53,666,689 SudokuP grids" can be rejected, due to "MCN considerations" ... and having no luck.

I'm only able to reject ~50% of them. On the other hand, I am seeing that with the UA sets that I'm using, over ~98% of the grids (including the rejected grids), don't have a 10-clue hitting set.

Am I right in assuming that when you reject a grid, it means that you have found 11+ disjoint UA sets in the grid ? On the other hand, maybe you're using what McGuire's paper calls "higher-degree unavoidable sets", in which case you can ignore the rest of this post.

If it's "11 disjoint UA sets" ...
Would you (somehow) list the UA sets for a few of the grids below ?
There are 100 grids listed. They're in row-minlex form, already ... presumably.
They represent a random sampling of the grids that I can't seem to reject.

Hidden Text: Show

It seems like I have a bug somewhere, but after much effort, I can't seem to find it

TIA,
Blue.

by **Mathimagics** » Mon Jun 25, 2018 8:20 pm

Hello blue!

I only used clique testing, ie finding mutually disjoint UA's, in the very first phase. All grid eliminations since then (3 passes of Phase 2) have been HS-based. A grid was only eliminated if no HS of size 10 or less was found in the UA set. The 3 passes progressively increased the number of UA's used (150, 250, 300).

I only use first-order UA's

I think my 10-clue first phase rejected roughly 50%, so your results do in fact seem to be consistent. 8-)

I'm happy to provide sample UA's if you need them.

Cheers!

by **blue** » Mon Jun 25, 2018 9:03 pm

Hi Mathimagics,

All grid eliminations since then (3 passes of Phase 2) have been HS-based.
...
I think my 10-clue first phase rejected roughly 50%, so your results do in fact seem to be consistent.

Ahh, good. The 98% number lines up too !

I'm happy to provide sample UA's if you need them.

No need. Thanks for the explanation.

Congratulations on your progress so far !
Hats off to Colin as well.

Cheers,
Blue.

by **Leren** » Mon Jun 25, 2018 9:07 pm

I'm a bit confused about what I think Mathememagics was saying above about the number of known SudokuP puzzles with a minimum of 11 clues. I thought that the number was 14.

The first table shows the 14 clue sets as originally published, 5 by Ocean and 9 by blue. For convenience I've labelled these O1 - O5 and B1 - B9.

Hidden Text: Show

The second table shows a set of isomorphic transformations of these clue sets to bring them into a consistent format (for me).

It also shows the number of solved cells when singles have been exhausted, and solved cells when basics have been exhausted (by my SudokuP solver, which I think is complete for singles and basics).

For me these two numbers become a "fingerprint" for the clueset. If the two numbers are different, I'm assuming that the resulting solution is an essentially different SudokuP grid. The clueset is certainly essentially different.

What I think Mathemagics is saying above is that Ocean's 5 cluesets reduce to 3 essentially different puzzles, although that's not obvious from the 5 essentially different cluesets.

Hidden Text: Show

I've been using this information to see if I can find just one new 11 clue clueset, that would be enough for me. To do this within a reasonable timeframe I examined the 14 clusets to see what they had in common.

To cut a long story short I found that all cluesets could be suitably transformed into a format that looks roughly like :

Hidden Text: Show

The 4 can only be in Box 2 and the 5 must be in Box 3 or a higher numbered box. Well, after trying over 6 billion cluesets I've had a total of just 10 hits. Unfortunately for me, careful examination of these cluesets shows that they are not essentially different from one of the 14 known cluesets. No success so far but I live in hope. I guess what I can say is that 11 clue cluesets must be extremely rare, if there are others to be found it will not be a large number, so heuristically I can say I strongly suspect that the answer to the 10 clue problem is that there isn't one.

For completeness, here is a table of the 10 hits I have found using this pseudo-scientific process:

Hidden Text: Show

I live in hope of finding just one new 11 clue clueset

Leren

by **Mathimagics** » Tue Jun 26, 2018 1:18 am

Leren wrote:What I think Mathimagics is saying above is that Ocean's 5 cluesets reduce to 3 essentially different puzzles, although that's not obvious from the 5 essentially different cluesets.

Hi Leren,

What I did was feed your list of 11C puzzles into my solver to get the solution grids, then reduced the list to ED-forms, and in this process the ED grids that I report are always the primary (lowest lex-order) representative. The result is 3 grids.

blue should be able to confirm this result.

Your observation regarding possible scarcity of 11C puzzles might well turn out to be true, there are some worrying indicators.

I too would be greatly relieved to make, or have somebody make, by the first (ED) new discovery! 8-)

by **Leren** » Tue Jun 26, 2018 3:44 am

Well, here are the 5 solutions for the O1 - O5 clue sets, with some indications of the solution path and the singles + basics "signature" for each puzzle:

Code: Select all: Singles Candidates Basics Candidates O1 : 182764593493528176657193284841259637765831942329476815976315428214687359538942761 Basics + 1 Skyscraper 18 312 56 59 O2 : 172864935493517286658293174247359618865172349319486527586721493924638751731945862 Singles + 7 Intersections 18 312 81 0 O3 : 142875693593624187768193245451269738876431952329587416987316524215748369634952871 Basics + a few chains 18 307 48 102 O4 : 142875936593614287768293145254369718876142359319587624687421593925738461431956872 Singles + 8 Intersections 27 247 81 0 O5 : 152837496397465281648291573269574318873912654415386927981623745526748139734159862 Basics + a several chains 19 328 19 257

The question of the day is : are these 3 or 5 essentially different SudokuP Grids. I gather that blue can put these into some canonical format, such as minlex, and resolve the question.

Leren

PS - If these aren't 5 essentially different SudokuP puzzles I'll be a monkey's uncle.

Not only have I taken the F,G and E transforms of each puzzle, I've taken random morphs of each. For each clue set the solution signature never changes. I've even added a new element to the solution signature, the number of candidates remaining at the end of the Basics + follow-on singles process ie the number remaining when the first non-basic move is required. For each clue set, with its F, G, and E transforms and morphs the solution signature never changes.

If there is a deficiency or bug in my SudokuP solver up to the end of Basics, it must be really subtle. Don't worry though, I've got some bananas at home just in case I'm proven wrong

Leren

by **Mathimagics** » Tue Jun 26, 2018 6:31 am

.
Leren,

here are your 5 grids, with their CF (using SudokuPF-canonical form function provided by blue):

As you can see, there are only 3 ED grids here:

Hidden Text: Show

I hope this is correct, otherwise we are all in trouble!!

by **Leren** » Tue Jun 26, 2018 7:33 am

Mathemagics,

It might be that nobody is in trouble.

If blue's software is correct (and I have little doubt that it is), then what it is saying is that we have more clue sets than solved puzzles. So, for example, Your puzzle number 53624261 has (at least) two different 11 clue solution paths ie from O1 and O3. Since the solution paths are fundamentally different the clue sets O1 and O3 are not SodokuP isomorphisms of each other. So what are we fundamentally interested in, clue sets or solved puzzles. I would have thought it was clue sets.

Haven't we just proved something ? The number of essentially different SudokuP 11 clue sets exceeds the number of essentially different SudokuP solutions. A bit counter intuitive but nevertheless true ?

Is it possible to locate the clue sets O1 and O3 in the O1 and O3 solutions and see what and where they are mapped to via blue's software ? I think that would prove or disprove this proposition, since you could plug the 2 mapped clue sets into a solver and arrive at the same solution by "essentially different" paths.

Leren

PS For the avoidance of any doubt on what constitutes an "essentially different" solution path I've included a new column in the table in my previous post, which is the number of candidates remaining when a basic clue mark-off and consequential naked and hidden singles moves are carried out. According to Mathemagics, clue sets O1 and O3 solve to the same puzzle no 53624261, but have different numbers of candidates after singles exhaustion, 312 for O1 and 307 for O3. O2 and O4 also solve to the same puzzle no 53557072 but their candidate numbers after singles exhaustion are also different, 312 for O2 and 247 for O4.

by **Mathimagics** » Tue Jun 26, 2018 1:03 pm

.
Hi Leren,

Leren wrote:If blue's software is correct (and I have little doubt that it is), then what it is saying is that we have more clue sets than solved puzzles.

So, for example, Your puzzle number 53624261 has (at least) two different 11 clue solution paths ie from O1 and O3

Indeed, this is true. While blue's 9 solution grids each have just one 11C puzzle, two of the "Ocean" grids have more than 1. 53624261 has two puzzles, 53557072 has four:

Code: Select all: ..3..............6..8..1.....5.............7..........67.9...........3..2........ # 53557072 ............2.......8........5.....4.....3.....6.......7...........6....23.....9. # 53557072 ............2.......8........5...........3.....6.......7.....4.....6....23.....9. # 53557072 ..3..............6..8........5.............7..........67.9...........3..2..1..... # 53557072 .....6...........2..9......6...........9..8..24........7.............1..3........ # 53624261 .....6...........2..9......6...........9..8..24......................17.3........ # 53624261

Those 8-digit index number tags that I use are unique ED grid (solution) identifiers. These are CFI's - canonical form index numbers.

If you sort the set of 53,666,689 different CF (canonical form) SudokuP grids, CFI is simply the position of a grid in that list.

Leren wrote:Since the solution paths are fundamentally different the clue sets O1 and O3 are not SudokuP isomorphisms of each other. So what are we fundamentally interested in, clue sets or solved puzzles. I would have thought it was clue sets.

I seem to recall that blue demonstrated this property (somewhere above in this thread). Comparing puzzles on equivalent (same CFI) grids is problematic.

Say we take a CF grid, G, and make a puzzle P1 for it. If we then apply a transformation to that puzzle, P2 = F(P1), then the solution is G2 = F(G1). P1 and P2 are thus equivalent in one sense, but can appear quite different to the solver (ie have different solution paths).

Leren wrote:Is it possible to locate the clue sets O1 and O3 in the O1 and O3 solutions and see what and where they are mapped to via blue's software ? I think that would prove or disprove this proposition, since you could plug the 2 mapped clue sets into a solver and arrive at the same solution by "essentially different" paths.

As I understand it, this is not straight-forward. We can't canonicalise clue sets, only solutions (and I think this is due to the intricacies of blue's transformations).

Serg has been wrestling with this very problem, I think.

by **blue** » Tue Jun 26, 2018 2:57 pm

Hi Leren & Mathimagics,

Leren wrote:If blue's software is correct (and I have little doubt that it is), then what it is saying is that we have more clue sets than solved puzzles.

All in all, what we have is:

Three of the solution grids, have one non-trivial automorphism.

--

Leren wrote:Is it possible to locate the clue sets O1 and O3 in the O1 and O3 solutions and see what and where they are mapped to via blue's software ?

Mathimagics wrote:While blue's 9 solution grids each have just one 11C puzzle, two of the "Ocean" grids have more than 1. 53624261 has two puzzles, 53557072 has four:

Mathimagics' (original) puzzle list was missing puzzles for two of the grids.
This is the list, extended to cover the missing grids, and with Leren's puzzle labels added:

Hidden Text: Show

--

Mathimagics wrote:We can't canonicalise clue sets, only solutions (and I think this is due to the intricacies of blue's transformations).

Later today, I'll find that code, and make a version that takes a puzzle and its solution for input.

by **Mathimagics** » Tue Jun 26, 2018 4:09 pm

Thanks blue, I have added the missing two to my list.

I now have 12 ED grids, 18 x 11C puzzles.

by **Mathimagics** » Tue Jun 26, 2018 6:09 pm

.
Colin (coloin) has suggested a reduction method for finding 11-clue puzzles that have explicit clues-per-box properties.

Most of our known solutions (admittedly a small sample) have some box with 3 clues. We can find these by first looking for 17-clue puzzles with one box filled in (9 clues) and 8 clues in the other boxes. Then we just test each of 11-clue puzzles obtained by reducing the full box to 3 clues:

For example:

Code: Select all: +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |123|456|789| |...|...|789| |.2.|45.|789| |.2.|45.|...| |456|789|132| |...|...|132| |...|...|132| |...|...|13.| |789|231|564| |...|...|564| |...|...|564| |...|...|.6.| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |674|395|218| |...|...|...| |...|.9.|...| |...|.9.|...| |518|624|973| |...|...|...| |...|...|.7.| |...|...|.7.| |392|178|456| |...|...|...| |...|...|...| |...|...|...| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |937|562|841| |...|...|...| |..7|...|...| |..7|...|...| |261|847|395| |...|...|...| |...|...|..5| |...|...|..5| |845|913|627| |...|...|...| |...|..3|...| |...|..3|...| +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ 1 2 3 4

We find the solution (4) by fixing box 3 (2), enumerating the HSets of size 8 that exclude box 3. One of these necessarily is the grid (3), which leads to the solution.

This has to be done for each box, but we only need to build our UA list once, we can simply mask out those UA's that reference cells in the filled box.

The full treatment (9 passes) seems to run 4 to 8 times faster than one-pass full HSet = 11 enumeration.

HSet enumeration time tends to increase/decrease exponentially wrt target HSet size, so while searching for 4-clues in a box cases would be even quicker, 2-clues per box dies in the bum.

However, given the fact that most known cases (16 of the 18 ED 11-clue puzzles) have 3 clues in a box, it makes sense to proceed with this approach.

The worst-case scenario would be that there exist undiscovered 2-clues-per-box puzzles, but NO more 3-clue cases.

But unless someone comes up with a better idea, I intend to run with this one!!

PS: Hats off (again) to coloin for this suggestion.

The New Sudoku Players' Forum

SudokuP - Min Clue Project

SudokuP: 10-clue progress

SudokuP: 10-clue progress

SudokuP: 11-clue Search

Re: SudokuP: 10-clue progress

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

SudokuP: 11-clue Search Strategy