SudokuP - Min Clue Project

For fans of Killer Sudoku, Samurai Sudoku and other variants

SudokuP: 10-clue progress

Postby 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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

SudokuP: 10-clue progress

Postby 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:
Attachments
SudokuPX.zip
Updated SudokuPX (reduction method)
(42.96 KiB) Downloaded 119 times
Last edited by Mathimagics on Wed Jun 27, 2018 2:55 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

SudokuP: 11-clue Search

Postby 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
Code: Select all
123456789456789132789231564674395218518624973392178456937562841261847395845913627 # 15449135
123456789456798213897312546318574692569821374274963158941235867682147935735689421 # 22504781
123456789456798231879312456568971342914823675237564198695237814382149567741685923 # 22979593
123456789456798231978312456237941568815623974649587123394875612582169347761234895 # 23068647
123456789456897312978231465264978531589163274317524896895312647731645928642789153 # 23201464
123456789456897312978231564264518937789623145315749826842375691531964278697182453 # 23201702
123456789457198632968273154294367518816549273735812496672935841381724965549681327 # 53380826
123456789457289631986371542678512394514793826239864157841937265362145978795628413 # 53541837
123456789457298136968371452395817264812643975746529813671932548589764321234185697 # 53557072
123456789457398612869127534698512347735964821241783956974831265586249173312675498 # 53624261
123456789457891236968372451571948362689523174234617895895234617312765948746189523 # 53658889
123456789457891236968372451571948362689723145234615897895237614312564978746189523 # 53658890


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
Code: Select all
.2.45..........13........6.....9...........7............7..............5.....3... # 15449135
12..........79.......3...................1...........8.4.....67.............8.... # 22504781
..3...........82.1.79......................7.2............3...........6..4....... # 22979593
........9......2....8..........4...........7................6.2......3..7.1..4... # 23068647
...........6.....2...............53..8..............9.........77.1..........89... # 23201464
1........4.....3............6......7.89.....5....4...................2.......2... # 23201702
.....6...4.7.....2..........................3..5..........3.....8....96..4....... # 53380826
.2........................2.7...........9........6.15...1..............8.....8..3 # 53541837
..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
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: SudokuP: 10-clue progress

