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 24, 2014 2:28 pm

JPF
champagne wrote:This should come from my cannibalization process
Are you speaking about your shrimps ? :roll:[/quote]

Hi JPF,

Thanks for the remark (I edited the post)

I have also to apologize for my scepticism, but in the past, in that field of statistics where I have only basic knowledge, I got from a (french) specialist an erroneous conclusion regarding the frequency of the exocet pattern in high Sudoku Explainer ratings.

Where experience shows more than 80%, he announced less than 1% based on a statistical approach (monte carlo).
champagne
2017 Supporter
 
Posts: 5612
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby champagne » Fri Oct 24, 2014 2:43 pm

blue wrote:
blue wrote:As promised, here are results from two concurrent runs with the same sample size.


Code: Select all
Monte Carlo sample size: 551452672 random 17-clue patterns

+-------------------------+-------------------------------------------------------+
|        raw results      |               results with filtering                  |
+-----------+-------------+-------------+-------------+-------------+-------------+
| maxlex r1 | ED patterns |    3+/chute | w/o 2 empty |        both |   Serg's 40 |
+-----------+-------------+-------------+-------------+-------------+-------------+
+-----------+-------------+-------------+-------------+-------------+-------------+
|    totals | 55112429330 | 42761132568 | 41766393546 | 37125633998 | 17856388325 |
+-----------+-------------+-------------+-------------+-------------+-------------+




Hi blue,

Again, if you want to study a point, ask first to blue, even if it's not published, he has the answer in his cache :roll:

One interesting point here is the fact that the magic 40 divide by 3 the count.
As the "2 empty rows" is part of the 40 set, only the 3/chute can add eliminations for 17 clues and less.

One question as I see you have cross checked all serg's findings.

What has been the process to prove that each of these 40 patterns can not produce puzzles (I know that at least one is trivial).
Is it just reasoning or any other method.
champagne
2017 Supporter
 
Posts: 5612
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby Serg » Fri Oct 24, 2014 3:19 pm

Hi!
JPF and blue have done great work! It's good idea to use Monte Carlo method to estimate potential of various elimination techniques. Frankly speaking, your results are very close to my expectation of considered filters' power.

blue, you wrote in your first post with Monte Carlo simulation results:
blue wrote:The last column, is ED patterns with 3+ clues per chute, that pass filtering by Serg's 40 patterns.
Note: The total at the bottom, is only 2% lower than in the column for filtering by Serg's patterns alone.

But both numbers must be exactly the same. 40-patterns filtering has "3+/chute" and "w/o 2 empty" filters as subsets, because the first filter was derived from 40-patterns list and the second filter is provided by pattern P137 from 40-patterns list.
Code: Select all
        P137
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+

If really there are some patterns which cannot be filtered out by 40-patterns list, but can be filtered out by "3+ clues per chute" filter, it implies coloin's proof of the statement "any valid 17-clue puzzle must have more than 2 clues in a band (stack)" was wrong. Have you any counterexamples to disprove that proof?

Serg
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: minimum number of clues per band/stack

Postby coloin » Fri Oct 24, 2014 3:44 pm

Thanks for that blue

If its any help to filter more .....
The not having 7 clues in 2 bands filter is confusing .....
as
Code: Select all
211
199
099 has valid puzzles


but the un proven band count 3,4,27 probably doesnt have valid puzzles, [4,4,27 has valid puzzles]

here is part of the table of no of patterns with n clues in n boxes

Code: Select all
         B1B2B3B4B5B6 
   
7 clues      12168     


Many of those patterns will have 1,6,27 and 2,5,27 and can be excluded [ as 2,8,27 is necessary]
How feasible is it to search those patterns with a given representative of the 44 gangster ways to populate the 27 clues in the third full band. ?
coloin
 
Posts: 1629
Joined: 05 May 2005

Re: minimum number of clues per band/stack

Postby blue » Fri Oct 24, 2014 6:32 pm

Serg wrote:blue, you wrote in your first post with Monte Carlo simulation results:
blue wrote:The last column, is ED patterns with 3+ clues per chute, that pass filtering by Serg's 40 patterns.
Note: The total at the bottom, is only 2% lower than in the column for filtering by Serg's patterns alone.

But both numbers must be exactly the same. 40-patterns filtering has "3+/chute" and "w/o 2 empty" filters as subsets, because the first filter was derived from 40-patterns list and the second filter is provided by pattern P137 from 40-patterns list.
Code: Select all
        P137
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+

