SudokuP: 12-clue Puzzle Search

Everything about Sudoku that doesn't fit in one of the other sections

SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Wed Jul 11, 2018 11:32 pm

.
Well, since our 11-clue search has so far produced no additions to the known cases (18 puzzles on 12 CF gridsCF), coloin and I have been looking at 12-clue puzzles.

We can safely assume that the overwhelming majority of these will be minimal puzzles, since unless we find new 11-clue cases, there are only 18 x 70 non-minimal 12-clue puzzles (on CF grids).

How many 12-clue puzzles might there be? Random CF grid tests using HS testing method in (9B + 8) reduction mode (ie: reducible to 3B + 9) suggests that the number of grids with 12-clue puzzles is around 1 in 500, so from 54 million CF grids we might expect to find 100,000 have 12-clue puzzles. That would translate to 400,000 - 500,000 ED grids.

The HS method, whether in full-enumeration or in reduction mode, is much slower here than for 11-clue testing, since we have to test HSets of greater size in both cases. Added to this we must also test a lot more grids - we can only eliminate half of the grids (based on these results).

The good news is that 12-clue puzzles are much easier to find by non-HS methods. In particular we have found that one can obtain new 12-clue puzzles by {+1, -1} morphing from a starting grid, then applying the morphing to the resulting set, and repeating this process. The set of 12-clue puzzles (in the generalised SudokuP puzzle space) appears to be strongly connected by a combination of {+1, -1} and {+2, -2} morphing operations.

When we build a large enough set of morphed 12-clue puzzles, we then convert them to CF and add the reduced set to our catalog. As a result, in only a week, we have found 40,000 CF grids, 200,000 CF puzzles on these grids. That is a sizeable chunk of the number predicted by random sampling.

Of course, using this method is essentially a Markov Chain process - even if the set of 12C puzzles was fully connected by simple morphing operations, it is relatively easy to find the first 50% typically, but then it gets progressively harder to find the remainder.

Meanwhile, should any of you have a stash of 12-clue puzzles, please let me know! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 590
Joined: 27 May 2015

SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Wed Jul 11, 2018 11:59 pm

.
We have sufficient data to give a clue-pattern profile of the known 12C puzzles.

We have 196,164 CF puzzles on 39,696 grids.

  • 54,611 of the puzzles are 2CB (max 2 clues in a box)
  • 134,693 are 3CB
  • 6,841 are 4CB
  • 23 are 5CB

We might then expect the HS reduction methods (9B + 9 for 3CB, 9B + 8 for 4CB, etc), to be able to identify, if necessary, around 75% of the puzzles, ie all except the 2CB cases.

But most of these 2CB puzzles, as blue conjectured, have 3 clues in a row or column. So it looks like 90% of cases can thus be identified by HS reductions.

When we hit the wall with our "Morphing Markov" method, we can hopefully find new instances via HS reduction, and then feed them into the morphing process to find others.
User avatar
Mathimagics
2017 Supporter
 
Posts: 590
Joined: 27 May 2015

SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Thu Jul 12, 2018 12:44 am

.
Since they appear to be rare, here is an example of 12-clue CF puzzle with 5CB:

Code: Select all
 . . . | . 5 . | . . .
 . . 6 | . . . | . 3 .
 . . . | . . . | . . .
 =====================
 . . . | . . 1 | . . .
 5 . 7 | . . . | . . .
 2 3 9 | . . . | . . .
 =====================
 . . . | . . 8 | . . .
 . . 2 | . . 4 | . . .
 . . . | . . . | . . .


A list of all 23 found so far, with CFI's (CF indices):

Hidden Text: Show
Code: Select all
....5......6....3...............1...5.7......239...........8.....2..4............ # 20204372
......7.9.....81....9...4.5..............5..........2...........1........3..8.... # 20996860
............7..............2.4.....85.9..3...6.......4....3..1..8................ # 23057143
............7..............2.......45.9..3...6.4.....8....3..1..8................ # 23057314
............7..............2.......4519..3...6.......8....3..1..8................ # 23057314
..3...........8..1.....2..........42...5..3.....6..19...........8................ # 23074445
...............2..97.3....................1....1......695..............7.34...... # 23075135
...............2..97.3....................1....1......6.5........2.....7.34...... # 23075135
1............8...........5.........8..............3......9..61....721......5..... # 50971372
......7..4...........2...........8..215......6.9.............4...........3..9.... # 52962497
...........7...........1..5..................6........5.2.......3.1..9..7.4...2.. # 53501358
.................69...............45......97...6.....3.....2.1...........3..8.... # 53556930
.......8.........69...............4.......975..6.....3.....2.1...........3....... # 53556935
........9.....................9.8..2.....4.....67.5.......6..1.........8.......2. # 53658888
...4...........2..9.............8.4....62......6.15..3..5........................ # 53658888


