The New Sudoku Players' Forum

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

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

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

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

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

by **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.]

by **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.]

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

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

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

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

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

by **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?

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

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

The New Sudoku Players' Forum

Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns