The New Sudoku Players' Forum

[Mathimagics]

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

Apologies!

• CF grids are grids in canonical form. Using blue's canonicalisation functions we map any SudokuP grid to one of the 53,666,689 different canonical form grids. The 8-digit grid #'s you sometimes see grids/puzzles tagged with are the position of the CF in the ordered list of all CF grids (aka CFI = CF Index).

• 12C CF puzzles are 12-clue SudokuP puzzles in canonical form. They have a unique solution which is a CF grid. Using blue's CF function we can take any 12-clue puzzle and convert it to CF, by passing the puzzle + solution to the function, which converts the solution to CF and applies the same transformations to the puzzle. Our "12C puzzle catalog" is all the different 12C CF puzzles we have collected.

• 10C Pool Grids are the 611,502 CF grids which were remaining after the 10-clue Search project had eliminated all CF grids with provable MNC (Minimum Number of Clues) greater than 10. This is not the MCP (minimum clues in a puzzle), but a lower bound obtained by UA/HSet analysis. These are only "10C" in the sense that they are the remaining candidates, the only grids that could possibly have 10C puzzles.

[dobrichev]

Thank you.

May I ask whether a lower bound obtained by UA/HSet analysis means a set of larger than the target givens number of mutually disjoint UA is found in the solution grid, or it includes more comprehensive analysis?

From what I understood, you sorted the solution grids using criterion A (canonical form) and investigate whether the puzzles that are "close" by criterion A, are also close by criterion B (number of non-redundant givens).
Of course this happens when some sub-structures of the grid match the both criteria A and B.
A good invention would be to modify normalization criterion A so that it matches criterion B as close as possible. Surely blue's transformation is based on clarity and speed, and the matching substructures (most likely the top band) is a coincidence.
And you could exploit this coincidence in more direct form - as top band number rather than the pool number.

I am reading your posts but can't follow the progress of this project, mainly due to the terminology and abbreviations problems. I am a bit disappointed that instead of finalising 11 clues search, you (and coloin) spread your efforts in finding 12s.

Cheers and Good luck!

[eleven]

Thanks for the posts, Mladen, generally i agree (and already learned by the last answer).

[Leren]

Mathimagics wrote : Catalog now has 267,262 CF puzzles on 52,253 grids

I know that this is a moving target but can't we say something heuristically significant about the likely existence of undiscovered 11 clue puzzles ??

We know that there are 12 grids with 11 clue puzzles, and we know that, trivially, they would all have 70 x 12 clue puzzles. So (assuming yo have already included these trivial extensions in your stats) if we subtract those out we can say something like "Catalog has 266,422 CF puzzles on 52,241 grids. So it appears that only one per 100 grids has a 12 clue puzzle, but if it does, it has, on average, about 5. So, of the non-known 11 clue puzzle grids, what is the grid with the maximum number of 12 clue puzzles ? Let's say it's 10 and also let's also say we have discovered, say, 50% of all the 12 clue puzzles there are. And let's say there is no peculiar bias in your (and Coloin's) search processes that somehow avoids 11 clue puzzles.

I'd expect that you would have a grid with, say, 35 12 clue puzzles and you would already have noticed that 11 of the 12 clues are common to the 35 sets.

If you haven't found this can't we say that the existence of an undiscovered 11 clue puzzle is extremely unlikely ? Something like the chance of tossing a coin 70 times and getting 10 heads when the expected number is 35.

I've long forgotten my probability theory from school, but I'm sure it's a pretty minute number. Does any of this make sense ?

Leren

[Mathimagics]

May I ask whether a lower bound obtained by UA/HSet analysis means a set of larger than the target givens number of mutually disjoint UA is found in the solution grid, or it includes more comprehensive analysis?

