The New Sudoku Players' Forum

by **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-)

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

by **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

Notice that the last two are directly adjacent to known 11C puzzles.

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

by **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

by **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

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 !

by **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

Leren

by **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)

by **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-)

by **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

).

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

by **Mathimagics** » Fri Jul 13, 2018 9:00 am

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................ # 38300855 123456789457189263689273415264518397378692541591734826835941672716825934942367158 # 38300855

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

by **Mathimagics** » Mon Jul 16, 2018 9:15 pm

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

by **Mathimagics** » Tue Jul 17, 2018 3:27 am

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

by **dobrichev** » Tue Jul 17, 2018 6:25 pm

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.

The New Sudoku Players' Forum

SudokuP: 12-clue Puzzle Search

SudokuP: 12-clue Puzzle Search

SudokuP: 12-clue Puzzle Search

SudokuP: 12-clue Puzzle Search

SudokuP: 12-clue Puzzle Search

Re: SudokuP: 12-clue Puzzle Search

Re: SudokuP: 12-clue Puzzle Search

Re: SudokuP: 12-clue Puzzle Search

SudokuP: 12-clue Puzzle Search

Re: SudokuP: 12-clue Puzzle Search

Re: SudokuP: 12-clue Puzzle Search

Re: SudokuP: 12-clue Puzzle Search

SudokuP: 12-clue Puzzle Search

SudokuP: 12-clue Puzzle Search

SudokuP: 12-clue Puzzle Search

Re: SudokuP: 12-clue Puzzle Search