Postby 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
123456789457189632689732154234615897761894325895327416372948561916573248548261973
123456789457189362896273451235961847741835296968742135612394578574618923389527614
123456789456789132798123546265394817841675293379812465932541678517968324684237951
123456789457189632689732415238541967794863521561297348312675894945318276876924153
123456789457189263689327145294568371536714892718293456845932617371645928962871534
123456789456789123789132465235894617891675342647213958962348571518967234374521896
123456789457189263689372451568217934971534826234968517895641372312795648746823195
123456789457189263986237451261594378835671924794823615642915837318742596579368142
123456789457189263698273451231648597576931824849527136964812375312795648785364912
123456789457189263689723145275648391841395672396217458934862517718534926562971834
123456789457189236689273415238961547971542863546738192392815674715694328864327951
123456789456789132897213645265841397341597268789362451972638514614975823538124976
123456789456789132798213645672945318345861927981372456867534291214698573539127864
123456789457189236869273154248691375371524698596738412934812567712965843685347921
123456789457189263896273451231648597748591326569327148374962815912835674685714932
123456789457189236869327415234518697915674328786293154371865942592741863648932571
123456789456789231798213654271834965964175328835962147617348592542697813389521476
123456789456789132789132546248617395915843267367925418832564971571398624694271853
123456789457189236986273154274395618598761342361842597842537961615924873739618425
123456789457189263986723145248675931735941628619238457362597814894312576571864392
123456789457189362689723154894637215715294638362518497948362571576841923231975846
123456789456789123789123465265918347937645218841237956694872531572361894318594672
123456789456789123789132465245617938397845612618293547862571394534968271971324856
123456789457189263986723451235914678794638512618572394562391847371845926849267135
123456789456789132879312654315864297964275813287931546632548971541697328798123465
123456789457189236689723415348512967715694823296378154874235691562941378931867542
123456789457189326689327451365214897718963245294578163942631578571892634836745912
123456789457189263968273451231968574546721938789534126692845317874312695315697842
123456789457189236896273154278614395345928671619735428531867942764592813982341567
123456789456798213978312465342675891865941372791823654514267938639184527287539146
123456789457189236869723154572648391398571642641392578934217865715864923286935417
123456789456789123789123564267541938591368247348972651674895312912634875835217496
123456789456789132789132564275364891368591247941278356532947618614825973897613425
123456789456789132879231546235847961641923875987165324514372698368594217792618453
123456789456789132879321645348275961915864327267193458532617894691548273784932516
123456789456789132789231546531978264294563871678124953845612397917345628362897415
123456789457189263869372451231864975678915324945237618312698547596741832784523196
123456789457189263689723145568241397374598621291367458912635874745812936836974512
123456789457189236689732145234695817791348562568217394342561978915874623876923451
123456789457189263689327541248615937316974825975238416562891374731542698894763152
123456789457189236689327145291865374365742891874913562942538617518674923736291458
123456789457189236869723154294631578718594623536278941342967815971845362685312497
123456789457189263986723541518297634674315928239864157862941375741532896395678412
123456789457189326689723154241378695798564213365912847914837562832645971576291438
123456789456798132879321456265834971341279865798165243612547398987613524534982617
123456789457189263968723154274968315615374928389215647591647832742831596836592471
123456789457189263698237415245618937731925648986374521372561894514892376869743152
123456789457189236896273514271834695645791823389625147912547368564318972738962451
123456789457189263689372415275894631941635872836721954312967548794518326568243197
123456789457189362869237451275361894916874523384925176538612947691748235742593618
123456789457189263689327415518642937376591824294738156865274391732915648941863572
123456789457189623689723154234617598768594231591238476875941362916372845342865917
123456789457189263986237451295674318314598672768312594532961847841725936679843125
123456789457189263896327154278645391341798526965231478534962817612874935789513642
123456789456789123789132564265841937837695241941327856394578612512964378678213495
123456789457189236986327154364295871518764923279813465642938517895671342731542698
123456789457189263689273451215398647798641325346725198531862974872934516964517832
123456789456789132789213465362871594874395621591642378645938217218567943937124856
123456789457189236986273154218534697764891523539627418371942865645318972892765341
123456789457189362968327451395218674614735928782694135831962547246571893579843216
123456789457189236689372145395841672874625391216937458538264917942718563761593824
123456789457189263698237451274618935315794628986523174561342897832971546749865312
123456789457189326689327451312865974894731562765942813541298637978613245236574198
123456789456789132798231564637542918541698327982173456874365291265914873319827645
123456789456789132789213654218645397694327815537891426862934571971568243345172968
123456789456789132789231654367942815215368947948517326531694278674823591892175463
123456789456789123789123456234598671978261534561374892342817965895642317617935248
123456789456789132879213564694375218215648397387192456932567841561824973748931625
123456789457189236689327145341572698875694312296831574934215867568743921712968453
123456789456789123789132546267948315348615972915327468892574631534261897671893254
123456789456798213879321465391862574564179832287543196938215647645987321712634958
123456789456789123789123465238591647975642831641837952862915374597364218314278596
123456789457189236869237514235841967794563821681972453518694372972318645346725198
123456789457189623689723154295674318814395276376218495961537842748962531532841967
123456789456798132789132564245361897967285341318947256632514978574829613891673425
123456789456798213789231465215647938634829571897513624571364892962185347348972156
123456789457189326689372541271534968945618273836297415312845697594761832768923154
123456789456789123789231645235867914617594832894123576572648391941375268368912457
123456789457189236869273154291364578748925361635718492912837645574692813386541927
123456789456798132789231465234675918865913274917842653592367841641589327378124596
123456789457189236986372154268534971374961825519728643645817392792643518831295467
123456789457189326896237145215394867764518293389762514538941672642875931971623458
123456789456789132798213465362948517941567823587132946635871294214395678879624351
123456789457189236896273154245931678361728945789645321512394867674812593938567412
123456789456789132879312654248637591691245378735198246362874915914523867587961423
123456789457189263869723145348267591792541638516938472635872914974315826281694357
123456789456789132879123564231567948965248371748931256394872615517694823682315497
123456789457189236689723415315268974768914523294537168532641897871395642946872351
123456789457189362869327154298614537746593821531278496372861945614935278985742613
123456789456789123789132564674591832512348697398627415967215348835964271241873956
123456789457189263689273145295631874746895321831724596568347912974512638312968457
123456789457189236869723154238615947671894523945237618394562871712948365586371492
123456789456798132789213465264975318315864927978132654832647591641589273597321846
123456789457189263689723415391245678745618392268397154812964537974531826536872941
123456789457189263689273451261837594574921836398564127945618372712395648836742915
123456789457189362869327154234615978916874523578293416392561847641738295785942631
123456789456789123789123564275634891834591672691278435567942318918365247342817956
123456789456789123789123564395614278874235691612897345947561832568342917231978456
123456789456798213978132654214675398639824175785319426567941832342587961891263547
123456789457189623869327154694815372531742896782693415948561237315274968276938541

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

