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

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
`. . .. . xx 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 01 9 90 9 9`
(A > 0).

Continuation follows ...

Serg
Serg
2018 Supporter

Posts: 719
Joined: 01 June 2010
Location: Russia

### Re: Investigation of one-crossing-free patterns

Hi, I continue.
Now it is the turn to analyze 3-clue configurations 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
`         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 0C 9 90 9 9`
A > 0, B > 0, C > 0).

Continuation follows ...

Serg
Serg
2018 Supporter

Posts: 719
Joined: 01 June 2010
Location: Russia

### Re: Investigation of one-crossing-free patterns

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

Posts: 719
Joined: 01 June 2010
Location: Russia

### Re: Investigation of one-crossing-free patterns

Hi, I continue.
I'll study patterns having next 3-clue configuration in B1 box.
Code: Select all
`. . .. . xx 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
2018 Supporter

Posts: 719
Joined: 01 June 2010
Location: Russia

### Re: Investigation of one-crossing-free patterns

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

Posts: 719
Joined: 01 June 2010
Location: Russia

### Re: Investigation of one-crossing-free patterns

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
`  V2A B 0C 9 90 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
2018 Supporter

Posts: 719
Joined: 01 June 2010
Location: Russia

### Re: Investigation of one-crossing-free patterns

Hi!
Let's consider variant V3 of patterns containing 2 empty boxes, i.e. patterns having map
Code: Select all
`  V30 0 AB 9 9C 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
2018 Supporter

Posts: 719
Joined: 01 June 2010
Location: Russia

### Re: Investigation of one-crossing-free patterns

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: 894
Joined: 11 March 2013

### Re: Investigation of one-crossing-free patterns

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

Posts: 719
Joined: 01 June 2010
Location: Russia

### Re: Investigation of one-crossing-free patterns

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: 894
Joined: 11 March 2013

### Re: Investigation of one-crossing-free patterns

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

Posts: 719
Joined: 01 June 2010
Location: Russia

### Re: Investigation of one-crossing-free patterns

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: 894
Joined: 11 March 2013

### Re: Investigation of one-crossing-free patterns

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: 1791
Joined: 24 May 2010

### Re: Investigation of one-crossing-free patterns

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?

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: 894
Joined: 11 March 2013

### Re: Investigation of one-crossing-free patterns

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

Posts: 719
Joined: 01 June 2010
Location: Russia

PreviousNext