Notice that the last two are directly adjacent to known 11C puzzles.
User avatar
Mathimagics
2017 Supporter
 
Posts: 590
Joined: 27 May 2015

SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Thu Jul 12, 2018 1:40 am

.
And speaking of known 11C puzzles, Leren pointed out that every 11C-puzzle has at least 70 x 12-clue (non-minimal) puzzles, of course.

Which made me wonder, how many minimal 12-clue puzzles do they have?

Code: Select all
  15449135 has   23 12C minimal puzzles
  22504781 has   91 12C minimal puzzles
  22979593 has  361 12C minimal puzzles
  23068647 has  133 12C minimal puzzles
  23201464 has  325 12C minimal puzzles
  23201702 has  158 12C minimal puzzles
  53380826 has   59 12C minimal puzzles
  53541837 has  220 12C minimal puzzles
  53557072 has  683 12C minimal puzzles
  53624261 has  267 12C minimal puzzles
  53658889 has 2010 12C minimal puzzles
  53658890 has 3245 12C minimal puzzles


Note that these figures might well need adjusting up, as they represent simply those cases that have been turned up by our Morphing Markov process, not by HS enumeration.
User avatar
Mathimagics
2017 Supporter
 
Posts: 590
Joined: 27 May 2015

Re: SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Thu Jul 12, 2018 9:36 am

.
Here is an example of a 2CX puzzle, ie no more than 2 clues in ANY row, col, box or position.

Code: Select all
 1 . . | . . . | . 8 .
 . . . | . . . | . . .
 . . . | . . . | 5 . .
 ------+-------+-------
 . 6 . | . . . | . . .
 . . . | . 1 . | . 2 .
 . . . | . 2 . | . . .
 ------+-------+-------
 9 . 7 | . . ..| . . .
 . . . | 5 . . | 3 . .
 . . . | . . 3 | . . .


