The New Sudoku Players' Forum

[champagne]

thanks to all of you for that quick summary of what is known in that field.

to Serg, a small typo in your text, you are using if I am right a minlex form of the pattern (I prefer for specific reasons to work on the maxlex).

May be now some comments on why I raised the question.

The recent post of mladen here shows a disappointing result on the power needed for a {-3 +3} vicinity search.

On another side, we have already seen that the theoretical enumeration of 17 clues patterns is highly overestimated in that thread here
17 clues 55 113 078 988 patterns

At the end I am wondering what can be the true order of magnitude knowing that the following conditions are not accounted in that count

- a 17/18 clues pattern has many "symmetries" reducing the count
- a valid 17 clues pattern has a minimum of 3 clues per band/stack
- a valid 17 clue pattern can not have 2 empty units in a band/stack

and may be other limitations I did not catch. (analysis of known 17 clues would suggest only one band/stack with 3 clues ??? )

Coloin gave a possible 77 millions puzzles, that would still be much to high but shows than counting such patterns could help.

[coloin]

I very much doubt if there are 7 more !
The 77 million comes from Serg and apparently is the number of patterns with box distribution of

Code: Select all

1 2 2
2 2 2
2 2 2

I think blue generated many of the 18s with box,row and column counts all with

Code: Select all

2 2 2
2 2 2
2 2 2

but I am not sure how complete it would have been.......but they are very uncommon - I think there only 2 non-minimal puzzles [17s] ?

Anyway if the object is to try to generate all possible 17-puzzles...........

The puzzles with either a full central box or a full row - plus 13 clues isn't closed unfortunately at {-1+1} for the 13 clues
It would have been within my grasp to collate all these puzzles ... million or so with the box and similar with the row - and I have probably 95% of them ......

Unfortunately even the 9plus14s arent closed with a {-1+1} with the 14 clues .......

C

[eleven]

Anyway if the object is to try to generate all possible 17-puzzles.

In that case it would be interesting to know, if now a 16 clue pattern search could be feasible.

[Serg]

Hi, all!
Yes, I calculated 2 years ago the number of essentially different patterns, having map

Code: Select all

1 2 2
2 2 2
2 2 2

Precise number of such (17-clue) patterns - 76,590,743 (see thread Number of non equivalent patterns having N clues).

I think to be able of doing exhaustive search through such subset of 17-clue patterns, we should be able to decrease 2 or 3 times (at least) number of possible crossings, i.e. patterns belonging to maps

Code: Select all

  A         B         C

1 2 2     2 2 1     2 2 2
2 9 9     2 9 9     2 9 9
2 9 9     2 9 9     2 9 9

I've just calculated the number of essentially different patterns for maps A and C.
Map A has 378 essentially different patterns.
Map C has 1278 essentially different patterns.

Not so many maximal patterns from 40-patterns list can be used to filter out invalid patterns in this case. According to my estimate, the number of essentially different patterns for map A can be decreased by several tens only. Filtering for map C is even less effective. So, it seems to be impossible to decrease, say, by 1000 times number of patterns to be examined for map

Code: Select all

1 2 2
2 2 2
2 2 2

Therefore I don't see real way to do exhaustive search through such kind of 17-clue patterns at the moment.

Serg

[JPF]

55113078988 is the exact number of essentially different (ed) 17 clue-patterns.
essentially different means that for any distinct patterns P1 and P2 of this Set, it doesn't exist any symmetry f such that f(P1) = P2.

