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 » Sat Feb 23, 2013 8:07 am

Hi!
I continue studying patterns having 4-clue configurations in B1 box.
Patterns with B1 box configuration
Code: Select all
. . x
. . x
. x x
are symmetric to the patterns having B1 box configuration
Code: Select all
. . .
. . x
x x x
Because we are interesting in essentially different patterns only, we can skip this configuration.

Next 4-clue B1 box configuration is
Code: Select all
. . .
. x x
. x x
It turns out that all possible patterns (P54 - P56) containing such B1 box configuration have valid puzzles even if B2/B4 boxes contain 1 clue each only.
Code: Select all
         P54                     P55                     P56
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . .|. . .|     |. . .|. . x|. . .|
|. x x|. . .|. . .|     |. x x|. . .|. . .|     |. x x|. . .|. . .|
|. x x|. . x|. . .|     |. x x|. . x|. . .|     |. x x|. . .|. . .|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . x|x x x|x x x|     |x . .|x x x|x x x|     |x . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|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, studying patterns having 4-clue configurations in B1 box is finished.
At this moment we have such validity diagram
Code: Select all
0  ?
1  ?
2  ???
3  ??????
4  ***++++
5  *++++++
6  ++++++
7  +++
8  +
9  +
for patterns with map
Code: Select all
A 1 0
1 9 9
0 9 9
(A > 0).

Continuation follows ...

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Sun Feb 24, 2013 8:44 am

Hi, I continue.
Now it is the turn to analyze 3-clue configurations in B1 box.
Let's start with configuration
Code: Select all
. . .
. . x
. x x
There are 6 essentially different variants of such patterns, having 1 clue in B2 and B4 boxes:
Code: Select all
         P57                     P58                     P59
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . .|. . .|     |. . .|. . .|. . .|
|. . x|. . .|. . .|     |. . x|. . .|. . .|     |. . x|. . .|. . .|
|. x x|. . x|. . .|     |. x x|. . x|. . .|     |. x x|. . x|. . .|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . x|x x x|x x x|     |. x .|x x x|x x x|     |x . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+

         P60                     P61                     P62
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . .|. . .|     |. . .|. . x|. . .|
|. . x|. . x|. . .|     |. . x|. . x|. . .|     |. . x|. . .|. . .|
|. x x|. . .|. . .|     |. x x|. . .|. . .|     |. x x|. . .|. . .|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. x .|x x x|x x x|     |x . .|x x x|x x x|     |x . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
Patterns P57-P59 have no valid puzzles, because they are subsets of P53 pattern (see previous posts). Search shows remaining patterns (P60-P62) have valid puzzles.

I'm trying to increase number of clues in B2/B4 boxes preserving property "pattern has no valid puzzles". Let's consider the ways to do it. If B2 box contains at least 1 clue in r1/r2 rows (6-cell "sensible area") AND B4 box contains at least 1 clue in c1/c2 columns (6-cell "sensible area" too), pattern definitely has valid puzzles (see patterns P60-P62). So, pattern has no valid puzzles if B2 box contains clues in r3 row only OR B4 box contains clues in c3 column only. Because B1 box contains symmetric clue configuration, we can limit our study to the case when B2 box contains clues in r3 row only. What are possible B4 box configurations provided that pattern has no valid puzzles?
Exhaustive search shows that next 3 patterns
Code: Select all
         P63                     P64                     P65
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . .|. . .|     |. . .|. . .|. . .|
|. . x|. . .|. . .|     |. . x|. . .|. . .|     |. . x|. . .|. . .|
|. x x|. . x|. . .|     |. x x|. . x|. . .|     |. x x|. . x|. . .|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . x|x x x|x x x|     |. x .|x x x|x x x|     |. . x|x x x|x x x|
|. x .|x x x|x x x|     |x . .|x x x|x x x|     |x . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
have valid puzzles, so if B4 box has at least 2 clues located in different rows AND different columns, pattern has valid puzzles. Hence B4 box must contain all its clues in the same row only or in the same column only if we want a pattern would have no valid puzzles. So, we should check patterns
Code: Select all
         P66                     P67                     P68                     P69
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . .|. . .|     |. . .|. . .|. . .|     |. . .|. . .|. . .|
|. . x|. . .|. . .|     |. . x|. . .|. . .|     |. . x|. . .|. . .|     |. . x|. . .|. . .|
|. x x|. . x|. . .|     |. x x|. . x|. . .|     |. x x|. . x|. . .|     |. x x|. . x|. . .|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . x|x x x|x x x|     |. x .|x x x|x x x|     |x . .|x x x|x x x|     |. . .|x x x|x x x|
|. . x|x x x|x x x|     |. x .|x x x|x x x|     |x . .|x x x|x x x|     |. . .|x x x|x x x|
|. . x|x x x|x x x|     |. x .|x x x|x x x|     |x . .|x x x|x x x|     |x x x|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
Exhaustive search shows, that patterns P66 and P69 have no valid puzzles, but patterns P67 and P68 have valid puzzles. So, all patterns of the type considered having no valid puzzles are subsets of patterns P52 or P53.

Therefore this type of patterns contributes nothing new to general case (when maps are
Code: Select all
A B 0
C 9 9
0 9 9
A > 0, B > 0, C > 0).

Continuation follows ...

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Tue Feb 26, 2013 6:11 am

Hi, I continue.
Now it is the turn to analyze 3-clue B1 box configuration
Code: Select all
. . .
. . .
x x x
There are 2 essentially different variants of such patterns, having 1 clue in B2 and B4 boxes:
Code: Select all
         P70                     P71
+-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . .|. . .|
|. . .|. . .|. . .|     |. . .|. . x|. . .|
|x x x|. . x|. . .|     |x x x|. . .|. . .|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . x|x x x|x x x|     |. . x|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----
Pattern P70 has no valid puzzles, because it has 2 empty rows in B1B2B3 band. (It is true for arbitrary B4 box clue configuration and arbitrary r3 row clue configuration.) Formally speaking, pattern P70 is subset of the next pattern, which has no valid puzzles.
Code: Select all
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
Search shows Pattern P71 has no valid puzzles too.

One should increase number of clues in B2/B4 boxes preserving property "pattern has no valid puzzles". The simplest (but not smartest) way to do it - to check all possible combinations of B2/B4 boxes configurations. The final result is finding of 2 new patterns having no puzzles:
Code: Select all
         P72                     P73
+-----+-----+-----+     +-----+-----+-----+
|. . .|. . x|. . .|     |. . .|. . x|. . .|
|. . .|. . x|. . .|     |. . .|. . x|. . .|
|x x x|x x x|. . .|     |x x x|x x x|. . .|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . x|x x x|x x x|
|x x x|x x x|x x x|     |. . x|x x x|x x x|
|x x x|x x x|x x x|     |. . x|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+

Continuation follows ...

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Tue Feb 26, 2013 6:52 am

Hi, I continue.
I'll study patterns having next 3-clue configuration in B1 box.
Code: Select all
. . .
. . x
x x .
There are 6 essentially different variants of such patterns, having 1 clue in B2 and B4 boxes:
Code: Select all
         P74                     P75                     P76
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . .|. . .|     |. . .|. . .|. . .|
|. . x|. . .|. . .|     |. . x|. . .|. . .|     |. . x|. . x|. . .|
|x x .|. . x|. . .|     |x x .|. . x|. . .|     |x x .|. . .|. . .|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . x|x x x|x x x|     |. x .|x x x|x x x|     |. . x|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+

         P77                     P78                     P79
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . x|. . .|     |. . .|. . x|. . .|
|. . x|. . x|. . .|     |. . x|. . .|. . .|     |. . x|. . .|. . .|
|x x .|. . .|. . .|     |x x .|. . .|. . .|     |x x .|. . .|. . .|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. x .|x x x|x x x|     |. . x|x x x|x x x|     |. x .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+     +-----+-----+-----+
Patterns P74-P75 have no valid puzzles, because they are subsets of P53 pattern (see previous posts). Search shows the patterns P76-P79 have valid puzzles. Next 2 patterns
Code: Select all
         P80                     P81
+-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . .|. . .|
|. . x|. . .|. . .|     |. . x|. . .|. . .|
|x x .|. . x|. . .|     |x x .|. . x|. . .|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . x|x x x|x x x|     |. x .|x x x|x x x|
|. x .|x x x|x x x|     |x . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+
have valid puzzles, so if B4 box has at least 2 clues located in different rows AND different columns, pattern has valid puzzles. Hence B4 box must contain all its clues in the same row only or in the same column only if we want a pattern would have no valid puzzles. This idea is right - patterns
Code: Select all
         P82                     P83