Around 1.2% of the CF puzzles are like this. These will never be found by any of our 4 HS reduction methods (9B+N, 9R+N, 9C+N, 9P+N). (I haven't yet looked at its F/G/E isotopes).

[ EDIT ] 2CX property confirmed in F/G/E
Last edited by Mathimagics on Thu Jul 12, 2018 12:02 pm, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 590
Joined: 27 May 2015

Re: SudokuP: 12-clue Puzzle Search

Postby coloin » Thu Jul 12, 2018 10:45 am

Indeed, have to say thanks to Mathimagics for fantastic programming and induging in the ideas which have got so far in this exercise !

I am sort of hoping that the whole set of 12-clue puzzles are connected with the {-1+1}
It would be an unlikely puzzle which wasnt connected - especially as each puzzle has at least 2 or 3 "different" morphs to use as seeds
Of note that a new non-minimal 12C hasn't turned up .... which is bad news for a new 11C. I think blue was aware of this :D :(

It might even be possible to fix a few clues and speed up things
For example a 1 @ r1C1 and 2 @ r1c4 or 1 @ r1c1 and 2 @ r4c4 [above puzzle does have both]
There has to be 8 clue numbers and the extra 4 clues have to go somewhere !

if we started at one random puzzle and set a generative process - if we got the same set of puzzles on a repeat process that would be pretty fair conclusion that we got them all !

We would have by then a good set of potential outlying puzzles - say ones without 3 clues in a R/C/B/Blue transform [P = position] [ like above] or those made by a made by {-2+2} [significantly slower even with Mathimagics extremely fast program !] These might not be in the set .... but we perhaps will see !
coloin
 
Posts: 1709
Joined: 05 May 2005

Re: SudokuP: 12-clue Puzzle Search

Postby Leren » Thu Jul 12, 2018 11:01 pm

Mathimagics Wrote : Meanwhile, should any of you have a stash of 12-clue puzzles, please let me know!

I've just made an adjustment to my 11 clue search process to look for 12 clue puzzles, and I'm starting to build a stash of them. Here's what I've got after about a day.

Hidden Text: Show
12.......3..4..5.......6.....6..4.....7...........1.....8......................6. 125897643369412578874356219916574382247983156583621497458269731691735824732148965
12.......3..4..5.............6..4.....7.....6.....1.....8......................6. 125897643369412578874356219916574382247983156583621497458269731691735824732148965
12.......3..4..5.............6..4.....7.........6.1.....8......................6. 125897643369412578874356219916574382247983156583621497458269731691735824732148965
12.......3..4..5.............6..5.....7..............2..8..................8..6.. 124567893389421576765398214246985731817234965953176482478612359692753148531849627
12.......3..4..5.............6.....4..7...........2.....8..................6..8.. 125893467389476521764215398256731984817964235943582176578349612692158743431627859
12.......3..4..5........2....6........4.....7.....1.....8..................8..... 125683479389472516467159238816547392934268157572391684258934761691725843743816925
12.......3..4..5.............6........4.....7.....1.....8..................8...2. 125683479389472516467159238816547392934268157572391684258934761691725843743816925
12.......3..4..5.......6.....6........4.....7.....1.....8...................8.... 125379684369418572847256319516847293984623157732591468458962731291735846673184925
12.......3..4..5..........6..6........4.....7.....1.....8...................8.... 125367984369418572847259316716843259984625137532971468478532691251796843693184725
12.......3..4..5.............6........4.....7.....1.....8...........6.......8.... 125367984369418572847259316716843259984625137532971468478532691251796843693184725
12.......3..4..5.............6........4.....7.....1.....8..............6....8.... 125379684369418572847256319516847293984623157732591468458962731291735846673184925
12.......3..4..5.....6.......6........4...........1.....7...........8.......7.... 125893674369417582748625319516742938874936125932581467487369251691258743253174896
12.......3..4..5.............6........4...........1..5..7..............8...3..... 125673489369482517478159236716534892254896173893721645947268351631945728582317964
12.......3..4..5.....2.......6........5..7...........1..8.....................8.. 124579683389416572567238149816392457935147268472685391248761935691853724753924816
12.......3..4..5.............6........5..7...........1..8...................2.8.. 124579683389416572567238149816392457935147268472685391248761935691853724753924816
12.......3..4..5.......6.....6........5..7...........1..8......................8. 124985367369472518857316249716249853985137624432568971578691432241853796693724185
12.......3..4..5..........6..6........5..7...........1..8......................8. 124685379369472518857319246416293857985147623732568491548731962291856734673924185
12.......3..4..5.............6........5..7...........1..8...........6..........8. 124685379369472518857319246416293857985147623732568491548731962291856734673924185
12.......3..4..5.............6........5..7...........1..8..............6.......8. 124985367369472518857316249716249853985137624432568971578691432241853796693724185
12.......3..4..5.............6........5...........4..1..7...........8.........3.. 124589673369417582578236149716892435245173896893654721957341268631728954482965317
12.......3..4..5........6....6........5..............1..7..............8.......7. 124675893369482517758319624416938752875124936932567481587241369691753248243896175
12.......3..4..5.............6....5...7.3............1..8...........6............ 124563897369478512875219436416782359297135684583694721638941275751826943942357168
12.......3..4..5.............6........7.3............1..8.....5.....6............ 124563897369478512875219436416782359297135684583694721638941275751826943942357168
12.......3..4..5.............6.....9..7..8...........1..5.....................2.. 124587963379416582568329147816742359957138624432695871695271438241863795783954216
12.......3..4..5.............6........7..8...........1..5....................94.. 124583967379416582568927134416732859257198643893645271645271398931864725782359416
12.......3..4..5...........4.6........7..8...........1..5.....................8.. 124853769379416582568927134416532978957148623283679451695281347831764295742395816
12.......3..4..5.............6........7..8.9.........1..5.....................8.. 124853769379416582568927134916532478257148693483679251695281347831764925742395816
12.......3..4..5.............6........7..8.........4.1..5.....................8.. 124853769379416582568927134416532978957148623283679451695281347831764295742395816
12.......3..4..5.............6........7..8...........1..5............9........8.. 124853769379416582568927134916532478257148693483679251695281347831764925742395816
12.......3..4..5.............6........7..8...........1..5.............9.......8.. 124853769379416582568927134416532978957148623283679451695281347831764295742395816
12.......3..4..5.............6........7....8..4......19....................6..... 124357698398461572765928314816239745237145986549876231971582463653714829482693157
12.......3..4..5.............6..9.....7.....8.....1.....4..................2..... 125963487379482516468157329816349752947625138532871694694538271251794863783216945
12.......3..4..5.............6........7.....8.....1.....4..................5....9 125967483379482516468135927516849732247653198893271654654398271931724865782516349
12.......3..4..5...........5.6........7.....8.....1.....4..................8..... 125769843379482516468135927516978432947623158283541679694357281831294765752816394
12.......3..4..5.............6........7.9...8.....1.....4..................8..... 125769843379482516468135927916578432247693158583241679694357281831924765752816394
12.......3..4..5.............6........7.....8...5.1.....4..................8..... 125769843379482516468135927516978432947623158283541679694357281831294765752816394
12.......3..4..5.............6........7.....8.....1.....4.........9........8..... 125769843379482516468135927916578432247693158583241679694357281831924765752816394
12....9..3..4..5.............6........7.....8.....1.....5..................2..... 124563987379482516568197324416358792957624138832971645645839271291745863783216459
12.......3..4..5.............6........7......5...21.....8..................6..... 124583769369472518785169234816347952247956183593821476478235691631794825952618347
12.......3..4..5.............6........7.......5..21.....8..................6..... 124583769369472518785169234816347952247956183953821476478235691631794825592618347
12.......3..4..5.............6........7..........21.....8...............5..6..... 124583769369472518785169234816347952247956183953821476478235691631794825592618347
12.8.....3..4..5.............6........7...........1.....4..........2...8......... 125869473379412586468375219916587342847293165532641897294738651651924738783156924
12.......3..4..5.............67.......7...........1.....4..............8...8..... 125967843379482516468135729516798432847623195293541687684379251731254968952816374
12.......3..4..5.............6.9......7...........1.....4..............8...8..... 125967843379482516468135729516798432847623195293541687684379251731254968952816374
12.......3..4..5.............6........7...........1.....4.7............8...8..... 125967843379482516468135729516798432847623195293541687684379251731254968952816374
12.......3..4..5.............6...7....7..............1..5...........8.........8.. 124853967379416582568729134416532798857194623293687451685241379731968245942375816
12.......3..4..5.............6....9...7..............1..5...........8.........8.. 124853967379416582568729134416532798857194623293687451685241379731968245942375816
12.......3..4..5.............6........7..............1..5....7......8.........8.. 124853967379416582568729134416532798857194623293687451685241379731968245942375816
12.......3..4..5.............6........7..............3.....9..8..9..1............ 124395687398476512765218349536942871247183965981657423413769258659821734872534196
12.....9.3..4...5............6.......7......8.....8.....5...........7............ 128573694369482751547916823856241937273695148491738265715369482934827516682154379
12.......3..4...5............6.5......7.....8.....4.....8....................1... 124597683389416752675238149836952471947163528512784396768349215291675834453821967
12.......3..4...5............6........7.8.........1..5..8..........7............. 125897634369412758784536219416759382537284196892361475278943561941675823653128947
12.......3..4...5............6........7..............2..8.1...................86. 124567389389421756675398124856932471237145698941786532798613245562874913413259867
12..9....3..4...5............6.............7...8........7..4...........1......... 125698743369427158784153926456271389913586274278349615837914562642735891591862437
12.......3..4...5........9...6..............2..7..4.....8...................8.... 124659387379418256865723491416872935983165742257934618798241563631597824542386179
12.......3..4...5........3...6..............2..7..4.....8...................8.... 124653987379418256865729431416872395983165742257394618738241569691537824542986173

Leren
Leren
 
Posts: 3284
Joined: 03 June 2012

SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Fri Jul 13, 2018 4:10 am

.
Hi Leren,

Your initial set produced one new grid, but that's only the beginning.

I'm running that grid through the MM process and we'll see what we get (that takes a few hours). Every new grid has excellent chance of producing more ... 8-)

