The New Sudoku Players' Forum

[Serg]

Hi, blue!

Great work again !

Thanks!

You finished the "0 empty boxes" case, very quickly !

"0 empty boxes" case took my program about 20 hours of CPU to analyze about 1.5 millions of patterns (9-year old notebook with "Intel Pentium-4m" processor). Final verification of 40-patterns list took me about 4 hours of CPU time (in this case I didn't use any apriori information about patterns having or not having valid puzzles).

I have the same list, for "maximal patterns".
...
Since we used completely different code, I think our final results must be correct.

I checked (by eye) all patterns in your list. It is rather surprising for me, but our lists are exactly the same (up to isomorphisms). I think this is reliable confirmation of our results correctness.

Serg

[coloin]

Thinking about all these patterns which have been proved not to have puzzles.

I removed a clue from a random 17 clue valid puzzle - I found that i could fit the subpuzzle into one of the patterns without puzzles... Although it didnt work for all clues .......

From here with 16 clues there are 15578997961 e-d patterns .

Code: Select all

 0   1
 1   1
 2   5
 3   21
 4   109
 5   548
 6   3074
 7   16847
 8   92393
 9   489448
 10  2499689
 11  12199113
 12  56737622
 13  250632745
 14  1049547176
 15  4159131734
 16  15578997961
 17  55113078988

There will be a level of n where all the patterns can be derived from all our patterns-without-puzzles ?

At least 9 - but not 16 i suspect ......?

C

[coloin]

Thinking about it a bit more ...............

Probably wiser to take a random selection of a few hundred templates with n clues and somehow determine the proportion completly within at least one of our [many] patterns-without-puzzles.....

I might try this with 11 clue templates plus one full box / 11 clue templates plus one full row.

C

[Serg]

Hi, coloin!

I removed a clue from a random 17 clue valid puzzle - I found that i could fit the subpuzzle into one of the patterns without puzzles... Although it didnt work for all clues .......

What did you do? Did you randomly selected a 17-clue puzzle from the list of known ones and then randomly selected 1 clue to remove?

There will be a level of n where all the patterns can be derived from all our patterns-without-puzzles ?
At least 9 - but not 16 i suspect ......?

I can state that the list of maximal patterns, containing 4 entire filled corner boxes (published above 40-patterns list) is sufficient to prove non-existence 11-clue valid puzzles (see thread How to prove non-existence of 8-clue valid puzzles?). All "Composition rules" from that thread (see 7-rules list), being sufficient to prove non-existence 11-clue valid puzzles, are subsets of the patterns from 40-patterns list. It's not so evident, but possible configuration of empty boxes in a valid puzzles is entire determined by 40-patterns list too.

Serg

[Serg]

Hi, coloin!

Probably wiser to take a random selection of a few hundred templates with n clues and somehow determine the proportion completly within at least one of our [many] patterns-without-puzzles.....

I might try this with 11 clue templates plus one full box / 11 clue templates plus one full row.

I think it's not so much sense in experimental determining efficiency of filtering out patterns by new found maximal patterns.
1. Such efficiency (to my mind) severe depends on patterns class (for example, 17-clue patterns and vertically symmetric 18-clue patterns can have quite different filtering efficiency).
2. It is quite real to do direct check - generate all possible patterns of some kind and then filter out patterns not having valid puzzles. At least, I am planning to do it for vertically symmetric 18-clue patterns. Maybe, in future, I could do it for 9plus12 or 9plus11 patterns classes.

Serg

[coloin]

hi serg, yes its debatable how effective it is going to be.
i'm thinking [rather optimistically] that if we are able to exclude 95 % of all patterns at a particular clue count - it will still leave us a rather large number of potentially valid templates.

Its good that your work has excluded all 11-clue templates.
Playing around with a 12 like this

Code: Select all

+---+---+---+
|1..|...|...|
|.2.|...|.4.|
|...|.3.|...|
+---+---+---+
|...|...|..8|
|..5|...|...|
|...|.67|...|
+---+---+---+
|7..|...|...|
|...|4..|1..|
|...|...|.9.|
+---+---+---+

- i got the impression that it might get passed by all the patterns we have up to now.....
certainly not having an empty box and no more than 2 clues to a row or box makes it difficult.

As an aside

Looking at the majority of valid puzzles [with many exceptions though]
they tend to have one or more

Code: Select all

             
+---+---+---+       
|x..|...|...|       
|...|x..|...|       
|...|...|x..|       
+---+---+---+       
|.x.|...|...|       
|...|.x.|...|       
|...|...|...|       
+---+---+---+       
|..x|...|...|       
|...|..x|...|       
|...|...|...|       
+---+---+---+ 7 positions

in their template

if they dont have 8 or 9 positions,
7 can usually be found [2 types] [one shown]
6 must be the minimum - e.g in puzzles with 3 empty boxes and some of the puzzles in the collection of box-9plus12s.
EDIT
5 is the minimum - pattens with 4 empty boxes have puzzles .....

This might be a factor if we were to start looking at subpuzzle templates .......

C

[coloin]

This might be a factor if we were to start looking at subpuzzle templates .......

for 12 clue templates
9-pattern plus any 3 [ note symmetry reduction]
8-pattern plus any 4 [but no 9-patterns][with or without one empty box]
7-pattern[s] plus any 5 [but no 8-patterns] [ increasing numbers of clue restrictions][with 0,1,2 empty boxes]
6-pattern[s] plus any 6 [but no 7-patterns ] [massive clue restrictions] [with 0,1,2,3 empty boxes]
5-patterns[s] - ? ignore

i think min clues for 3 empty boxes is ? 18 or more
I think min clues for 4 empty boxes is ? 19 or more

C

[Serg]

Hi, coloin!

Playing around with a 12 like this

Code: Select all

+---+---+---+
|1..|...|...|
|.2.|...|.4.|
|...|.3.|...|
+---+---+---+
|...|...|..8|
|..5|...|...|
|...|.67|...|
+---+---+---+
|7..|...|...|
|...|4..|1..|
|...|...|.9.|
+---+---+---+

- i got the impression that it might get passed by all the patterns we have up to now.....

Nice example! I checked all its 9 crossing (by eye) and found that you are right - no maximal pattern from 40-patterns list contains this pattern as subset. So, 40-patterns list is sufficient to prove non-existence of 11-clue valid puzzles, but isn't sufficient to prove non-existence of 12-clue valid puzzles.

Looking at the majority of valid puzzles [with many exceptions though]
they tend to have one or more

Code: Select all

             
+---+---+---+       
|x..|...|...|       
|...|x..|...|       
|...|...|x..|       
+---+---+---+       
|.x.|...|...|       
|...|.x.|...|       
|...|...|...|       
+---+---+---+       
|..x|...|...|       
|...|..x|...|       
|...|...|...|       
+---+---+---+ 7 positions

in their template

if they dont have 8 or 9 positions,
7 can usually be found [2 types] [one shown]
6 must be the minimum - e.g in puzzles with 3 empty boxes and some of the puzzles in the collection of box-9plus12s.
EDIT
5 is the minimum - pattens with 4 empty boxes have puzzles .....

This might be a factor if we were to start looking at subpuzzle templates .......

Do you mean patterns having valid puzzles usually contains such patterns as subsets?

Serg

[Serg]

Hi, coloin!

for 12 clue templates
9-pattern plus any 3 [ note symmetry reduction]
8-pattern plus any 4 [but no 9-patterns][with or without one empty box]
7-pattern[s] plus any 5 [but no 8-patterns] [ increasing numbers of clue restrictions][with 0,1,2 empty boxes]
6-pattern[s] plus any 6 [but no 7-patterns ] [massive clue restrictions] [with 0,1,2,3 empty boxes]
5-patterns[s] - ? ignore

It is possible to start proving 12-clue valid puzzles impossibility (for example, by method described in the cited thread How to prove non-existence of 8-clue valid puzzles?), but I have no time to do it right now. This task is rather difficult and needs universal utility to check given patterns for having valid puzzles (I still have no such tool).

i think min clues for 3 empty boxes is ? 18 or more
I think min clues for 4 empty boxes is ? 19 or more

Maybe you are right, but how to prove it? (I cannot see the way to do it yet.)

Serg

[coloin]

Indeed..... it would be even a little easier to put 12 clues in 8 boxes which would defeat the 40 patterns without puzzles

Do you mean patterns having valid puzzles usually contains such patterns as subsets?
Serg

Yes !
Around over 50% of 17-puzzles have a pattern of 7 [actually with all differnt clues]
I imagine most puzzles will be 8 - even more so with increasing clues. [An empty row or box precludes a 9]
Its of academic interest as i dont think we will be generating 16 or 17 clue templates just yet !
As you say we havnt a tool for testing it.

Miladens program finds minumum size puzzles from reduced grid solutions.

The best i could do with 4 empty boxes was 21 clues

Code: Select all

+---+---+---+
|35.|...|...|
|...|8.7|...|
|.92|..6|...|
+---+---+---+
|.1.|36.|...|
|7.4|...|...|
|.6.|.52|...|
+---+---+---+
|...|...|15.|
|...|...|426|
|...|...|7..|
+---+---+---+

and a 18-clue with 3 diagonal empty boxes - there isnt a 17-puzzle with 3 empty boxes though.

Code: Select all

+---+---+---+
|2..|.6.|...|
|.1.|.85|...|
|4..|...|...|
+---+---+---+
|...|...|.14|
|.7.|...|..3|
|.85|...|...|
+---+---+---+
|...|42.|...|
|...|3..|.8.|
|...|...|57.|
+---+---+---+

as ever ...... its not proof though.

C

[coloin]

as ever ...... its not proof though.

Maybe not quite

Number of different patterns in 8 boxes

Code: Select all

N                 B1B2B3B4B5B6B7B8
11                    32465851
12                   131758212


looking at it this way

Code: Select all

+---+---+---+
|x..|...|...|
|...|x..|...|
|...|...|x..|       
+---+---+---+       
|...|xxx|...|       
|...|xxx|.x.|       
|...|xxx|...|       
+---+---+---+       
|...|...|...|       
|...|...|...|       
|...|...|..x|       
+---+---+---+  any 6 in B478 - easy to see these will be impossible

what about this one of the 32465851

Code: Select all

+---+---+---+
|..x|...|...|
|...|xx.|...|
|...|...|x..|       
+---+---+---+       
|..x|xxx|...|       
|...|xxx|x..|       
|...|xxx|x..|       
+---+---+---+       
|...|.x.|..x|       
|.x.|...|...|       
|x..|...|...|
+---+---+---+  Is this impossible ?  ....... [Edited as one of the crossings was impossible].....

I can state that the list of maximal patterns, containing 4 entire filled corner boxes (published above 40-patterns list) is sufficient to prove non-existence 11-clue valid puzzles .....

Well that means you have excluded all 11 clue patterns with one empty box [?]

By any chance does that empty box in your patterns always have 9 clues in it ?

If so .........

It would mean that you have proved that box 11plus9-puzzles are impossible
Which at a stroke you have proved that all 13-clue puzzles are impossible
because with 13 clues - there has to be 2 clues in a box.
Looking for proofs - it would also prove that 17-puzzles with 6 clues in a box are impossible

C

[Serg]

Hi, coloin!

Number of different patterns in 8 boxes

Code: Select all

N                 B1B2B3B4B5B6B7B8
11                    32465851
12                   131758212


Do you mean patterns containing 0 or 9 clues in B9 box? How did you calculated these numbers?

looking at it this way

Code: Select all

+---+---+---+
|x..|...|...|
|...|x..|...|
|...|...|x..|       
+---+---+---+       
|...|xxx|...|       
|...|xxx|.x.|       
|...|xxx|...|       
+---+---+---+       
|...|...|...|       
|...|...|...|       
|...|...|..x|       
+---+---+---+  any 6 in B478 - easy to see these will be impossible

I agree, such patterns are subsets of Magic Pattern.

what about this one of the 32465851

Code: Select all

+---+---+---+
|..x|...|...|
|...|xx.|...|
|...|...|x..|       
+---+---+---+       
|..x|xxx|...|       
|...|xxx|x..|       
|...|xxx|x..|       
+---+---+---+       
|...|.x.|..x|       
|.x.|...|...|       
|x..|...|...|
+---+---+---+  Is this impossible ?  ....... [Edited as one of the crossings was impossible].....

At least this pattern passes check by 40-patterns list, so it can have valid puzzles.

I can state that the list of maximal patterns, containing 4 entire filled corner boxes (published above 40-patterns list) is sufficient to prove non-existence 11-clue valid puzzles .....

Well that means you have excluded all 11 clue patterns with one empty box [?]

Yes.

By any chance does that empty box in your patterns always have 9 clues in it ?

I don't understand - in what way can empty box contain 9 clues?

It would mean that you have proved that box 11plus9-puzzles are impossible

Why? If we would substitute empty box by entire filled box we would get patterns of different type. "9plus11" and "0plus11" - absolutely different classes of patterns. Maybe I missed something...

Which at a stroke you have proved that all 13-clue puzzles are impossible
because with 13 clues - there has to be 2 clues in a box.

I don't understand your idea .

Looking for proofs - it would also prove that 17-puzzles with 6 clues in a box are impossible

Yes, if we would have proof 9plus11 patterns impossibility, then we could prove 17-puzzles with 6 clues in a box impossibility. But we have no proof 9plus11 patterns impossibility yet...

Serg

[coloin]

Hi Serg sorry i missed your reply ..........
to answer
JPF calcultated those figures innthis thread here
and yes the B9 box will have 0 or 9 clues ....

I see that that 11 clue pattern by-passes your set of impossible patterns ...... hmmmm

No you havnt missed something there ..... i also see that an empty box cant have 9 clues !
I think I was getting ahead of myself there - what I meant probably is that number of ED ways 11 clues over 8 boxes [32465851] is going to be reduced to a great extent with your impossible patterns. But not fully because i managed to construct one which passes.

Anyhow

I don't understand your idea

EDIT
well ... assuming we have proved the 11 clues plus 9 thing - [and we havnt yet i agree][and it might be a very big if]

All 20 clue patterns with 11 plus 9 are impossible
All 19 clue patterns with 11 plus 8
All 17 clue patterns with 11 plus 6
All 14 clue patterns with 11 plus 3
All 13 clue patterns with 11 plus 2 - which is all 13 clue patterns

With respect to the multitude of row and box 9plus13 puzzles i have made - an empty box is a relative rarity.
Less than 1 in 500 in the corner boxes with a full central B5.

The box 9plus11 exercise is actually a simultaneous exercise with 4 crossing patterns.

The number of templates where there are 8 clues [1 per box ] in 8 boxes is small compared to 32465851 ..... ? < 6000
certainly less than ~ 12945 [9^8/ 6^4 *2^3]

Code: Select all

+---+---+---+
|...|...|...|
|.4.|.1.|.9.|
|...|...|...|
+---+---+---+
|...|...|...|
|.1.|.X.|.4.|
|...|...|...|
+---+---+---+
|...|...|...|
|.9.|.4.|.1.|
|...|...|...|
+---+---+---+  9*9*4*4*4 = 5184

reducing by 2*2*2 for band swaps and reflection leaves at most 648.

EDIT
Whateverway i tried to estimate the number of ED 9plus8 puzzles without an empty box....
I generated 385 only

Code: Select all

001#....................X..X..X....................X..X..X......XXX......XXX..X..XXXX
002#....................X..X..X....................X..X..X......XXX......XXX..X.X.XXX
003#....................X..X..X....................X..X..X......XXX......XXX.X..X.XXX
    ......                                                                           
    ......                                                                           
    ......                                                                           
382#.................X..X..X..........X.....X.....X..........XXX......XXXX..X..XXX...
383#........X.....X.....X..............X....X.....X.............XXX......XXXX..X..XXX
384#........X.....X.....X..............X....X.....X.............XXX...X..XXXX.....XXX
385#........X.....X.....X.............X.....X.....X.............XXX...X..XXXX.....XXX

adding any 3 would give us all 9plus11 patterns without an empty box, and yes quite a lot of patterns.......
C

[champagne]

question to serg or blue,

in the summary, p121 is described in that way not minlex (can exchange rows 2 and 3 and stacks 2 and 3)
as far as I can see, all others are minlex;
is it correct or is there any typo

Code: Select all

        P121                   
+-----+-----+-----+     
|. . .|. . .|. . .|       
|. . .|. . .|. 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|     
+-----+-----+-----+       

[Serg]

Hi, champagne!

in the summary, p121 is described in that way not minlex (can exchange rows 2 and 3 and stacks 2 and 3)
as far as I can see, all others are minlex;
is it correct or is there any typo

Code: Select all

        P121                   
+-----+-----+-----+     
|. . .|. . .|. . .|       
|. . .|. . .|. 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|     
+-----+-----+-----+       

Your question concerns my representation of 40 maximal patterns list (blue published his own representation of these patterns in this thread). My representation is neither minlex nor maxlex form. It is simply suitable for me view.

Serg