If really there are some patterns which cannot be filtered out by 40-patterns list, but can be filtered out by "3+ clues per chute" filter, it implies coloin's proof of the statement "any valid 17-clue puzzle must have more than 2 clues in a band (stack)" was wrong. Have you any counterexamples to disprove that proof?

Hi Serg,

Yes, I realized that, some hours after making the first post.
it was my mistake -- a stupid bug in the code -- a copy/paste/edit error.
See the "Added: [ text in blue ]" comment in the first post (and the later post with 2 tables, if you like).
blue
 
Posts: 573
Joined: 11 March 2013

Re: minimum number of clues per band/stack

Postby blue » Fri Oct 24, 2014 8:37 pm

champagne wrote:One question as I see you have cross checked all serg's findings.

What has been the process to prove that each of these 40 patterns can not produce puzzles (I know that at least one is trivial).
Is it just reasoning or any other method.

We both used a clever idea that Red Ed had mentioned years ago.
He used it to show that this pattern (I think) has no puzzles:

Code: Select all
+-------+-------+-------+
| x x x | x x x | x x x |
| x x x | . . . | x x x |
| x x x | . . . | x x x |
+-------+-------+-------+
| x . . | . . . | . . x |
| x . . | . . . | . . x |
| x . . | . . . | . . x |
+-------+-------+-------+
| x x x | . . . | x x x |
| x x x | . . . | x x x |
| x x x | x x x | x x x |
+-------+-------+-------+

It's a neat idea, but unfortunately it's only practical for patterns with many automorphisms, and a relatively small number of empty cells.

The idea is to show that every "essentially distinct" way of filling the empty cells, either
A) cannot be extended to a complete grid, or
B) contains an unavoidable set.

In the code, the genral idea is enumerate the ED fills for empty cells, and for each one:
1) Treat it as a puzzle, and use a brute force solver, to try to find one solution -- if none exists, condition A is satisfied.
2) If a solution is found, clear the cells that should be empty in the pattern; treat that as a 2nd puzzle; and use the brute force solver to try to find two solutions. If two solutions exist, then condition (B) is satisfied (and vica-versa). If one solution exists, it's a counterexample to the proposition that the pattern has no valid puzzles.

To see that the method is valid, suppose the pattern had a valid puzzle. Then its solution could be transformed to make the values in the empty cells, match one of the ED empty cell fills -- one that would: A') have an extension to a complete grid, and B') not contain an unavoidable set.

I don't know the details of how Serg did his testing.
For me, I had special code for each pattern.
It almost always broke the empty cell pattern into 2 overlapping parts, and produced short lists of fills satisfying (A) and (B) above. [ That was a poor wording: lists where each has an extension to a complete grid, and none contains an unavoidable set ]. Then it then combined fills from each list, them to produce fills for the full empty cell pattern. For some patterns, it was necessary to apply a small set of transformations to the fills from one of the lists, before combining with the fills from the other list. For some patterns, the code finished in seconds, and for others, it took minutes or hours.

As for how to come up with a list of patterns to test, that's another long story.

Also added: About the last paragraph above ... in more detail, the two parts of the empty cell pattern, overlapped in box 1. "Essentially distinct" was also too general. More correct, is essentially distinct with respect to transformations that leave box 1 in its place. Also, for me, the 2nd list was often longer than necessary, depending on how much work I was willing to do in tranforming fills from the first list, before combining them with fills from the 2nd list. For anyone comtemplating trying this, the bit about combining patterns from two lists of "(mostly) essentially distinct" fills, can be very tricky. You need to think carefully, to make sure that in testing the combinations, you are guaranteed to hit a morph of each ED "combined" pattern, at least once -- twice is OK, but you need to ensure that nothing would be missed. Reducing one of the lists by too many "equivalence transformations", can be fatal.
Last edited by blue on Fri Oct 24, 2014 11:26 pm, edited 1 time in total.
blue
 
Posts: 573
Joined: 11 March 2013

Re: minimum number of clues per band/stack

Postby JPF » Fri Oct 24, 2014 9:57 pm

blue wrote:We both used a clever idea that Red Ed had mentioned years ago.
He used it to show that this pattern (I think) has no puzzles:

Code: Select all
+-------+-------+-------+
| x x x | x x x | x x x |
| x x x | . . . | x x x |
| x x x | . . . | x x x |
+-------+-------+-------+
| x . . | . . . | . . x |
| x . . | . . . | . . x |
| x . . | . . . | . . x |
+-------+-------+-------+
| x x x | . . . | x x x |
| x x x | . . . | x x x |
| x x x | x x x | x x x |
+-------+-------+-------+

actually, he (Red Ed) proved that this maximal pattern is not valid:
Code: Select all
+-------+-------+-------+
| x x x | x x x | x x x |
| x x x | . . . | x x x |
| x x x | . . . | x x x |
+-------+-------+-------+
| x . . | . . . | . . x |
| x . . | . x . | . . x |
| x . . | . . . | . . x |
+-------+-------+-------+
| x x x | . . . | x x x |
| x x x | . . . | x x x |
| x x x | x x x | x x x |
+-------+-------+-------+

see here the beginning of the discussion.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Re: minimum number of clues per band/stack

Postby champagne » Sat Oct 25, 2014 6:09 am

thanks to blue and jpf for that quick summary of the method applied to prove the magic 40.
champagne
2017 Supporter
 
Posts: 5612
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby champagne » Mon Oct 27, 2014 2:43 pm

coloin wrote:
How feasible is it to search those patterns with a given representative of the 44 gangster ways to populate the 27 clues in the third full band. ?


can you clarify " 44 gangster ways to populate the 27 clues"
I have in mind 416 permutations for the 27 clues (401 with valid puzzles)
champagne
2017 Supporter
 
Posts: 5612
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby coloin » Mon Oct 27, 2014 7:50 pm

Well ...... I was thinking the object was [somehow] to prove that a {3,4,27} doesnt exist ...
Taking an example of a {4,4,27}
Code: Select all
...9.....3....1.........8...5......1....8...........4.231457689497368215865129374

we can get two others, closely related with the same 27 clue band
Code: Select all
...9.....3....1.........8....9.....7....8...........4.231457689497368215865129374     
3...........9.1.........8....9.....7....8...........4.231457689497368215865129374

fixing band one and two
Code: Select all
584936127329871456716542893658294731143785962972613548...........................

gives 168 solutions,of which 28 are different, / ways to complete a puzzle
I believe they are all the same "gangster" as they have the same vertical tuple of 3 clues
Code: Select all
...9.....3....1.........8...5......1....8...........4.231457689497368215865129374     
...9.....3....1.........8...5......1....8...........4.231458679467129385895367214           
...9.....3....1.........8...5......1....8...........4.237159684491368275865427319           
...9.....3....1.........8...5......1....8...........4.237458619491367285865129374           
...9.....3....1.........8...5......1....8...........4.261457389497328615835169274           
...9.....3....1.........8...5......1....8...........4.261457389497368215835129674           
...9.....3....1.........8...5......1....8...........4.261458379437129685895367214           
...9.....3....1.........8...5......1....8...........4.261458379437169285895327614           
...9.....3....1.........8...5......1....8...........4.267159384491328675835467219           
...9.....3....1.........8...5......1....8...........4.267159384491368275835427619           
...9.....3....1.........8...5......1....8...........4.267458319491327685835169274           
...9.....3....1.........8...5......1....8...........4.267458319491367285835129674           
...9.....3....1.........8...5......1....8...........4.291357684435168279867429315           
...9.....3....1.........8...5......1....8...........4.291357684465128379837469215           
...9.....3....1.........8...5......1....8...........4.291358674435167289867429315           
...9.....3....1.........8...5......1....8...........4.291358674437169285865427319           
...9.....3....1.........8...5......1....8...........4.291358674465127389837469215           
...9.....3....1.........8...5......1....8...........4.291358674467129385835467219           
...9.....3....1.........8...5......1....8...........4.291467385435128679867359214           
...9.....3....1.........8...5......1....8...........4.291467385467358219835129674           
...9.....3....1.........8...5......1....8...........4.291468375435127689867359214           
...9.....3....1.........8...5......1....8...........4.295167384461358279837429615           
...9.....3....1.........8...5......1....8...........4.295167384467358219831429675           
...9.....3....1.........8...5......1....8...........4.295168374461357289837429615           
...9.....3....1.........8...5......1....8...........4.297358614435167289861429375           
...9.....3....1.........8...5......1....8...........4.297358614465127389831469275           
...9.....3....1.........8...5......1....8...........4.297468315435127689861359274           
...9.....3....1.........8...5......1....8...........4.297468315461357289835129674

