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 blue » Wed Nov 05, 2014 6:57 pm

coloin wrote:No. gsf is definitely saying that there are no min lex grids starting with those 15 bands.
All bands have around 100 M gridsolutions.
It looks like some gangsters will be a lot easier to search than others......
C

To expand on what Colin said, all 416 bands have around 100M solutions with minlex column 1, and around 72*100M, if the "column 1" condition is dropped.

The story behind the 15 bands, is that whenever a (complete/solution) grid contains a band or stack that is isomorphic to one of the 15, some other band or stack has a "smaller" minlex type.
blue
 
Posts: 573
Joined: 11 March 2013

Re: minimum number of clues per band/stack

Postby blue » Wed Nov 05, 2014 8:32 pm

champagne wrote:
blue wrote:For champagne,

To explain the "6^4" factor, You need to think about this: Suppose someone handed you a valid 3+4+27 puzzle. Suppose the 3+4 part didn't match one of the ED forms, and suppose the full band wasn't in any kind of canonical form. How could you show that your code would find the puzzzle, or one of its equivalents.


I like that start and here is my understanding.

We have a ED pattern corresponding to that valid puzzle (we generated all ED patterns). Morph the proposed puzzle to that ED pattern.

Take one box in the 27 clues band having the highest number of column occupied. Relabel rows 1 and 2 in that box to have 12345 in cells 1 to 5
if you are lucky, you can continue relabelling to have 123456789 in row 1, if it does not work, you have to exchange columns (and may be stacks 2 and 3) to come to the sequence 1234456789, the only one you have studied through the 401 minlex starts

It isn't always possible to do what you suggest, even if you allowed row permutations.
Example -- suppose box 1 (and its columns) must remain in place:
Code: Select all
1 2 3 | 4 8 6 | 7 5 9
4 5 6 | 9 7 2 | 8 3 1
7 8 9 | 3 1 5 | 2 6 4

Even if it was possible, it would not guarantee that the final result matched one of the 416 minlex types.
For most of the types -- 279 of them -- if you apply a random transformation to the "minlex" version, then there is only one way to restore it to its original form. This means that for most bands, you need to consider all 6^4 "stack & column" permutations, and thier effects on the 1871 ED "3+4" patterns.

Doing that, I come up with 842724 ED patterns.
That's after applying one of the 6^4 column permutations, and then permuting rows in the 3 and 4 clue bands, to give a maxlex result in each band.

That won't mean that you definitely need to test 416*842724 (or 44*842724) different "<filled band, 3/4 pattern>" combinations.
For bands that have automorphisms (in particular, automorphisms that involve a column permutation ... which almost all of them do), you can test a subset of the 842724 of the "3+4" patterns.

To make a "smallest possible" list, for a band type, you can do this:
1) Loop through the list of 842724 patterns.
2) If the pattern is marked as "tested", skip it ... otherwise:
3) Add it to a list of patterns to be tested for that band.
4) Mark it as tested, along with every pattern that can be produced by applying the column permutation from one of the band automorphisms, and permuting rows in the 3 & 4 clue bands to give maxlex results in those bands.

When I do that for minlex bands, I come up with 283,283,376 different combinations, for an average of 680,970 per band.
Using gangster classes, the result is smaller because of two things: 44 is smaller than 416, of course, but also the "gangster types" have more automorphisms than the "minlex" types.
The number I come up with, using gangsters, is 14,760,393 combinations, for an average of 335,463 patterns per gangster type.

You can go farther than that too. Many of the gangster types (17 of 44) -- have automorphisms that don't involve column swaps -- only relabeling. When testing one those against a particular 3+4 pattern, you can check each way of setting clues in the 7 cells, for whether it is minlex with respect the "relabeling only" automorphisms, and skip the solver test for the ones that aren't minlex.

You can go one step farther, looking at automorphisms for the filled band that involve column swaps that leave the 3+4 pattern unchanged (unchanged after row permutations to restore the maxlex form). They are very rare though, and in the end, reduce the number of puzzles to be tested by only ~0.015%.

Using the 14,760,393 <gangster type, 3/4 pattern> combinations, and the reduction by "relabeling only" automorphisms, I count 1,291,535,777,143 different puzzles to be tested. Without the "relabeling" reductions, it's 2,071,606,976,120. The enumeration took around 8 hours.