+-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . .|. . .|
|. . x|. . .|. . .|     |. . x|. . .|. . .|
|x x .|. . x|. . .|     |x x .|. . x|. . .|
+-----+-----+-----+     +-----+-----+-----+
|. . x|x x x|x x x|     |. . .|x x x|x x x|
|. . x|x x x|x x x|     |. . .|x x x|x x x|
|. . x|x x x|x x x|     |x x x|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+
have no valid puzzles. If we add 1 clue to B4 box in these patterns (to the arbitrary free cell), they will have valid puzzles.
But 3rd possible pattern
Code: Select all
         P84
+-----+-----+-----+
|. . .|. . .|. . .|
|. . x|. . .|. . .|
|x x .|. . x|. . .|
+-----+-----+-----+
|. x .|x x x|x x x|
|. x .|x x x|x x x|
|. x .|x x x|x x x|
+-----+-----+-----+
|. . .|x x x|x x x|
|. . .|x x x|x x x|
|. . .|x x x|x x x|
+-----+-----+-----+
has valid puzzles.

If B2 box contains clues in r1/r2 rows, pattern has valid puzzles. So, next patterns have no valid puzzles with maximal number of clues in B2/B4 boxes:
Code: Select all
         P85                     P86
+-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . .|. . .|
|. . x|. . .|. . .|     |. . x|. . .|. . .|
|x x .|x x x|. . .|     |x x .|x x x|. . .|
+-----+-----+-----+     +-----+-----+-----+
|. . x|x x x|x x x|     |. . .|x x x|x x x|
|. . x|x x x|x x x|     |. . .|x x x|x x x|
|. . x|x x x|x x x|     |x x x|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+
Both patterns are not interesting, because pattern P85 is subset of P36 pattern, but P86 is subset of P53 pattern.

So, this configuration gives us nothing new.

Continuation follows ...

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Fri Mar 08, 2013 8:06 am

Hi, all!
I found a bug in my code, so it took me several days to fix the bug and to repeat exhaustive searches for all patterns considered in this thread. Search repetition itself took me 12 hours. It turns out, that bug didn't affected search results, so I confirm validity of my results published in this thread.

Now it is the turn to analyze the last 3-clue B1 box configuration
Code: Select all
. . x
. x .
x . .
There are 2 essentially different variants of such patterns, having 1 clue in B2 and B4 boxes:
Code: Select all
         P87                     P88
+-----+-----+-----+     +-----+-----+-----+
|. . x|. . .|. . .|     |. . x|. . .|. . .|
|. x .|. . .|. . .|     |. x .|. . .|. . .|
|x . .|. . x|. . .|     |x . .|. . x|. . .|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . x|x x x|x x x|     |x . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----
Exhaustive search shows both patterns have valid puzzles, so this type of patterns has nothing interesting.

it is the turn to analyze 2-clue B1 box configuration
Code: Select all
. . .
. . x
. x .
Let me post final results, omitting search details description (I doubt that it can be interesting) - I found 2 new patterns having no valid puzzles:
Code: Select all
         P89                     P90
+-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . x|. . .|
|. . x|. . .|. . .|     |. . x|. . x|. . .|
|. x .|x x x|. . .|     |. x .|. . x|. . .|
+-----+-----+-----+     +-----+-----+-----+
|. x .|x x x|x x x|     |. . .|x x x|x x x|
|. x .|x x x|x x x|     |. . .|x x x|x x x|
|. x .|x x x|x x x|     |x x x|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----

Let's consider the next type of 2-clue B1 box configuration
Code: Select all
. . .
. . .
. x x
I is very surprising, but this type of patterns adds nothing new to collection of patterns not having valid puzzles. Moreover, this class of patterns is absolutely equivalent to the class of patterns having B1 box configuration
Code: Select all
. . .
. . .
x x x
It turns out, both classes return the same results (pattern has valid puzzles or has no valid puzzles) for any B2/B4 boxes configurations.

So, study 2-clue B1 box configurations is finished.

Continuation follows ...

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Sat Mar 09, 2013 10:12 pm

