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 09, 2013 10:40 pm

Hi, people!
I've done at last search for patterns not having valid puzzles for the "variant 1 of patterns containing one empty box", i.e. I've checked patterns containing exactly 1 empty box which is placed at "periphery" (B7 empty box). Here are 20 possible such patterns.
Code: Select all
Patterns having no valid puzzles:

        P101                       P102                       P103
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . 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 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 x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P104                       P105                       P106
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . 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 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|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|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P107                       P108                       P109
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . 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 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 x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P110                       P111                       P112
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . 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|        |. . .|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|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P113                       P114                       P115
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . 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 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 x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P116                       P117                       P118
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . 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 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|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P119                       P120
+-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . .|. . 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|
+-----+-----+-----+        +-----+-----+-----+
|. . .|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
[Edited: I added pattern P120 missing in original post. Thanks to Blue for this correction.]
[Edited: I changed terminogy - some published above patterns are not maximal in the strict sense, i.e. they can be extended by adding clues in B7 box.]
Last edited by Serg on Mon May 13, 2013 10:41 am, edited 2 times in total.
Serg
2017 Supporter
 
Posts: 501
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby blue » Fri May 10, 2013 8:25 pm

Hi Serg,

Well done !
I can confirm that they don't have puzzles.

It looks like you forgot to include one.
(I'm sure you have it).

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 x |
+-------+-------+-------+

It isn't a subset of one of the others is it ?
(It isn't maximal).

Except for that one, your list matches mine.
Thank you for the confirmations.

Best Regads,
Blue.
blue
 
Posts: 573
Joined: 11 March 2013

Re: Investigation of one-crossing-free patterns

Postby Serg » Sun May 12, 2013 7:09 am

Hi, Blue!
Thank you for confirmation of my results.
blue wrote:Hi Serg,
It looks like you forgot to include one.
(I'm sure you have it).

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 x |
+-------+-------+-------+

It isn't a subset of one of the others is it ?
(It isn't maximal).

I missed this pattern. Patterns P101, P103, P105 and P107 were produced "artificially", by hand, from already published 4 maximal patterns which were proven by you not to have valid puzzles, so I can be wrong. But remaining patterns were produced by true exhaustive search (and cross-checks), so I am sure there are no other patterns not having valid puzzles with empty B7 box and filled boxes B5, B6, B8 and B9. Maybe it would be better to publish true maximal patterns only, because at the end of this investigation maximal patterns only will participate final list of patterns not having valid puzzles with free crossing. Nevertheless, thank you for correction (I'll edit my previous post).

I checked remaining 15 published pattern for maximality. It turns out, patterns P102, P104, P108-P116, P118-P119 (totally 13 patterns) are really maximal, but patterns P106 and P117 are not maximal. Both patterns can be extended futher to maximal patterns
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 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|
+-----+-----+-----+     +-----+-----+-----+

So, only published below 13 patterns with empty B7 box are really maximal.
Code: Select all
Maximal patterns with empty B7 box:

        P102                       P104                       P108
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . .|. . 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 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 x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P109                       P110                       P111
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . 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 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|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P112                       P113                       P114
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . 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|        |. . .|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|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P115                       P116                       P118
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . .|. . .|        |. . .|. . 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 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 x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

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

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Wed May 22, 2013 5:43 am

Hi, people!
I've done search for patterns not having valid puzzles for the "variant 2 of patterns containing one empty box", i.e. I've checked patterns containing exactly 1 empty box which is placed at the "centre" of crossing (B1 empty box). There are 7 possible such patterns only.
Code: Select all
Patterns having no valid puzzles, which cannot be expanded by adding clues in the B2, B3, B4 and B7 boxes:

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

        P124                       P125                       P126
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . 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|
|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|        |. . .|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|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

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

It turns out, all these patterns, but P127, are maximal, i.e. adding 1 clue to B1 box brokes their property "not having valid puzzes".

So, all possible crossing patterns containing exactly 1 empty box were considered. I should check the last (the most complicated) case of crossings pattern - crossing patterns without empty boxes.

Serg

[Edited. I corrected 2 errors - P126 pattern contained extra clues, P127 pattern was missed. (Manual error.) Thanks to blue for his correction.]
Last edited by Serg on Fri May 24, 2013 6:16 am, edited 1 time in total.
Serg
2017 Supporter
 
Posts: 501
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby blue » Thu May 23, 2013 7:17 pm

Hi Serg,

Great work again !
I have one differnce from your results.

In place of this patten:

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 x|x x x|x x x|
+-----+-----+-----+

I have this one, as a maximal pattern:

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|x x x|
+-----+-----+-----+

and the (non-maximal) pattern that's a subset of this (maximal) pattern from our earlier discussions:

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 x|x x x|
+-----+-----+-----+

Best Regards,
Blue.
blue
 
Posts: 573
Joined: 11 March 2013

Re: Investigation of one-crossing-free patterns

Postby Serg » Fri May 24, 2013 6:07 am

Hi, blue!
blue wrote:I have one differnce from your results.

In place of this patten:

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 x|x x x|x x x|
+-----+-----+-----+

I have this one, as a maximal pattern:

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|x x x|
+-----+-----+-----+

and the (non-maximal) pattern that's a subset of this (maximal) pattern from our earlier discussions:

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 x|x x x|
+-----+-----+-----+

Best Regards,
Blue.

You are right, as usually. I copied wrongly P126 pattern from program listing, and then decided that subset of your last maximal pattern can be excluded. Manual error again! :evil: I'll edit my previous post to fix the error.

Thank you for confirmation of my results!

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Fri May 24, 2013 6:49 am

Hi, people!
I've done search for patterns without empty boxes not having valid puzzles. There are 8 possible such patterns only. One pattern is new, the rest were published earlier. All these patterns are maximal.
Code: Select all
Maximal patterns containing no empty boxes:

        P128                       P129                       P130
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . 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|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|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|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P131                       P132                       P133
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . .|. . 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 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 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|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P134                       P135
+-----+-----+-----+        +-----+-----+-----+
|. . .|. . 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|
|. . .|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|
+-----+-----+-----+        +-----+-----+-----+

So, all possible maximal crossing patterns were considered.

I should mention for the sake of completeness one more maximal pattern:
Code: Select all
        P136
+-----+-----+-----+
|. . .|. . .|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|
+-----+-----+-----+

It is well known that this pattern has no valid puzzles. It turns out it is maximal.

Hope, I am not wrong this time :) .

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Fri May 24, 2013 8:11 am

Hi, blue!
Would you clarify the way of splitting posted below two-column UA18 to Type-A and Type-B pieces? (Two-row UA18 is splitted easily.) Published fragment is part of real solution grid.
Code: Select all
+-----+-----+-----+
|9 1 2|3 4 5|6 8 7|
|3 8 4|1 6 7|5 2 9|
|5 6 .|. . .|. . .|
+-----+-----+-----+
|1 5 .|
|6 4 .|
|2 7 .|
+-----+
|4 2 .|
|8 3 .|
|7 9 .|
+-----+

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

Re: Investigation of one-crossing-free patterns

Postby coloin » Fri May 24, 2013 1:27 pm

Fantastic work Serg

Now the fun starts

There will be many 16 clue patterns which are within each one of your "proven impossible" patterns.

What are the reductions on the symmetric 18s - perhaps the main incentive for this work ?

Many patterns with 9 clues plus 12 will be impossible too [either 9 clues in a box or 9 clues in a row].

Currently i have found 105 vertical-9plus12s [ongoing] and 143 box-9plus12s [stopped]. here

C
coloin
 
Posts: 1624
Joined: 05 May 2005

Re: Investigation of one-crossing-free patterns

Postby blue » Fri May 24, 2013 2:49 pm

Hi Serg,

Serg wrote:Would you clarify the way of splitting posted below two-column UA18 to Type-A and Type-B pieces? (Two-row UA18 is splitted easily.) Published fragment is part of real solution grid.
Code: Select all
+-----+-----+-----+
|9 1 2|3 4 5|6 8 7|
|3 8 4|1 6 7|5 2 9|
|5 6 .|. . .|. . .|
+-----+-----+-----+
|1 5 .|
|6 4 .|
|2 7 .|
+-----+
|4 2 .|
|8 3 .|
|7 9 .|
+-----+

I'm confused -- it's UA4+UA14 in the columns.

Blue.
blue
 
Posts: 573
Joined: 11 March 2013

Re: Investigation of one-crossing-free patterns

Postby Serg » Fri May 24, 2013 3:27 pm

Hi, coloin!
coloin wrote:Fantastic work Serg

Thanks!
coloin wrote:What are the reductions on the symmetric 18s - perhaps the main incentive for this work ?

You are right. I started this work keeping in mind additional reduction of the search space for symmetric 18-clue patterns.
coloin wrote:Many patterns with 9 clues plus 12 will be impossible too [either 9 clues in a box or 9 clues in a row].
Currently i have found 105 vertical-9plus12s [ongoing] and 143 box-9plus12s [stopped]. here

Finding all possible "9 plus 12" patterns and proving impossibility of "9 plus 11" patterns are interesting tasks too. But first I should develope universal program for exhaustive search of valid puzzles for any given pattern (now I have searching program for one-crossing-free patterns only). Hope I'll do it.

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Fri May 24, 2013 4:41 pm

Hi, blue!
blue wrote:
Serg wrote:Would you clarify the way of splitting posted below two-column UA18 to Type-A and Type-B pieces? (Two-row UA18 is splitted easily.) Published fragment is part of real solution grid.
Code: Select all
+-----+-----+-----+
|9 1 2|3 4 5|6 8 7|
|3 8 4|1 6 7|5 2 9|
|5 6 .|. . .|. . .|
+-----+-----+-----+
|1 5 .|
|6 4 .|
|2 7 .|
+-----+
|4 2 .|
|8 3 .|
|7 9 .|
+-----+

I'm confused -- it's UA4+UA14 in the columns.
Sorry, it seems my question isn't stated clearly.
Maybe I am still missing something in your "2 rows + 2 columns" UA sets construction.

Let's consider my example in more details.
Splitting two-rows UA18 gives
Code: Select all
   "A-rows" piece     "B-rows" piece
+-----+-----+-----+     +-----+-----+-----+
|9 . 2|. 4 5|6 8 7|     |. 1 .|3 . .|. . .|
|. 8 4|. 6 7|5 2 9|     |3 . .|1 . .|. . .|
|. . .|. . .|. . .|     |. . .|. . .|. . .|
+-----+-----+-----+     +-----+-----+-----+

Let's find "A-cols" piece. We are starting from r1c1 cell, i.e. from "9" digit. It has "pair" cell r2c2 - "8" digit. Then we should search column c1 for "8" digit. We can find it in r8c1 cell. It's "pair" cell - r8c2 (digit "3"). So, we have chain r1c1 --> r2c2 --> r8c1 --> r8c2 --> r2c1 --> r2c2, so we cannot close chain and come to r9c2 cell. Therefore we cannot split given two-column UA18 to "A-cols" and "B-cols" pieces.

Serg

P.S. I got to understand my error, sorry. Your method demands two-row and two-column UA set be analysed for minimality first. Splitting to "type A" and "type B" pieces must be applied to minimal UA18 sets only. Two-row UA18 in my example is minimal, so it can be splitted to "A-rows" and "B-rows" pieces. But two-column UA18 in my example is not minimal, so splitting fails (it can or cannot fail - it depends on UA subset structure). So, 2 clues in r1c1 and r2c2 cells potentially can break all UA sets placed entirely in r1/r2 rows and c1/c2 columns.

P.P.S. blue, thank you for your clarification. I've seen your post after submitting my P.S. to this post.
Last edited by Serg on Fri May 24, 2013 5:32 pm, edited 2 times in total.
Serg
2017 Supporter
 
Posts: 501
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby blue » Fri May 24, 2013 5:11 pm

Hi Serg,

I see. What you say is true. The (A/B) split will only succeed when the r1c12 and r2c12 segments are part of the same (minimal) 2-column UA set. With a minimal UA18, that's always true, of course.

This is the smallest UA that can be split like that:
Code: Select all
+-------+   +-------+   +-------+
| 1 2 . |   | 1 . . |   | . 2 . |
| 3 4 . |   | . 4 . |   | 3 . . |
| . . . |   | . . . |   | . . . |
+-------+   +-------+   +-------+
| 2 3 . |   | . . . |   | 2 3 . |
| . . . | = | . . . | u | . . . |
| . . . |   | . . . |   | . . . |
+-------+   +-------+   +-------+
| 4 1 . |   | 4 1 . |   | . . . |
| . . . |   | . . . |   | . . . |
| . . . |   | . . . |   | . . . |
+-------+   +-------+   +-------+

Blue.
blue
 
Posts: 573
Joined: 11 March 2013

Re: Investigation of one-crossing-free patterns

Postby Serg » Sun May 26, 2013 10:32 am

Hi, people!
This is summary - list of all possible one-crossing-free (i.e. having 9 clues in B5, B6, B8 and B9 boxes) maximal patterns.
Code: Select all
Maximal patterns containing no empty boxes:

        P128                       P129                       P130
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . 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|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|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|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P131                       P132                       P133
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . .|. . 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 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 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|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P134                       P135                       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 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|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|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

Totally 9 patterns


Maximal patterns containing 1 empty box:

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

        P124                       P125                       P126
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . 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|
|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|        |. . .|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|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P102                       P104                       P108
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . .|. . 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 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 x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P109                       P110                       P111
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . 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 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|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P112                       P113                       P114
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . 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|        |. . .|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|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P115                       P116                       P118
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . .|. . .|        |. . .|. . 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 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 x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

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

Totally 19 patterns


Maximal patterns containing 2 empty boxes:

         P32                       P138                       P139
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . 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 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 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|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

         P98                        P99                       P100
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|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|
|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 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|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

         P90                        P92
+-----+-----+-----+        +-----+-----+-----+
|. . .|. . 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|        |. . .|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|
+-----+-----+-----+        +-----+-----+-----+

Totally 8 patterns


Maximal patterns containing 3 empty boxes:

         P140                      P141                       P136
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . 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 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 x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

Totally 3 patterns


Maximal patterns containing 4 empty boxes:

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

Totally 1 pattern

There are 40 maximal patterns in total with "fixed" boxes B5, B6, B8 and B9 (i.e. these boxes must contain 9 clues each). Four of them (P134, P137, P138 and P139) were published before opening of this thread, the rest are new.

Investigation of one-crossing-free patterns is finished. Thanks to all for help and attention. Separate thanks to blue for his cross-checking of these results, many new valuable results/ideas posted in this thread.

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

Re: Investigation of one-crossing-free patterns

Postby blue » Thu May 30, 2013 6:23 am

Hi Serg,

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

I have the same list, for "maximal patterns". Thank you in return, for the confirmations.
You helped me find a case (too), where I had copied a pattern incorrectly -- #30 below, with one empty box.

Since we used completely different code, I think our final results must be correct.

This was my list.
It has the 40 patterns, plus two isomorphs -- 2a,2b and 3a,3b.

Code: Select all
         (1)                        (2a)                        (2b)

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       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 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


        (3a)                        (3b)                         (4)

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       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       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


         (5)                         (6)                         (7)

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       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       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


         (8)                         (9)                        (10)

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


        (11)                        (12)                        (13)

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
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 | 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


        (14)                        (15)                        (16)

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


        (17)                        (18)                        (19)

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 | . . . | 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 x x | . x . | x x x       x x x | x x x | x x x       x x x | x x x | x x x


        (20)                        (21)                        (22)

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
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 | x x x       x x x | x x x | x x x       x x x | x x x | x x x


        (23)                        (24)                        (25)

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 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 | x x x       x x x | x x x | x x x       x x x | x x x | x x x


        (26)                        (27)                        (28)

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 . | . . .       . . . | . 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 x x       x x x | x x x | x x x       x x x | . . . | x x x


        (29)                        (30)                        (31)

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
. . . | . . . | . 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 x       x x x | x x x | x x x


        (32)                        (33)                        (34)

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 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 | x x x


        (35)                        (36)                        (37)

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
. . . | 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 x x


        (38)                        (39)                        (40)

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

Best Regards,
Blue.
blue
 
Posts: 573
Joined: 11 March 2013

PreviousNext

Return to General