So the question is: How long to test ~1.3 * 10^12 puzzles ?
[ That's assuming I haven't made any mistakes in the counting. ]

On the other hand, maybe a 3+4+27 puzzle really does exist, and one would be found quickly.
For myself, I haven't had any luck producing one by "other means".
I also tried testing a random 1% of the 14,760,393 <gangster type, 3/4 pattern> combinations (~20 hours), and found nothing.
blue
 
Posts: 573
Joined: 11 March 2013

Re: minimum number of clues per band/stack

Postby dobrichev » Wed Nov 05, 2014 9:42 pm

Blue, do you have code that can produce stream of these 1.3e12 puzzles in about 8 hours?
If so, the solving, using 20 threads x 100 000 puzzles per second, gives one week of computaions, right? I can do this.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: minimum number of clues per band/stack

Postby coloin » Thu Nov 06, 2014 12:31 am

Well, I think that confirms the enormity of what would appear to be a simple task - but it does show that it can be done ! Excellent.
blue wrote:For myself, I haven't had any luck producing one by "other means".

well the only way i can think of doing it would be to generate - pseudorandomly 4+4+27 puzzles ..... and check for a superflous clue !
Ive not looked at the patterns of valid 4+4+27 puzzles ..... but any 3+4+27 would have to come from within .....
It would be astounding if a 3+4+27 did have a valid puzzle - but since no one has looked at the 12e11 possibilities.....

I did think that we could look at doubleganster bands ! [54 clues] Out of interest how many Ed of these are there ?
C
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: minimum number of clues per band/stack

Postby blue » Thu Nov 06, 2014 1:51 am

dobrichev wrote:Blue, do you have code that can produce stream of these 1.3e12 puzzles in about 8 hours?
If so, the solving, using 20 threads x 100 000 puzzles per second, gives one week of computaions, right? I can do this.

I sent you a PM.
blue
 
Posts: 573
Joined: 11 March 2013

Re: minimum number of clues per band/stack

Postby blue » Thu Nov 06, 2014 2:22 am

coloin wrote:
blue wrote:For myself, I haven't had any luck producing one by "other means".

well the only way i can think of doing it would be to generate - pseudorandomly 4+4+27 puzzles ..... and check for a superflous clue !
Ive not looked at the patterns of valid 4+4+27 puzzles ..... but any 3+4+27 would have to come from within .....

That was one of the things I tried. The 4+4+27's didn't come fast enough to get much testing done.
This was one of the nicer looking ones -- 4 empty houses !

Code: Select all
. . . | . . . | 5 3 .
1 7 . | . . . | . . .
. . . | . . . | . . .
------+-------+------
4 1 8 | 9 5 7 | 3 2 6
7 2 6 | 4 8 3 | 9 5 1
9 5 3 | 1 6 2 | 8 4 7
------+-------+------
. . . | . . . | . . .
. . . | . . . | . 1 9
. 6 5 | . . . | . . .


I did think that we could look at doubleganster bands ! [54 clues] Out of interest how many Ed of these are there ?

I can't say, but I'll try some code. Someone familiar with using that method to count the 6.67e+21 solution grids, might know.
How many valid 3 and 4-clue puzzles there are for each gangster class, would be good to know too.
That seems like a good idea too -- possibly better than the one that we've been considering.
blue
 
Posts: 573
Joined: 11 March 2013

Re: minimum number of clues per band/stack

Postby champagne » Thu Nov 06, 2014 6:32 am

Hi blue,

very rich post, opening doors for the future

blue wrote:
It isn't always possible to do what you suggest, even if you allowed row permutations.


Right, I think the stat was good till I reached row1 filed and the first mini row 456/7, but then applying only the 416 minlex band was wrong
But your count is better that what I would do following that idea, so I have to read carefully what you did.

blue wrote:

Using the 14,760,393 <gangster type, 3/4 pattern> combinations, and the reduction by "relabeling only" automorphisms, I count 1,291,535,777,143 different puzzles to be tested. Without the "relabeling" reductions, it's 2,071,606,976,120. The enumeration took around 8 hours.

So the question is: How long to test ~1.3 * 10^12 puzzles ?


Mladen already answered, but for a standard puzzle (likely faster with 27 given and non valid puzzles) we can expect a minimum of 100 000 puzzles per second using a good brute force existing process. So you come to something much better than what I started.

It seems you solved that old conjecture (answer in one week) Congratulations
champagne
2017 Supporter
 