Hi, all!
It is the turn to analyze (the only) 1-clue B1 box configuration
Code: Select all
. . .
. . .
. . x
This configuration is highly productive. I omit rather sophisticated sequence of exhaustive searches, I am publishing final result only - 7 new patterns having no valid puzzles:
Code: Select all
Patterns having no valid puzzles:
         P91                        P92                        P93
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. x x|. . .|        |. . .|. . x|. . .|
|. . .|. . x|. . .|        |. . .|. x x|. . .|        |. . .|. . x|. . .|
|. . x|. . .|. . .|        |. . x|. x x|. . .|        |. . x|x x x|. . .|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|x x x|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

         P94                        P95                        P96
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . x|. . .|        |. . .|. . .|. . .|
|. . .|x x x|. . .|        |. . .|. . x|. . .|        |. . .|x x x|. . .|
|. . x|. . .|. . .|        |. . x|x x x|. . .|        |. . x|. . .|. . .|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . x|x x x|x x x|        |. . x|x x x|x x x|
|x x x|x x x|x x x|        |. . x|x x x|x x x|        |. . x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

         P97
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|x x x|. . .|
|. . x|. . .|. . .|
+-----+-----+-----+
|. x .|x x x|x x x|
|. x .|x x x|x x x|
|. x .|x x x|x x x|
+-----+-----+-----+
|. . .|x x x|x x x|
|. . .|x x x|x x x|
|. . .|x x x|x x x|
+-----+-----+-----+
But P93 pattern is subset of P72 pattern, P96 pattern is subset of (transposed) P73 pattern, P97 pattern is subset of P89 pattern. So, we should "store for the future" P91, P92, P94 and P95 patterns only.

Investigation of variant V2 is finished.
Code: Select all
  V2

A B 0
C 9 9
0 9 9
(A > 0, B > 0, C > 0)

Continuation follows ...

Serg

[Edited. I corrected a typo.]
[Edited. I rejected 3 extra patterns (P93, P96 and P97) being subsets of other already published patterns. Thanks to blue for his correction.]
Last edited by Serg on Wed Mar 13, 2013 6:34 am, edited 1 time in total.
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby Serg » Sun Mar 10, 2013 10:49 am

Hi!
Let's consider variant V3 of patterns containing 2 empty boxes, i.e. patterns having map
Code: Select all
  V3

0 0 A
B 9 9
C 9 9
Below are final results of exhaustive search.
Code: Select all
Patterns having no valid puzzles:

         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|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
Plus 2 evident (old) patterns containing 9 clues in B4/B7 boxes:
Code: Select all
Patterns having no valid puzzles:

+-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . x|        |. . .|. . .|. . x|
|. . .|. . .|. . x|        |. . .|. . .|. x .|
|. . .|. . .|x x x|        |. . .|. . .|x . .|
+-----+-----+-----+        +-----+-----+-----+
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|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, analysis of the patterns containing 2 empty boxes is finished. Here is summary - list of such patterns having no valid patterns:
Code: Select all
Patterns having no valid puzzles:

+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . x|. . .|. . .|        |. . x|. . .|. . .|        |. . .|. . .|. . .|
|. . x|. . .|. . .|        |. x .|. . .|. . .|        |. . .|. . .|. . .|
|x x x|. . .|. . .|        |x . .|. . .|. . .|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

         P32                        P36                        P53
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . x|. . .|. . .|        |. . .|. . .|. . .|
|. x x|. . .|. . .|        |. . x|. . .|. . .|        |. . x|. . .|. . .|
|x x x|x x x|x x x|        |x x x|x x x|. . .|        |x x x|x x x|. . .|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . x|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . x|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

         P72                        P73                        P89
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . x|. . .|        |. . .|. . x|. . .|        |. . .|. . .|. . .|
|. . .|. . x|. . .|        |. . .|. . x|. . .|        |. . x|. . .|. . .|
|x x x|x x x|. . .|        |x x x|x x x|. . .|        |. x .|x x x|. . .|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . x|x x x|x x x|        |. x .|x x x|x x x|
|x x x|x x x|x x x|        |. . x|x x x|x x x|        |. x .|x x x|x x x|
|x x x|x x x|x x x|        |. . x|x x x|x x x|        |. x .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|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                        P91                        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 x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

         P94                        P95                        P98
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . x|. . .|        |. . .|. . .|x x x|
|. . .|x x x|. . .|        |. . .|. . x|. . .|        |. . .|. . .|x x x|
|. . x|. . .|. . .|        |. . x|x x x|. . .|        |. . .|. . .|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . x|x x x|x x x|        |. . .|x x x|x x x|
|x x x|x x x|x x x|        |. . x|x x x|x x x|        |. . .|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |x x x|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

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

Continuation follows ...

Serg

[Edited. I corrected my mistake - rejected 3 extra patterns (P93, P96 and P97) being subsets of other already published patterns. Thanks to blue for his correction.]
[Edited. I corrected my mistake - added missed pattern (P100). Thanks to blue for his correction.]
Last edited by Serg on Sun Mar 17, 2013 10:18 pm, edited 2 times in total.
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby blue » Tue Mar 12, 2013 5:21 am