The 2 other {4,4,x} can be made into a valid puzzle with each of the 28 {27-clue bands}

I dont know how many {4,4,27} there are but surely it is finite. [!]
It may even be easier to search for 4,4,27 { exhaustively} than {3,4,27}
But there are reductions of 44 from 416, I think.
These are the three band-pairs from above which can be solved with 4+4 clues - not sure how many there are likely to be......
Code: Select all
                                                                                       
...9.....3....1.........8...5......1....8...........4.231457689497368215865129374           
584936127329871456716542893658294731143785962972613548...........................           
                                                                                             
...9.....3....1.........8....9.....7....8...........4.231457689497368215865129374           
728936451356841792914572863689214537143785926572693148...........................           
                                                                                             
3...........9.1.........8....9.....7....8...........4.231457689497368215865129374           
356842791728931456914576823689214537143785962572693148...........................

C
coloin
 
Posts: 1629
Joined: 05 May 2005

Re: minimum number of clues per band/stack

Postby coloin » Thu Oct 30, 2014 12:15 am

coloin wrote:Well ...... I was thinking the object was [somehow] to prove that a {3,4,27} doesnt exist ...

well its not quite as simple, even adding 6 clues [ and there are reductions if we say one per box] to a single 27 clue band.
The number of patterns may well be small [74 ED with 6 clues in 6 boxes, B1B2B3B4B5B6, no empty box] ..... add one clue is quick though
Its still too much
C
coloin
 
Posts: 1629
Joined: 05 May 2005

Re: minimum number of clues per band/stack

Postby champagne » Thu Oct 30, 2014 6:48 am

I tried to create all ED patterns 3 4 27 with a variant of the code used to create the 17 clues patterns.

I find 1202 ED patterns. A small part of these patterns will disappear using the magic 40 filters.
These means that the check would be IMO to see if any valid puzzles can be produced out of the 401 "27 clues" starts identified by gsf as having valid puzzles

401 x 1202 is something that can be studied.
with the first band filled, we can expect something as 150 k hints to test for each pattern and the brute force with 34 known clues is very fast.
champagne
2017 Supporter
 
Posts: 5612
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby dobrichev » Thu Oct 30, 2014 8:02 am

IMO you have to iterate the values of the 7 cells in the each ED pattern over the 44 x 6^4 = 539136 base 27-clue bands.
For individual pattern the 539136 factor can be reduced by examining the pattern automorphisms. (Assuming the band 3 has 27 givens, the symmetry over stack and column permutations does the reduction. The rest symmetries are already accounted during the pattern canonicalization).
Edit: As noted by others, 416 = the number of ED bands is changed to 44 = the number of gansters not taking into account the possible permutations of the values in the vertical triplets.
Last edited by dobrichev on Sat Nov 01, 2014 3:14 am, edited 1 time in total.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: minimum number of clues per band/stack

Postby champagne » Thu Oct 30, 2014 1:24 pm

dobrichev wrote:IMO you have to iterate the values of the 7 cells in the each ED pattern over the 416 x 6^4 = 539136 base 27-clue bands.
For individual pattern the 539136 factor can be reduced by examining the pattern automorphisms. (Assuming the band 3 has 27 givens, the symmetry over stack and column permutations does the reduction. The rest symmetries are already accounted during the pattern canonicalization).

Hi mladen,

we for sure in that exercise assume that we have 27 given if the "base band".

Adding 7 cells in the 2 other bands with at most one empty row per band does not give so many ED patterns. We have still the full potential for stack symmetries.

If my code is ok, this leads to 1202 ED patterns.

At that point , I don't see more than the 401 gsf permutations as starts in the base band. I can't explain your 6 ^4 additional factor. But I accept that I could be wrong.

My 150k hints comes from the following quick calculation :

6 potential digits for the 4 clues in one band
5 potential digits in average for the 3 more digits in the last band

162 000 hints rounded to 150 000

EDIT : my count of ED pattern missed the case 1+1+1 in the band having 3 clues
champagne
2017 Supporter
 
Posts: 5612
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby JPF » Thu Oct 30, 2014 5:27 pm

champagne,

I get 6099 {3,4,27} ed patterns and only 4919 without 2 empty rows in the same band.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

PreviousNext

Return to General