[ EDIT ] Finished MM, net yield was 4 new grids + 8 new puzzles (CF grids/puzzles)
User avatar
Mathimagics
2017 Supporter
 
Posts: 590
Joined: 27 May 2015

Re: SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Fri Jul 13, 2018 6:21 am

.
We now have 234,800 CF puzzles on 47,473 grids.

colin is responsible for most of these (45K or more), whatever he's doing, it works a treat! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 590
Joined: 27 May 2015

Re: SudokuP: 12-clue Puzzle Search

Postby Leren » Fri Jul 13, 2018 6:28 am

Hi Mathemagics, perhaps you could tell which of my hits was a "new grid" and the puzzle details in your format (yep, like everyone else I do have an ego :D).

I'm only really doing this for fun, because the 11 clue search was going nowhere, and I could go months before I get a new hit, if any (which I doubt). At least the 12 clue search is likely to produce more regular hits.

Also, from a scientific perspective, since my search method is different from yours, you have a genuine independent check, even if it only produces spasmodic results, a point the scientific method boffins would hug themselves over.

Leren
Leren
 
Posts: 3284
Joined: 03 June 2012

Re: SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Fri Jul 13, 2018 9:00 am

Leren wrote:yep, like everyone else I do have an ego.


OMG!!! :o

Hmm, tracking the successful item down was harder than I thought, but I think this is right:

Your puzzle + solution:
Code: Select all
12.......3..4..5.............6........7....8..4......19....................6.....
124357698398461572765928314816239745237145986549876231971582463653714829482693157


Canonicalised form:
Code: Select all
..3...7..4........6.......5..........78.......9..3..2.....4.....1................ # 38300855
123456789457189263689273415264518397378692541591734826835941672716825934942367158 # 38300855
User avatar
Mathimagics
2017 Supporter
 
Posts: 590
Joined: 27 May 2015

SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Sun Jul 15, 2018 8:20 am

.
We have now found 50,800 CF grids with 12-clue puzzles.

We would like to get a better estimate for the actual number than the crude random sampling provided.

It seems a good idea to look at the distribution of 12C puzzle grids to see whether they are reasonably well distributed across the CFI range (grid CF index, 1 to 53666689).

Of course it turns out they are NOT, which I might have predicted had I done the same analysis for the 10C/11C grid pool!

Dividing the CF grids into intervals of size 1,000,000 (ie using the first 2 digits of the grid #'s), we show for each interval N, the number of grids with 12C puzzles found so far, the % of the total, and the corresponding % of pool grids.

The 12 known 11C grids are indicated with a "*" for each grid.

The pool grids have the property that we know the MNC (minimum number of clues) for each grid is 10 or less.

Hidden Text: Show
Code: Select all
   # of 12C grids = 50821

   N       12C    %12C     %Pool   
  ==============================
  00:        0   
  01:        0
  02:        0
  03:        0
  04:        1
  05:        3
  06:        2
  07:       13    0.03%    0.03%
  08:       56    0.11%    0.14%
  09:       94    0.18%    0.38%
  10:       68    0.13%    0.37%
  11:      192    0.38%    0.32%
  12:       62    0.12%    0.23%
  13:      810    1.59%    2.02%
  14:      593    1.17%    1.66%
  15:     1915    3.77%    3.97%  *
  16:      222    0.44%    0.60%
  17:      744    1.46%    2.37%
  18:      765    1.51%    2.60%
  19:     3036    5.97%    6.06%
  20:     2797    5.50%    4.81%
  21:     4238    8.34%    7.72%
  22:     5661   11.14%    8.08%  **
  23:     2941    5.79%    3.18%  ***
  24:       24    0.05%    0.08%
  25:       34    0.07%    0.26%
  26:       77    0.15%    0.43%
  27:       80    0.16%    0.22%
  28:       17    0.03%    0.14%
  29:      496    0.98%    2.20%
  30:        7    0.01%    0.08%
  31:       36    0.07%    0.23%
  32:      312    0.61%    0.81%
  33:      151    0.30%    0.48%
  34:      351    0.69%    1.20%
  35:      291    0.57%    1.08%
  36:      159    0.31%    0.46%
  37:       83    0.16%    0.56%
  38:      125    0.25%    0.77%
  39:       33    0.06%    0.24%
  40:      792    1.56%    2.47%
  41:       35    0.07%    0.30%
  42:     1414    2.78%    3.60%
  43:     1161    2.28%    2.85%
  44:       95    0.19%    0.69%
  45:      614    1.21%    1.91%
  46:     1252    2.46%    2.96%
  47:      595    1.17%    1.69%
  48:      725    1.43%    2.17%
  49:       23    0.05%    0.19%
  50:      367    0.72%    2.04%
  51:     3705    7.29%    7.80%
  52:     3259    6.41%    6.61%
  53:    10295   20.26%   10.92%  ******



The distinct clustering of grids in the intervals is evident.

Intervals 51-53 constitute 43% of 12C grids found, 25% of the pool grids, and 50% of the known 11C grids.

Intervals 19-23 constitute 37% of 12C grids found, 30% of the pool grids, and 42% of the known 11C grids.

Interval 53 is in fact only 667K wide, and has the highest scores in every category. Intervals 0-9 constitute 10 million, nearly 20% of the total grids, yet has virtually no impact.

Why should this be so? :?

It does mean that we can find new 12C grids for our seeding process, and get a better estimate of the expected number, by targeting the intervals most likely to yield new grids.

The same process (testing random grids in specific intervals) will also provide increasingly accurate predictions of the likely total # of 12C grids we are looking at.
User avatar
Mathimagics
2017 Supporter
 
Posts: 590
Joined: 27 May 2015


Return to General