Serg wrote:So, analysis of the patterns containing 2 empty boxes is finished. Here is summary - list of such patterns having no valid patterns:
Serg


Hello Serg.

Nice work !
I can confirm (up to possible bugs in my own code), that none of those patterns have puzzles.

I see a few problems, though.
Best to tell you now, before you get too far into "one empty box" and "no empty box" patterns.

1. Your pattern P93, is a subset of P72.

2. I think there is a missing pattern. Can you confirm that it has no puzzles ? I think it is also maximal.
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 |
+-------+-------+-------+

3. Two of your patterns are not maximal for the "2-empty-box" condition. P96 and P97 can be extended to maximal subsets of these 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 x |
+-------+-------+-------+     +-------+-------+-------+
For those patterns, like the one discussed here (and one other), there are fairly easy proofs that they have no puzzles.

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Tue Mar 12, 2013 10:28 pm

Hi, blue!
Glad to see you at this forum. Welcome!

At last someone cross-checks my posts! The most error-prone procedure in my investigation - identification of "superset" pattern, containing given pattern as subset. I do it "by eye", hence can be wrong.
blue wrote:1. Your pattern P93, is a subset of P72.

You are right. P93 is extra pattern.
blue wrote:2. I think there is a missing pattern. Can you confirm that it has no puzzles ? I think it is also maximal.
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 |
+-------+-------+-------+


Yes, I confirm this pattern has no valid puzzles. I missed it. I must consider variant V3 again. Thank you for correction.
blue wrote:3. Two of your patterns are not maximal for the "2-empty-box" condition. P96 and P97 can be extended to maximal subsets of these 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 x |
+-------+-------+-------+     +-------+-------+-------+

P96 pattern is subset of (transposed) P73 pattern, P97 pattern is subset of P89 pattern. Both patterns (P96 and P97) are extra patterns, I missed them, thanks.
blue wrote:For those patterns, like the one discussed here (and one other), there are fairly easy proofs that they have no puzzles.

It's very interesting - please, publish these proofs.

Thank you for your help. I'll edit proper post to correct mistakes.

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

Re: Investigation of one-crossing-free patterns

Postby blue » Wed Mar 13, 2013 5:55 am

Hi Serg.

Thanks for the warm welcome.

Serg wrote:P96 pattern is subset of (transposed) P73 pattern, P97 pattern is subset of P89 pattern. Both patterns (P96 and P97) are extra patterns, I missed them, thanks.

Ahh, and I noticed P73 and P89, but missed the subset connections. Sorry,

Serg wrote:
blue wrote:For those patterns, like the one discussed here (and one other), there are fairly easy proofs that they have no puzzles.

It's very interesting - please, publish these proofs.

I'll work something up.
Would you like to see it in this topic, or somewhere else ?

Blue.
blue
 
Posts: 573
Joined: 11 March 2013

Re: Investigation of one-crossing-free patterns

Postby Serg » Wed Mar 13, 2013 12:25 pm

Hi, blue!
blue wrote:Would you like to see it in this topic, or somewhere else ?

I think such proofs meet this thread topic, so they can be published here.

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

Re: Investigation of one-crossing-free patterns

Postby blue » Wed Mar 13, 2013 8:53 pm

Here we go then ...

Proof(s) that these patterns have no puzzles:

On the left, is the pattern used in the proof(s), and on the right, a "nicer looking" version.

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

+-------+-------+-------+     +-------+-------+-------+
| . . x | . . . | . . . |     | x x x | . x . | x x x |
| . . x | . . . | . . . |     | x x x | . x . | x x x |
| . . x | x x x | x x x |     | x x x | . x . | x x x |
+-------+-------+-------+     +-------+-------+-------+
| . . x | x x x | x x x |     | . . . | . x . | . . . |
| . . x | x x x | x x x |     | x x x | . x . | x x x |
| . . x | x x x | x x x |     | . . . | . x . | . . . |
+-------+-------+-------+     +-------+-------+-------+
| . . x | x x x | x x x |     | x x x | . x . | x x x |
| . . x | x x x | x x x |     | x x x | . x . | x x x |
| x x x | x x x | x x x |     | x x x | x x x | x x x |
+-------+-------+-------+     +-------+-------+-------+