The grids were first reduced by eliminating grids with UA cliques (sets of mutually disjoint UA's) of size > 10.

Then the remaining grids were further reduced by MHS (minimum UA-hitting-set size). After eliminating grids with MHS > 10 we were left with the "10C pool" of 611,502 grids.

I am reading your posts but can't follow the progress of this project, mainly due to the terminology and abbreviations problems. I am a bit disappointed that instead of finalising 11 clues search, you (and coloin) spread your efforts in finding 12s.

The 11C search is in fact very much active and ongoing. See my previous status report here, for example. I am going to post an update sometime later today.

And in a way the 12C search is revealing information about the 11C search. We have not found any non-minimal 12-clue puzzle that is not equivalent to one of the known 11-clue cases. This tends to confirm what the 11C search is suggesting, that there are probably no more 11-clue puzzles to be found.

PS: If you want clarifications of any terminology/abbreviations I am happy to explain them. Just ask! (by PM or post)

[dobrichev]

After eliminating grids with MHS > 10 we were left with the "10C pool" of 611,502 grids.

Do you

• did elimination of part of all grids so that 611,502 remain to be processed/eliminated, or
• these 611,502 grids at some point hit all known UA by known <=10 clues but you forgot to call the solver at this point to prove/disprove the uniqueness of puzzle(s) solution?

For the first case I see nothing special in this pool.
For the second I see an example where focusing on a single task gives better result. At least for men. And some doubts arise on what method are you using for 11-clue search.

Else you know 611,502 grids that have at least one valid 10-clue puzzle and now you are searching for 11s and 12s

[Mathimagics]

• these 611,502 grids at some point hit all known UA by known <=10 clues but you forgot to call the solver at this point to prove/disprove the uniqueness of puzzle(s) solution?

This is sort of correct, but we did NOT forget to call the solver. We simply asked the question for each grid:

• does there exist a HSet of size <= 10 clues?

'The answer was YES for 611,502 grids, and that is our pool of "candidates". These are the only grids that might possibly have 10-clue puzzles.

This question is considerably easier to answer than "Does this grid have a 10-clue puzzle?"

To answer the main question (is there a 10-clue puzzle?) we need to enumerate, for each grid, all Hsets of size <= 10, and test-solve all the possible puzzles for each HSet.

We have in fact already done this for about 120,000 of the grid pool (ie approx 17%) and have found no 10-clue puzzles. Nor do we expect to find any, given the scarcity of 11-clue puzzles.

I now suggest that we switch to the "Min Clue Project" thread to discuss this further! This thread is supposed to be about 12-clue puzzles.

[dobrichev]

I now suggest that we switch to the "Min Clue Project" thread to discuss this further! This thread is supposed to be about 12-clue puzzles.

Disagree. Rename the thread to "minimal 12-clues", else 10-clues puzzles are valid here as subset of 12s

[Mathimagics]

.
Ok, Mladen, you have got me there!

How about this?

• SudokuP: An Inquiry into the Number of Puzzles Having 12-clues and Having the Property that No Clue Is Redundant, and an Investigation into the Feasibility of a Complete Enumeration Of All Such Puzzles

[dobrichev]

This is fairly incomplete. In-line explanation of "redundant" is a must. Possibly same for "complete".
And you missed the key point that enumeration is done for all ED puzzles, which itself requires in-line explanation what Essentially Different means in this context.
SudokuP could be left as a reference to a page that lists the several hundreds synonyms and definitions. Ordered by date, latest first so that "SudokuP" isn't on the bottom.

[Mathimagics]

.
Great suggestion, I approve!

[coloin]

Hey ! dobrichev go easy on Mathimagics !
Its very true that we have been making a few 12C SudokuP puzzles - with modifications of your software [I think !! ].
Its also true that we have been very aware that no new non-minimal 12C puzzles have been generated - despite [probably] generating a very significant proportion of the total estimated.
In some ways the search is easier than normal sudoku [less clues] but in others there is the added factor of the extra position constraint makes it more complicated !
The 17C enumeration project is ongoing , despite the fact that a complete {-3 +3} has been performed and yieded no new puzzles.
We have only just heard from blue that he has apparently performed a complete search for 11C

I agree that the ordering of the set of 50 million grids could have been done more advantageously - if we had iinclination .... say in terms of MCN [minimum clique number]

Anyway welcome to the project !

[dobrichev]

Hi Coloin,

The best ordering is the trivial A==B, i.e. by the number of 12-clue puzzles.

The MCN approximation is a good candidate, although from my statistically insignificant experience it is a better measure for a complexity of the scanning process rather than a likelihood for low-clue puzzle existence. But I could be wrong.
Other issue is the unreliability in finding the absolute minimal clique. From 17-clue search a measurable portion (say 5%) of the grids, after finding the MCN using the chosen UA, happened to have an additional large UA disjoint from the clique, this automatically increasing MCN by one. Doing this trick on the loads of other MCN candidates is expensive.

An easier ordering would be evaluation of bands followed by ordering by best-rated band (instead of lexicographically minimal band if the current canonicalization is based on it). This would place grids having the same top-rated band from within all 6 bands/stacks close to each other.

Variations of the latest include ordering by best-rated 2-rookery or 3-rookery. Almost proved fruitless. Or not?

MCN reordering is avoidable by adding MCN tag to a grid in a unordered or arbitrary ordered list of grids.
Tagging all 6 band indexes or variety of rookeries is likely unnecessary because they are calculated easy and fast on the fly.

[coloin]

Thanks for that ...
It was strange why the spread of the puzzles was not all the way through ,,,, and i dont now think it was the mcn of the solution grids. But an mcn of 13 is a good way to rule out a grid.
Thinking about it ....It maybe just possible that the first band with a repeating minirow [ with a 6 at r2c3] and low minlex number - somehow precludes a 12C puzzle !!! [ but I havent looked at that ]
By definition all the 416 bands are compatible with sudokuP .

Those fruitless discoveries sometimes can be useful .....

I suppose we await a reasonable estimation of the total number of 12C puzzles but can we really know how big the tail of the distribution is ?.

Regarding the generation of 12C puzzles, and where we are going with this since we now know there are no more new 11C puzzles.
We could continue to generate with a -2+2 process either systematically wandering or systematically trawling new puzzles.
We can either try generate all the puzzles in each known grid - which potentially is doable.
Or we can generate on a particular common pattern - on the face of it it looks like having 12 clues might be easy [8 different clues 1-8 out of 12 [?495 ] - then add 4 clues
But it looks like any one pattern has 6^4 extra puzzle morphs to be tested - so I think that might effectively scupper that method.

[blue]

Hi Colin,

I suppose we await a reasonable estimation of the total number of 12C puzzles but can we really know how big the tail of the distribution is ?.

I don't know if you were referring to my comment in the other thread (or not ?).
I'll have a good estimate for the total number of grids with 12C puzzles, in ~3 hours.

Meanwhile, I'll add a few posts here, touching on some of the things discussed in recent posts here.
For a preview, I'm sure that Mladen was on the right track when he wrote this:

An easier ordering would be evaluation of bands followed by ordering by best-rated band (instead of lexicographically minimal band if the current canonicalization is based on it). This would place grids having the same top-rated band from within all 6 bands/stacks close to each other.