TIA,
Blue.
blue
 
Posts: 975
Joined: 11 March 2013

Re: SudokuP - Min Clue Project

Postby 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!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: SudokuP - Min Clue Project

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

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.
blue
 
Posts: 975
Joined: 11 March 2013

Re: SudokuP - Min Clue Project

Postby 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
Code: Select all
1.2........3..............4.4..5.....6..............1..7...........8..........7..   O1
1.2........3..............4.4..5.....6..7...........2..8......................8..   O2
1.2........3..4...........5.5..6.....7..............1..8......................8..   O3
1.2........3..4...........5.5..6.....7..............2..8......................8..   O4
1.2......3..4...........5...6..7.....7..............2..8......................8..   O5
.2.45..........13........6.....9...........7............7..............5.....3...   B1
12..........79.......3...................1...........8.4.....67.............8....   B2
..3...........82.1.79......................7.2............3...........6..4.......   B3
........9......2....8..........4...........7................6.2......3..7.1..4...   B4
...........6.....2...............53..8..............9.........77.1..........89...   B5
1........4.....3............6......7.89.....5....4...................2.......2...   B6
.....6...4.7.....2..........................3..5..........3.....8....96..4.......   B7
......7.9.......3..6...2............6..............8.........1........4.7...8....   B8
.................69..........1...........3..5.............3.....1....97..4.....2.   B9

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
Code: Select all
                                                                                    Morph   Singles   Basics
12.......3...........4.......4.....5..6...........2.....7..............8....7....   M (O1)     18        56
12.......3...........4.......4.....5..6.....7.....1.....8...................8....   M (O2)     18        81
12.......3..4...........5....5..6.....7..............2..8......................8.   M (O3)     18        48
12.......3..4...........5....5..6.....7..............1..8......................8.   M (O4)     27        81
12.......3..4...........5....6..7.....7..............2..8.....................8..   M (O5)     19        19
12.4.....3..............5....5..6.....7.............1...8.......................4   M (B1)     23        81
12.......3...........4..............5.6...........78.2....4....................6.   M (F(B2))  33        55
12.......3..4...........5....6...........7..3..5........8..........2.............   M (TB3)    27        33
12.4.....3...................5..6.....7.............2......8........5...........4   M (E(B4))  20        57
12.......3...........4.........................5..6.....7............4.3....78...   M (B5)     22        34
12.......3..4................5..6.....7.............2............8..9...........3   M (E(B6))  17        46
12.......3...4..........5....8......7...................5........6..7...........2   M (E(B7))  20        43
12.......3...........4...5.........5.6.........4...6............7...........8....   M (E(B8))  48        48
12.......3...........4..5..67..............3......6.....8..................8.....   M (B9)      7        31

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
Code: Select all
1   2   .  | 4  .  .  | .  .  .
 3   .   .  | .  .  .  | .  .  .
 .   .   .  | .  .  .  | .  5  .
------------+----------+---------
 .   .   .  | .  .  .  | .  .  .
 .   .   .  | .  .  .  | .  .  .
 .   .   .  | .  .  .  | .  .  .
------------+----------+---------
 .   .   .  | .  .  .  | .  .  .
 .   .   .  | .  .  .  | .  .  .
 .   .   .  | .  .  .  | .  .  .

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
Code: Select all
                                                                                       Morph of