+-------+-------+-------+     +-------+-------+-------+
| . . . | . . . | . . x |     | x x x | . x . | x x x |
| . . . | . . . | . . x |     | x x x | . x . | x x x |
| . . x | x x x | x x x |     | x x x | . x . | x x x |
+-------+-------+-------+     +-------+-------+-------+
| . . x | x x x | x x x |     | . . . | . . . | . . x |
| . . x | x x x | x x x |     | x x x | . x . | x x x |
| . . x | x x x | x x x |     | . . . | . . . | . . x |
+-------+-------+-------+     +-------+-------+-------+
| . . x | x x x | x x x |     | x x x | . x . | x x x |
| . . x | x x x | x x x |     | x x x | . x . | x x x |
| x x x | x x x | x x x |     | x x x | x x x | x x x |
+-------+-------+-------+     +-------+-------+-------+

+-------+-------+-------+     +-------+-------+-------+
| . . . | . . . | . . . |     | x x x | . x . | x x x |
| . x . | . . . | . . . |     | x x x | . x . | x x x |
| . . x | x x x | x x x |     | x x x | . x . | x x x |
+-------+-------+-------+     +-------+-------+-------+
| . . x | x x x | x x x |     | . . . | . . . | . . . |
| . . x | x x x | x x x |     | x x x | . x . | x x x |
| . . x | x x x | x x x |     | . . . | . . x | . . . |
+-------+-------+-------+     +-------+-------+-------+
| . . x | x x x | x x x |     | x x x | . x . | x x x |
| . . x | x x x | x x x |     | x x x | . x . | x x x |
| . . x | x x x | x x x |     | x x x | . x . | x x x |
+-------+-------+-------+     +-------+-------+-------+


First, a review of facts about 2-row unavoidable sets:

Code: Select all
1. Any two rows in the same band, form an unavoidable set,
    since swapping them in a valid solution grid, always
    gives another valid solution grid.

2. Typically, the full two row UA sets are not minimal UA sets,
   and they can be partitioned into two or more minimal sets.

   Example:

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

     Splits into three sets (a UA8 a UA6, and a UA4):

     +-------+-------+-------+
     | 2 8 . | . 4 . | . 7 . |    4 numbers appearing two times each,
     | 7 4 . | . 2 . | . 8 . |    in 4 columns
     | . . . | . . . | . . . |
     +-------+-------+-------+

     +-------+-------+-------+
     | . . 5 | 1 . . | . . 6 |    3 numbers appearing two times each,
     | . . 1 | 6 . . | . . 5 |    in 3 columns
     | . . . | . . . | . . . |
     +-------+-------+-------+

     +-------+-------+-------+
     | . . . | . . 9 | 3 . . |    2 numbers appearing two times each,
     | . . . | . . 3 | 9 . . |    in 2 columns
     | . . . | . . . | . . . |
     +-------+-------+-------+

