## SudokuP: 12-clue Puzzle Search

For fans of Killer Sudoku, Samurai Sudoku and other variants

### SudokuP: 12-clue Puzzle Search

.
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!

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### SudokuP: 12-clue Puzzle Search

.
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.

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### SudokuP: 12-clue Puzzle Search

.
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...... # 230751351............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.

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### SudokuP: 12-clue Puzzle Search

.
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.

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP: 12-clue Puzzle Search

.
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.

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP: 12-clue Puzzle Search

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

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: 2216
Joined: 05 May 2005
Location: Devon

### Re: SudokuP: 12-clue Puzzle Search

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: 4338
Joined: 03 June 2012

### SudokuP: 12-clue Puzzle Search

.
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 ...

[ EDIT ] Finished MM, net yield was 4 new grids + 8 new puzzles (CF grids/puzzles)

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP: 12-clue Puzzle Search

.
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!

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP: 12-clue Puzzle Search

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

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: 4338
Joined: 03 June 2012

### Re: SudokuP: 12-clue Puzzle Search

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

OMG!!!

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................ # 38300855123456789457189263689273415264518397378692541591734826835941672716825934942367158 # 38300855`

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### SudokuP: 12-clue Puzzle Search

.
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.

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### SudokuP: 12-clue Puzzle Search

.
In light of the above, it seems worthwhile to do a similar table which includes puzzle counts.

Here we look only at the 611,502 10C pool grids, to see how many have 12C puzzles, and the results are quite interesting.

Hidden Text: Show
Code: Select all
`12C analysis by 10C Pool grids:  N = interval (grid # / 1000000)  N12CG = grids in pool with 12C puzzles  NPOOLG = grids in pool  N12CP = puzzle count for grids in pool  N      N12CG     %    NPOOLG     %     N12CP      %   ===================================================== 04          0               5   0.00%       0         05          0              20   0.00%       0         06          2   0.00%      54   0.01%       2   0.00% 07          6   0.01%     162   0.03%       9   0.00% 08         22   0.05%     865   0.14%      34   0.01% 09         65   0.14%    2345   0.38%     102   0.04% 10         44   0.09%    2256   0.37%      83   0.03% 11         96   0.20%    1952   0.32%     170   0.07% 12         33   0.07%    1469   0.24%      66   0.03% 13        659   1.40%   12336   2.02%    1668   0.65% 14        413   0.88%   10200   1.67%     780   0.30% 15       1647   3.51%   24638   4.03%    4546   1.76% 16        154   0.33%    3235   0.53%     294   0.11% 17        636   1.36%   14563   2.38%    1526   0.59% 18        679   1.45%   16095   2.63%    1817   0.70% 19       2872   6.12%   37143   6.07%   10912   4.22% 20       2608   5.56%   29440   4.81%   13548   5.24% 21       4046   8.62%   47001   7.69%   15629   6.04% 22       5429  11.57%   50678   8.29%   31939  12.35% 23       2882   6.14%   17985   2.94%   31711  12.26% 24         15   0.03%     560   0.09%      29   0.01% 25         24   0.05%    1582   0.26%      52   0.02% 26         57   0.12%    2648   0.43%     107   0.04% 27         58   0.12%    1331   0.22%     150   0.06% 28         12   0.03%     840   0.14%      14   0.01% 29        476   1.01%   13442   2.20%    1221   0.47% 30          3   0.01%     489   0.08%       3   0.00% 31         21   0.04%    1368   0.22%      26   0.01% 32        264   0.56%    4935   0.81%     657   0.25% 33        111   0.24%    2929   0.48%     243   0.09% 34        306   0.65%    7367   1.20%     912   0.35% 35        249   0.53%    6559   1.07%     584   0.23% 36        130   0.28%    2832   0.46%     465   0.18% 37         62   0.13%    3432   0.56%     121   0.05% 38         85   0.18%    4738   0.77%     215   0.08% 39         24   0.05%    1547   0.25%      36   0.01% 40        725   1.54%   15011   2.45%    2726   1.05% 41         28   0.06%    1832   0.30%      53   0.02% 42       1226   2.61%   22082   3.61%    3600   1.39% 43       1062   2.26%   17375   2.84%    4125   1.60% 44         66   0.14%    4213   0.69%     132   0.05% 45        549   1.17%   11709   1.91%    1383   0.53% 46       1061   2.26%   18137   2.97%    2605   1.01% 47        494   1.05%   10293   1.68%    1224   0.47% 48        643   1.37%   13235   2.16%    1528   0.59% 49         15   0.03%    1208   0.20%      17   0.01% 50        331   0.71%   13212   2.16%     750   0.29% 51       3467   7.39%   46933   7.68%   12185   4.71% 52       3049   6.50%   41186   6.74%   10525   4.07% 53      10024  21.36%   66035  10.80%   98040  37.92% ----------------------------------------------------         46930          611502          258564All 12C: 52057                          265882         --------------------------------------------Non-pool: 5127   9.85%                    7318   2.75%`

For all 12C (CF) puzzles found so far, 90.15% of the grids, and 97.25% of the puzzles involve 10C pool grids.

I don't have a distribution yet for the non-pool grids with 12C puzzles, but am working on it.

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### SudokuP: 12-clue Puzzle Search

.
Catalog now has 267,262 CF puzzles on 52,253 grids

I am happy to report that I am at last making a significant contribution with my new Find12C-RW process, which is finding new puzzles on a regular basis. (As noted above, coloin has produced most of our finds so far, and Leren has also contributed.)

Find12C-RW is a true Markov process, ie a "random walk". We start with a random 12C puzzle from the catalog, call it X, say.

We iterate (forever) as follows:

• randomly choose N (N = 1, 2 or 3) of the 12 clues in X

• randomly choose N morph cells (clue replacement cells)

• if the morph produces a valid 12-clue puzzle Y, then set X = Y (adding to the catalog if Y is new)

This is essentially the same process that perturbation-based random Sudoku grid generators use (eg Pittenger/Jacobsen-Matthews). If the solution space is fully connected by the perturbation operations then eventually it will generate all possibilities.

For 12-clue SudokuP's, we don't really know whether the space is fully connected by {+N,-N} morphs (N = 1, 2, 3) but it does seem highly likely from our results so far. If and when the new puzzles dry up we can always try adding N = 4 to see if that turns up anything.

Testing for N = 3 morphing is feasible here since we only apply it to the selected clues, we don't attempt to enumerate all 3-clue morph combinations. So an N = 3 test takes at worse 9 times an N = 2 test.

It can do 1000 iterations per second, and takes on average 1000 iterations to obtain a new Y (ie a replacement for X). Currently it seems to take about 180-200 Y's on average (3 minutes) to produce a new puzzle, ie one we haven't seen already.

I'm running 4 copies, each of which has produced nearly 300 new puzzles over the first 12 hours.

I'm keeping a log of each new puzzle event, so we can monitor the (inevitable) increase in times between new-puzzle events.

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP: 12-clue Puzzle Search

Mathimagics wrote:For all 12C (CF) puzzles found so far, 90.15% of the grids, and 97.25% of the puzzles involve 10C pool grids.

This is very informative statement for those who know what 12C (CF) puzzles and 10C pool grids means.
dobrichev
2016 Supporter

Posts: 1830
Joined: 24 May 2010

Next

Return to Sudoku variants