Posts: 5737
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby champagne » Thu Nov 06, 2014 7:25 am

It seems that the conjecture is dead.
However, where we are, it would be interesting to have the full list of 3+4+27 puzzles


12345678945718962368927314524............79................1..........54......... ED=1.5/1.2/1.2
12345678945718962368927314524............79................1..........52......... ED=1.5/1.2/1.2
12345678945718962368927314524............73................1..........54......... ED=1.5/1.2/1.2
12345678945718962368927314524............73................1..........52......... ED=1.5/1.2/1.2
12345678945718962368927315424............79................1..........48......... ED=1.5/1.2/1.2
12345678945718962368927315424............79................1..........45......... ED=1.5/1.2/1.2
12345678945718962368927315424............73................1..........48......... ED=1.5/1.2/1.2
12345678945718962368927315424............73................1..........45......... ED=1.5/1.2/1.2
champagne
2017 Supporter
 
Posts: 5737
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby blue » Thu Nov 06, 2014 7:50 am

Very good :!:
Congratulations.

How did you do it ?
blue
 
Posts: 573
Joined: 11 March 2013

Re: minimum number of clues per band/stack

Postby champagne » Thu Nov 06, 2014 7:58 am

blue wrote:Very good :!:
Congratulations.

How did you do it ?


As I wrote earlier, I started a check of my ~ 66000 patterns made of the 1871 * columns permutations in stacks 2/3 against the 401 minlex bands of gsf's catalog;

I don't have the power that mladen can lock for a while, so it is a slow process.
This came this morning (likely during the night) in one of the 10 ongoing batches.

I am convinced that we have to learn from the exhaustive count, so this partial result should not stop what you are doing with mladen.
champagne
2017 Supporter
 
Posts: 5737
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby champagne » Thu Nov 06, 2014 4:47 pm

more in an ongoing run

12345678945718923669873251496...........7.8...............2...........91.........
12345678945718923669873251496...........7.8...............2...........61.........
12345678945718923669873251496...........7.3...............2...........91.........
12345678945718923669873251496...........7.3...............2...........61.........

EDIT these ones in a closed batch

12345678945718923669873251496..........8...7.................4.....95............
12345678945718923669873251496..........8...7.................4.....65............
12345678945718923669873251496..........3...7.................4.....95............
12345678945718923669873251496..........3...7.................4.....65............
champagne
2017 Supporter
 
Posts: 5737
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby JPF » Thu Nov 06, 2014 5:48 pm

Hi champagne,

interesting!

Up to now your patterns are isomorphic:
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

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

Re: minimum number of clues per band/stack

Postby champagne » Thu Nov 06, 2014 6:08 pm

JPF wrote:Hi champagne,

interesting!

Up to now your patterns are isomorphic:
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

JPF




That's a reason why I think that it would be anyway a good idea to make a full search using blue's "optimal" basis.

It could be also that some of these puzzles are morphs of the same one. My ~66000 pattern basis is not as well done as blue's basis.

Last but not least in the wider scope of that thread, it will be interesting to see whether the found puzzles can give new 17 clues.

So far we have no 17 clues puzzle with 3+4+10 and (if my memory is still good) only 9 patterns giving some 4+4+9 puzzles

PS: I split the 66000 patterns base in lots of 100 puzzles. The processing is a kind of sequential one.
champagne
2017 Supporter
 
Posts: 5737
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby coloin » Thu Nov 06, 2014 9:36 pm

coloin wrote: It would be astounding if a 3+4+27 did have a valid puzzle - but since no one has looked at the 12e11 possibilities.....C

I am astounded !
To be fair its a lot harder to find something if you think its not actually there .... and now in retrospect looking for {3+5+27} puzzles might have been a more productive way to find a {3+4+27}.
However, well done for persevering - in some respects it would have been a bit flat if blue/dobrichev had done that big search - only to conclude that they didn't exist - and now that you have found several, the puzzles do look very empty !!!.
C
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: minimum number of clues per band/stack

Postby coloin » Thu Nov 06, 2014 10:16 pm

And there are at least a good few more of that pattern ........101 off my first run using those as seeds .....C
Edit - which is to be expected as there will be one puzzle for each of the different 416 bands of the particular gangster. ....
C
coloin
 
Posts: 1638
Joined: 05 May 2005

PreviousNext

Return to General