3. Each column in the row, belongs to a unique minimal UA set.
   To construct the set containing a particular column, we can
   start by including that column, and following "chain" of
   number and column links.
   In the example above, for the set that contains the (2 7)
   in column 1, we can follow it in either direction.
   For the "left to right" direction (call it), since the
   number 7 is included, we must also add the (7 8) in column 8.
   Then since the 8 has been included, we must add the (8 4)
   from column 2.
   Continuing in that manner, we'll eventually "close the loop".
   In this case, the next step closes the loop.
   Since the 4 has been included, we must add the (4 2) from column 5.
   At that point, the 2 is not "new", since it was in the starting
   column -- (2 7).
   After collecting the first UA set, like that, if we haven't
   used all 9 columns, we can collect a 2nd set, by starting
   with an unused column, and following the same procedure.
   When the 2nd set is collected, we can be sure that we will
   only collect columns that were "unused" after the first set
   was collected, since none of the numbers used in the first
   set, appear in the unused columns -- they appear in two
   columns only, and they were both used in the first set.
   If there are still columns remaining, we can collect a 3rd
   set, and so on.  [ A UA6 and 3 UA4's is possible. ]

4. Minimal UA18 sets, do exist.
   Example:

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


Then the proof(s):

Code: Select all
1. The thing to show: for each solution to a puzzle having one
   of the 4 patterns, the initially empty cells, must contain
   an unavoidable set.

2. For the initial part of the argument, we note that in each
   of the patterns, in rows 1 and 2, only one column contains
   clue cell(s).  If we partition rows 1 & 2, into 2-row UA
   sets, there are two cases to consider -- either we get one
   minimal UA18, or we get two or more minimal sets.  If it's
   the "two or more" case, then since only one column contains
   clue cells, one of the sets will contain only "initially
   empty" cells, and we can stop there.  In the other case,
   where rows 1 & 2 contain a minimal UA18, we can look at
   columns 1 & 2.  A similar argument applies there -- either
   we can find a small 2-column UA set, that's entirely within
   the empty cells, or columns 1 & 2 will contain a minimal UA18.

3. The case that we still need to handle, is when both rows 1 & 2,
   and columns 1 & 2, contain minimal UA18 sets.

4. When that's the case, we can split the UA18's into two
   "pieces" like this:

     An original UA18:

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

     The two pieces:

     "Type-A" piece: includes R1C1 and R2C2
     +-------+-------+-------+
     | 5 . 7 | 4 . 2 | 3 9 . |
     | . 3 2 | 7 . 9 | 4 5 . |    6 numbers, used twice each
     | . . . | . . . | . . . |
     +-------+-------+-------+

     "Type B" piece: includes R1C2 and R2C1
     +-------+-------+-------+
     | . 6 . | . 1 . | . . 8 |
     | 8 . . | . 6 . | . . 1 |    3 numbers, used twice each
     | . . . | . . . | . . . |
     +-------+-------+-------+

    To produce the pieces, there are two methods that work.
    Easy:  To collect the type-A piece above,  start with
      the (5 3) in (R1C1 R2C2); treat them as if they were
      in the same column, and follow the "usual" procedure
      discussed above.  What remains is the type-B piece.
    More direct:  Start with a column that isn't C1 or C2,
      Follow the "chain" of columns discussed above, in
      both directions, and stop with one cell only, when
      you enter C1 or C2.
      For example, with the (7 2) column as a starting
      point: follow the 2 to the (2 9) column, include it,
      and follow the 9 to the (9 5) column, and then follow
      the 5 to R1C1, and stop there.  Then work in the other
      direction from the starting column -- follow the 7 to
      the (4 7) column, the 4 to the (3 4) column, and the
      3 to R2C2.
      For this method, note: if following the chain one way,
      leads you to R1C1, then following it the other way,
      can only lead to R2C2, since 1) it can only lead to
      a cell in R2, and 2) if it lead to R2C1 instead, then
      you would have collected a 2-row UA set that didn't
      include C2, and that's impossible if the 2 rows
      contain a (minimal) UA18.

5. To continue with the example, here's a 2-column UA18 that
   is compatible with the 2-row UA18 above, and its breakdown.

      UA18         Type-A        Type-B
    +-------+     +-------+     +-------+
    | 5 6 . |     | 5 . . |     | . 6 . |
    | 8 3 . |     | . 3 . |     | 8 . . |
    | 9 1 . |     | 9 1 . |     | . . . |
    +-------+     +-------+     +-------+
    | 7 8 . |     | . . . |     | 7 8 . |
    | 3 2 . |     | 3 2 . |     | . . . |
    | 6 4 . |     | . . . |     | 6 4 . |
    +-------+     +-------+     +-------+
    | 2 9 . |     | 2 9 . |     | . . . |
    | 1 5 . |     | 1 5 . |     | . . . |
    | 4 7 . |     | . . . |     | 4 7 . |
    +-------+     +-------+     +-------+