These patterns are valid or not valid; probably most of them are not valid(i.e. they don't contain any valid puzzle)

Let N = 5.51 x 10^10 be an approximation of 55113078988.
N is a huge number. It seems out of the current technology to test each pattern for finding valid puzzles.

Can we narrow down the search by adding some obvious requirements?
For example:
How many ed 17 clue patterns having at least 3 clues per band and per stack are there in this Set?

To answer this question, I used a Monte Carlo algorithm.
answer : 4.27 x 10^10 ; still a lot!

How many ed 17 clue patterns without 2 empty units in each band and stack?
answer : 4.18 x 10^10

For both of the two previous requirements:
answer : 3.72 x 10^10

Methodology:
Let E be a set of patterns: here the set of all the 17 clue patterns with Card(E) = C(81,17) = 1.2845 x 10^17 elements.
Let F be a condition (a subset of E)
Generate randomly n patterns of E with equal probability.
If the pattern P satisfies the condition F, calculate its number of automorphisms.
After n patterns :
p is the proportion of patterns satisfying F: i.e. out of n patterns, there are p.n patterns included in F
a is the average of their (satisfying F) number of automorphisms

then, an estimation of Card(F) is Card(F) = p.Card(E)
and the number of ed patterns of F is p.a.Card(E)/(2*6^8) = p.a x 3.8237 x 10^10


Conditions:
The random generator has to be unbiaised! (I am not confident in mine)
n has to be large enough to get a correct precision.

I tested this algorithm successfully on the following estimations, where the exact figures are known:

number of ed 17 clues-patterns
number of ed patterns of:
1 2 2
2 2 2
2 2 2

and

2 2 2
2 2 2
2 2 2

JPF

[champagne]

I tested this algorithm successfully on the following estimations, where the exact figures are known:

number of ed 17 clues-patterns
number of ed patterns of:
1 2 2
2 2 2
2 2 2

and

2 2 2
2 2 2
2 2 2

JPF

Hi JPF,

Just a comment on these 2 patterns.

The second one is a 18 clues pattern

if the max lexical start for row 1 is
1.. 1.. ...
the count is 72

is it something your monte carlo process checks?

for the first one (17 clues), if again row 1 max lexical is
1.. 1.. ...

The count I find is 1155

Again is it the order of magnitude you have?


I am still working on preparing a code to count, but as I am aging and having other activities, it is a slow process,

One interesting partial result with the start (max lexical for row1)

11. ... ...

Despite severe filters I have at generation time, I produced plenty of patterns. (about 100 millions patterns in the sample)
Checking with a reliable canonical process, I am left with only 2% of the original puzzles,

Just to have an idea of the filters used at generation time, I generate only 73 patterns for a final count of 72 with the start 1.. 1.. ...

I am preparing a fast canonical process working specifically on patterns before restarting the generation process. I hope to have some results in the near future.

[champagne]

Methodology:
Let E be a set of patterns: here the set of all the 17 clue patterns with Card(E) = C(81,17) = 1.2845 x 10^17 elements.
Let F be a condition (a subset of E)
Generate randomly n patterns of E with equal probability.
If the pattern P satisfies the condition F, calculate its number of automorphisms.
After n patterns :
p is the proportion of patterns satisfying F: i.e. out of n patterns, there are p.n patterns included in F
a is the average of their (satisfying F) number of automorphisms

then, an estimation of Card(F) is Card(F) = p.Card(E)
and the number of ed patterns of F is p.a.Card(E)/(2*6^8) = p.a x 3.8237 x 10^10


Conditions:

JPF

it seems to me that we have another definition of the ratio "n clues patterns to check" to "enumeration of n clues patterns"

1) generate randomly a pattern with n clues (not so easy, I agree)
2) check for specific conditions as {not 2 empty rows columns} ...
3) if 2) is ok, check if the pattern is canonical and keep it only if it is

This gives an estimate of the expected ratio
number of patterns passing 2 and 3 / number of generated patterns

and then you are sure to have considered all possibilities of "symmetries"

[champagne]

withdrawn : big flaw in the code, we come later with fixed code

[eleven]

Wow, so each 6th pattern with a line, where all 3 clues are in a box, has a 17. Surprising indeed.

[Edit:]Removed obsolete question.

[Serg]

Hi, champagne!
Surprising results! You decreased number of potentially valid 17-clue patterns by 5000 times just applying 2 simple filters.
You didn't consider patterns containing more than 6 clues in the first row. Why?

Serg

[champagne]

withdrawn, no interest

[coloin]

Could you explain the

The second column is the octal corresponding value if the pattern is located in a 16 bit field with the highest bi corresponding to the left position.

please .....

However good to see some progress - I have long been a fan of the max lex pattern to keep the clues together ......

What about " not more than one band/stack with 3 clues"

well it is proven that a "crossing" stack/band cant have valid puzzles if there is 3 in each
all these have been shown by Serg to be invalid

Code: Select all

111   012   210   300
199   199   199   099
199   299   099   099    are all invalid clue counts - and this could probably be taken a bit farthur

however

Code: Select all

211    310    211
199    199    199
199    099    099    can give valid puzzles

it is not proven that a band count of

Code: Select all

3
3
27

is invalid.....
however no puzzle has ever been found with

Code: Select all

3
4
27

I also think [for now] you can exclude any pattern with 6 clues in a row/column or box - and i would go as far to suggest not to bother with 5 in any row/column or box !!!!!!!!

C

[JPF]

champagne,

In order to check that your algorithm works properly, you should first use it without any filter and show that you get a fair estimate of the exact number of patterns i.e. 5.51 x 10^10

JPF

[coloin]

Its definitely a nice result for the 640 octal ..... i get it now ......
However arnt the reductions going to be less for the other octals ? ...........
Unless you ignore all the patterns with the max 5 clues in a row ..... this would get rid of octals 770,760,744,666 and 664.
The reason i say this is that here are "almost" all the 113 horizontal 9plus12 puzzles from a little background game i did here.
From that, one can easily remove clues to provide all 28 of the horizontal 5plus12 puzzles.
I was rather hoping it would prove useful one day !
The only difficulty might be proving that there isnt one or two hanging around - but that may well be easier than searching patterns with 5 or more clues in the row.
C

[champagne]

champagne,

In order to check that your algorithm works properly, you should first use it without any filter and show that you get a fair estimate of the exact number of patterns i.e. 5.51 x 10^10

JPF

yes,
but the canonical algorithm mixes classical morphs and other "symmetries", so, at the end, it's not so easy.