12.4.....3..............5....5..6.....7.............1...8.......................3      B1
12.4.....3..............5....5..6.....7.............1...8.......................4      B1
12.4.....3..............5....5........6..7...........1..8......................2.      O4
12.4.....3..............5....6..7........8...........1..5......................2.      E(O3)
12.4.....3..............5....6........7..8...........1..5......................2.      E(O3)
12.4.....3..............5....6......................2...5..7........8...........1      E(O4)
12.4.....3...............5...6..5.....7..............1..8.....................6..      G(M(B1)
12.4.....3...............5...6..7.....5..............1..8.....................6..      E(M(B1)
12.4.....3...................5..6.....7.............2......8........5...........4      M(E(B4)
12.4.....3...................5..6.....7.............2............8..5...........3      M(E(B4)

I live in hope of finding just one new 11 clue clueset :D Leren
Leren
 
Posts: 5019
Joined: 03 June 2012

Re: SudokuP - Min Clue Project

Postby 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-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: SudokuP - Min Clue Project

Postby 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 :D Leren
Last edited by Leren on Tue Jun 26, 2018 8:42 am, edited 1 time in total.
Leren
 
Posts: 5019
Joined: 03 June 2012

Re: SudokuP - Min Clue Project

Postby 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
Code: Select all

 1: 182764593493528176657193284841259637765831942329476815976315428214687359538942761
CF: 123456789457398612869127534698512347735964821241783956974831265586249173312675498 # 53624261

 2: 172864935493517286658293174247359618865172349319486527586721493924638751731945862
CF: 123456789457298136968371452395817264812643975746529813671932548589764321234185697 # 53557072

 3: 142875693593624187768193245451269738876431952329587416987316524215748369634952871
CF: 123456789457398612869127534698512347735964821241783956974831265586249173312675498 # 53624261

 4: 142875936593614287768293145254369718876142359319587624687421593925738461431956872
CF: 123456789457298136968371452395817264812643975746529813671932548589764321234185697 # 53557072

 5: 152837496397465281648291573269574318873912654415386927981623745526748139734159862
CF: 123456789457289631986371542678512394514793826239864157841937265362145978795628413 # 53541837



I hope this is correct, otherwise we are all in trouble!! :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: SudokuP - Min Clue Project

Postby 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.
Leren
 
Posts: 5019
Joined: 03 June 2012

Re: SudokuP - Min Clue Project

Postby 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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: SudokuP - Min Clue Project

Postby 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:
    14 ED puzzles
    12 ED solution grids, with 18 valid 11-clue puzzles
Three of the solution grids, have one non-trivial automorphism.
    One has 2 ED puzzles, and 4 puzzles total.
    Two have one ED puzzle, and 2 puzzles total.
--

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
Code: Select all
.2.45..........13........6.....9...........7............7..............5.....3... # 15449135 (B1)
12..........79.......3...................1...........8.4.....67.............8.... # 22504781 (B2)
..3...........82.1.79......................7.2............3...........6..4....... # 22979593 (B3)
........9......2....8..........4...........7................6.2......3..7.1..4... # 23068647 (B4)
...........6.....2...............53..8..............9.........77.1..........89... # 23201464 (B5)
1........4.....3............6......7.89.....5....4...................2.......2... # 23201702 (B6)
.....6...4.7.....2..........................3..5..........3.....8....96..4....... # 53380826 (B7)
.2........................2.7...........9........6.15...1..............8.....8..3 # 53541837 (O5 morph)
..3..............6..8..1.....5.............7..........67.9...........3..2........ # 53557072 (O4 morph)
............2.......8........5.....4.....3.....6.......7...........6....23.....9. # 53557072 (O4 morph)
............2.......8........5...........3.....6.......7.....4.....6....23.....9. # 53557072 (O2 morph)
..3..............6..8........5.............7..........67.9...........3..2..1..... # 53557072 (O2 morph)
.....6...........2..9......6...........9..8..24........7.............1..3........ # 53624261 (O1 morph)
.....6...........2..9......6...........9..8..24......................17.3........ # 53624261 (O3 morph)
(added)
......7.9.......3..6...2............6..............8.........1........4.7...8.... # 53658889 (B8)
1.......9...8.........72....7....3.....5........6.........3.....1................ # 53658889 (B8 morph)
.................69..........1...........3..5.............3.....1....97..4.....2. # 53658890 (B9)
.2............1............5..9.....6..72..........8................4..8..6...... # 53658890 (B9 morph)

--

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.
blue
 
Posts: 975
Joined: 11 March 2013

Re: SudokuP - Min Clue Project

Postby 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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

SudokuP: 11-clue Search Strategy

Postby 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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

PreviousNext

Return to Sudoku variants