Investigation of one-crossing-free patterns

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Thu May 30, 2013 5:41 pm

Hi, blue!
blue wrote:Great work again !
Thanks!
blue wrote: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).
blue wrote: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
Serg
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby coloin » Sun Jun 02, 2013 1:35 am

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
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Re: Investigation of one-crossing-free patterns

Postby coloin » Sun Jun 02, 2013 11:24 pm

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
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Re: Investigation of one-crossing-free patterns

Postby Serg » Mon Jun 03, 2013 6:50 am

Hi, coloin!
coloin wrote: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?
coloin wrote: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
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby Serg » Mon Jun 03, 2013 6:36 pm

Hi, coloin!
coloin wrote: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
Serg
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby coloin » Tue Jun 04, 2013 8:45 am

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
Last edited by coloin on Tue Jun 04, 2013 11:57 am, edited 1 time in total.
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Re: Investigation of one-crossing-free patterns

Postby coloin » Tue Jun 04, 2013 9:14 am

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
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Re: Investigation of one-crossing-free patterns

Postby Serg » Wed Jun 05, 2013 4:16 am

Hi, coloin!
coloin wrote: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.

coloin wrote: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
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby Serg » Wed Jun 05, 2013 4:41 am

Hi, coloin!
coloin wrote: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).
coloin wrote: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
Serg
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby coloin » Thu Jun 06, 2013 12:47 am

Indeed..... it would be even a little easier to put 12 clues in 8 boxes which would defeat the 40 patterns without puzzles
Serg wrote: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
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Re: Investigation of one-crossing-free patterns

Postby coloin » Thu Jun 06, 2013 10:17 am

coloin wrote: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].....

serg wrote: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
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Re: Investigation of one-crossing-free patterns

Postby Serg » Mon Jun 10, 2013 4:31 pm

Hi, coloin!
coloin wrote: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?
coloin wrote: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.
coloin wrote: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.
coloin wrote:
serg wrote: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.
coloin wrote: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?
coloin wrote: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...
coloin wrote: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 :( .
coloin wrote: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
Serg
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby coloin » Fri Jun 21, 2013 10:34 pm

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
serg wrote: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
Last edited by coloin on Sun Jun 28, 2015 1:42 pm, edited 2 times in total.
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Re: Investigation of one-crossing-free patterns

Postby champagne » Sun Oct 26, 2014 5:09 pm

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Sun Oct 26, 2014 8:30 pm

Hi, champagne!
champagne wrote: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
Serg
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

PreviousNext

Return to General