6. To continue the proofs then, examining the 4 patterns, its easy
   to see that for any of the patterns, (exactly) one of the two
   row pieces, and (exactly) one of the two column pieces, will not
   include any clue cells.
   For the example UA18's, these are the combinations that "work":

    1st pattern: type-B 2-row, type-B 2-col
    2nd pattern: type-B 2-row, type-A 2-col
    3rd pattern: type-A 2-row, type-A 2-col
    4th pattern: type-B 2-row, type-B 2-col (it's always two type-B)

7. The final step is to note that the combinations actually
   do yield unavoidable sets.
   These "small UA set" examples should be convincing:

    Originals:

    +-------+-------+     +-------+-------+
    | . 1 . | 2 . . |     | 3 1 . | 2 . . |
    | 2 . . | 1 . . |     | 2 4 . | 1 . . |
    | . . . | . . . |     | . . . | . . . |
    +-------+-------+     +-------+-------+
    | 1 2 . |             | 4 3 . |
    | . . . |             | . . . |
    | . . . |             | . . . |
    +-------+             +-------+

    Alternates:

    +-------+-------+     +-------+-------+
    | . 2 . | 1 . . |     | 2 3 . | 1 . . |
    | 1 . . | 2 . . |     | 4 1 . | 2 . . |
    | . . . | . . . |     | . . . | . . . |
    +-------+-------+     +-------+-------+
    | 2 1 . |             | 3 4 . |
    | . . . |             | . . . |
    | . . . |             | . . . |
    +-------+             +-------+

    (same type)          (different types)

Edit: Swapped last two rows in step 5 UA sets, and fixed "working" combinations in step 6.

For kicks, here's a minimal UA28:

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


Cheers,
Blue.
Last edited by blue on Thu Mar 14, 2013 2:00 am, edited 1 time in total.
blue
 
Posts: 573
Joined: 11 March 2013

Re: Investigation of one-crossing-free patterns

Postby dobrichev » Wed Mar 13, 2013 11:46 pm

Hi Blue and welcome.

Do you mean that you checked all permutations of the 4 essentially different two-row minimal UA18 when they are composed in "L" shape and found that any of the permutations results in one of the non-two-row UA shown at the bottom of your post?
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: Investigation of one-crossing-free patterns

Postby blue » Thu Mar 14, 2013 2:01 am

dobrichev wrote:Hi Blue and welcome.

Do you mean that you checked all permutations of the 4 essentially different two-row minimal UA18 when they are composed in "L" shape and found that any of the permutations results in one of the non-two-row UA shown at the bottom of your post?

Hi Mladen, and thank you.

This was one of the (few) cases where detailed checking is not required.

If you can follow steps 4,5 & 6 in the "proof", I was trying to argue (maybe not so well), that such sets always exist, for any one of the 4 pattern shapes.
It won't be the same UA set, for each shape -- but for each shape, one of the "(A or B)-rows + (A or B cols)" combinations, will lie entirely within the initially empty cells.

I see I forgot to exchange a pair of rows in the "cols" UA18, and then messed up the A/B combinations that work for the 4 patterns. I've fixed that now (thank you !).

For the 2nd patterm, now, for example .. it's the "B-rows + A-cols" combination that works.
Code: Select all
+-------+-------+-------+     +-------+-------+-------+
| . 6 . | . 1 . | . . 8 |     | 5 . . | . . . | . . . |
| 8 . . | . 6 . | . . 1 |     | . 3 . | . . . | . . . |
| . . . | . . . | . . . |     | 9 1 . | . . . | . . . |
+-------+-------+-------+     +-------+-------+-------+
| . . . | . . . | . . . |     | . . . | . . . | . . . |
| . . . | . . . | . . . |  +  | 3 2 . | . . . | . . . |
| . . . | . . . | . . . |     | . . . | . . . | . . . |
+-------+-------+-------+     +-------+-------+-------+
| . . . | . . . | . . . |     | 2 9 . | . . . | . . . |
| . . . | . . . | . . . |     | 1 5 . | . . . | . . . |
| . . . | . . . | . . . |     | . . . | . . . | . . . |
+-------+-------+-------+     +-------+-------+-------+


      +-------+-------+-------+
      | 5 6 . | . 1 . | . . 8 |
      | 8 3 . | . 6 . | . . 1 |
      | 9 1 . | . . . | . . . |
      +-------+-------+-------+
      | . . . | . . . | . . . |
  ==  | 3 2 . | . . . | . . . |
      | . . . | . . . | . . . |
      +-------+-------+-------+
      | 2 9 . | . . . | . . . |
      | 1 5 . | . . . | . . . |
      | . . . | . . . | . . . |
      +-------+-------+-------+

-- doesn't overlap this:

      +-------+-------+-------+
      | . . x | . . . | . . . |
      | . . x | . . . | . . . |
      | . . x | x x x | x x x |
      +-------+-------+-------+
      | . . x | x x x | x x x |
      | . . x | x x x | x x x |
      | . . x | x x x | x x 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 » Thu Mar 14, 2013 4:35 pm

Hi, blue!
Interesting proof.

Maybe I missed something. But when we'll split 2-row minimal UA set to 2 pieces and split 2-column minimal UA set to 2 pieces (the case when both r1/r2 rows and c1/c2 columns contain minimal UA18 sets), we'll obtain 2 independent UA (let call them "rows+columns" UA sets) - the first UA contains r1c1 and r2c2 (plus one 2-row piece and one 2-column piece), the second (complementary) UA must contain r1c2 and r2c1 (plus another 2-row piece and another 2-column piece). So, 2 UA sets must be destroyed by 2 clue fragments (the first fragment contains 2 cells occupying the same column, the second fragment contains 2 cells occupying the same row). We would be lucky if both clue fragment hit the same "rows+columns" UA set. But what will be the case if each clue fragment hits its own "rows+columns" UA set? I think you should show that it is impossible.

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

PreviousNext

Return to General