minimum number of clues per band/stack

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

Re: minimum number of clues per band/stack

Postby champagne » Fri Oct 17, 2014 12:33 am

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.
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby coloin » Fri Oct 17, 2014 7:36 pm

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
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: minimum number of clues per band/stack

Postby eleven » Sat Oct 18, 2014 7:58 pm

coloin wrote: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.
eleven
 
Posts: 1583
Joined: 10 February 2008

Re: minimum number of clues per band/stack

Postby Serg » Sat Oct 18, 2014 10:44 pm

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
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: minimum number of clues per band/stack

Postby JPF » Mon Oct 20, 2014 6:15 pm

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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Re: minimum number of clues per band/stack

Postby champagne » Mon Oct 20, 2014 7:29 pm

JPF wrote:
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
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby champagne » Tue Oct 21, 2014 8:41 am

JPF wrote: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
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby champagne » Wed Oct 22, 2014 10:00 am

withdrawn : big flaw in the code, we come later with fixed code
Last edited by champagne on Mon Oct 27, 2014 7:35 am, edited 2 times in total.
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby eleven » Wed Oct 22, 2014 6:22 pm

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.
Last edited by eleven on Thu Oct 23, 2014 12:33 pm, edited 2 times in total.
eleven
 
Posts: 1583
Joined: 10 February 2008

Re: minimum number of clues per band/stack

Postby Serg » Wed Oct 22, 2014 7:13 pm

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
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: minimum number of clues per band/stack

Postby champagne » Wed Oct 22, 2014 8:14 pm

withdrawn, no interest
Last edited by champagne on Mon Oct 27, 2014 7:36 am, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby coloin » Wed Oct 22, 2014 10:02 pm

Could you explain the
champagne wrote: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 ......
champagne wrote: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
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: minimum number of clues per band/stack

Postby JPF » Wed Oct 22, 2014 10:55 pm

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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Re: minimum number of clues per band/stack

Postby coloin » Thu Oct 23, 2014 12:11 am

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
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: minimum number of clues per band/stack

Postby champagne » Thu Oct 23, 2014 1:48 am

JPF wrote: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.
champagne
2017 Supporter
 
Posts: 5742
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to General