The New Sudoku Players' Forum

by **Serg** » Thu Feb 14, 2013 9:13 am

Hi, people!
I've wrote a program which performs exhaustive search for any pattern of certain type, i.e. for patterns having map

Code: Select all: A B C D 9 9 E 9 9

A, B, C, D, E, F - arbitrary digits in the range 0-9. In other words, I consider patterns having exactly 9 clues in B5, B6, B8, B9 boxes and arbitrary number of clues in remaining boxes (B1, B2, B3, B4, B7).

Though this program is intermediate result of my work only (I am planning to write a program searching any given pattern for valid puzzles), I decided to test it in one-crossing-free patterns investigation. I think searching results can be interesting to sudoku people. "Crossing" is combination of one band and one stack. For example, set of boxes B1, B2, B3, B4, B7 is crossing. Conceptually this investigation follows my previous Investigation of one-band-free patterns. Previously I fixed 6 boxes and changed 3 ("free") boxes. Now I'll try to fix 4 boxes only and keep 5 boxes free. I think, such investigation results can be used during 16/17/18-clue patterns exhaustive search projects.

Here is an example of pattern with free crossing - my favorite Magic Pattern:

Code: Select all: +-----+-----+-----+ |. . .|. . x|. . x| |. . .|. . x|. . x| |. . x|. . x|. . x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |x x x|x x x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |x x x|x x x|x x x| +-----+-----+-----+

Let's consider first patterns having 4 empty boxes (maximal possible empty boxes for valid puzzles). The only possible map (having 1 free crossing) for valid puzzles is

Code: Select all: A 0 0 0 9 9 0 9 9

Let's consider all possible configurations of filled cells in the box B1, denoted by letter "A". There are 36 essentially different box patterns (rows/columns permutations are allowed, but transposing isn't allowed).

Code: Select all: . . . 0 filled cells . . . . . . . . . 1 filled cells . . . . . x . . . . . . . . . 2 filled cells . . x . . . . . x . x . . x x . . x . . . . . . . . x . . . . . x . . x 3 filled cells . . x . . . . . x . . x . . x . x . . x x x x x . . x x x . . x . x . . . . x . . . . . x . . . . . x . . . . . x 4 filled cells . . x . . x . . x . x x . x . . x x . x . x x . x x x . x x x . x . x x . x x x . x ************************************* . . x . . . . . x * . . x . . x . . x . . x 5 filled cells . . x . x x . x x * . x x . x . x x . . x x x x x x x x . x x * x . x x x x x x . x x . **************************************** . . x . . . . x x . x x . . x . x x 6 filled cells . x x x x x . x x . x x x x . x . x x x x x x x . x x x . x x x x x x . . x x . . x . x x 7 filled cells x . x x x x . x x x x x x x x x x x . x x 8 filled cells x x x x x x x x x 9 filled cells x x x x x x

It turns out, B1 box patterns placed upper asterisk line have no valid puzzles, but B1 box patterns placed lower asterisk line have valid puzzles.
In other words, there are following requirements to B1 box configuration if we want a pattern

Code: Select all: A 0 0 0 9 9 0 9 9

could have valid puzzles:
1. B1 box must contain not less than 5 clues.
2. Patterns posted below (containing 5 clues each in B1) have no valid puzzles.
3. If B1 box contains 6 or more clues, pattern has valid puzzles.

Code: Select all: Patterns having no valid puzzles: P1 P2 P3 +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . x|. . .|. . .| |. . .|. . .|. . .| |. . x|. . .|. . .| |. . x|. . .|. . .| |. x x|. . .|. . .| |. x x|. . .|. . .| |x x x|. . .|. . .| |x x x|. . .|. . .| |. x x|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+

You can see patterns P2 and P3 are isomorphic.

Above result can be formulated in another form. If any pattern can be morphed to subset of following patterns, the pattern has no valid puzzles.

Code: Select all: Patterns having no valid puzzles: P1 P2 P4 +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . x|. . .|. . .| |. . .|. . .|. . .| |. . x|. . .|. . .| |. . x|. . .|. . .| |. x x|. . .|. . .| |. x .|. . .|. . .| |x x x|. . .|. . .| |x x x|. . .|. . .| |x . x|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|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 **m_b_metcalf** » Thu Feb 14, 2013 10:22 am

Serg,
This happily confirms a result we obtained here (and modified here).

Regards,

Mike Metcalf

by **Serg** » Thu Feb 14, 2013 10:46 am

Hi, Mike!

m_b_metcalf wrote:This happily confirms a result we obtained here (and modified here).

Thank you for your links (I can't see the last link because of setbb.com "country restrictions"). Did you do exhaustive search? (I did.)
I am glad to see confirmation of my result. (Published above my data is just starting point for my investigation.)

Serg

by **m_b_metcalf** » Thu Feb 14, 2013 11:01 am

Serg wrote:Did you do exhaustive search? (I did.)

No, that's why I'm glad to see our empirical result confirmed.

Regards,

Mike Metcalf

P.S. The second link merely shows a minimal version of the puzzle.

by **coloin** » Thu Feb 14, 2013 6:51 pm

well it might be useful in excluding patterns in these puzzles

good luck with furthur proofs !

just to confirm
this pattern doesnt have 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| +-----+-----+-----+

and also ...... you don't explain why transposing [i assume reflection about a diagonal] isn't allowed

C

by **Serg** » Fri Feb 15, 2013 7:51 am

Hi, coloin!

coloin wrote:well it might be useful in excluding patterns in these puzzles
good luck with furthur proofs !

Thanks. Yes, published exclusive patterns having no valid puzzles can be used to reduce search space for 9plus12 game. But their exclusive potential is not high. I hope to go further to patterns having less empty boxes - they can be more useful. I have a dream to find another Magic Pattern which is extremely useful in excluding invalid patterns (patterns having no valid puzzles).

coloin wrote:just to confirm
this pattern doesnt have 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| +-----+-----+-----+

This is Magic Pattern. Its more common view is posted below.

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

It was discussed in 2007 (see thread Ask for some patterns that they don't have puzzles). Red Ed proved, that this pattern has no valid puzzles. I checked this pattern by my program (to cross-check it) - this pattern really has no valid puzzles (1 hour CPU burning).

coloin wrote:and also ...... you don't explain why transposing [i assume reflection about a diagonal] isn't allowed

I mean possible clue configuration in alone box. When pattern has no diagonal symmetry, we should consider 36 possible box configurations, but when a pattern has diagonal symmetry, we can shorten number of box configuration to 26 (by exclusion symmetric configurations) for diagonal boxes B1, B5, B9. "36 possible box configurations" classification is more universal, so it can be used when boxes' transposing is permitted and when it doesn't permitted.

Serg

by **Serg** » Fri Feb 15, 2013 10:51 pm

Hi, all!
We considered the case when 4 boxes of the crossing are empty, and only 1 box of the crossing contains clues. Now let's consider more complicated case - 2 boxes contain clues and 3 boxes are empty. There exist 3 essentially different types of patterns having 3 empty boxes in the crossing B1+B2+B3+B4+B7 (here are their maps):

Code: Select all: M1 M2 M3 A B 0 0 A B 0 0 A 0 9 9 0 9 9 0 9 9 0 9 9 0 9 9 B 9 9

(A > 0, B > 0). You can see that patterns with maps M2 and M3 have no valid puzzles for arbitrary A&B values. So, we should consider M1 map only (B3, B4, B7 boxes are empty, B1 and B2 boxes contain clues).

Let's start with B = 1, i.e. consider map

Code: Select all: M1 A 1 0 0 9 9 0 9 9

B1 box can have 36 possible configurations (more precisely - 35, because A > 0). Let's build "validity diagram" for this map containing 36 cells - one cell per possible B1 box configuration. I'll mark proper cell by "+", if all resulting patterns have valid puzzles, by "-", if all resulting patterns have no valid puzzles, by "?", if it is unknown - do resulting patterns have valid puzzles or no, by "*", if some resulting patterns have valid puzzles, but others have no valid puzzles (mixed validity).
Starting position is (left digits denote numbers of clues in B1 box):

Code: Select all: 0 ? 1 ? 2 ??? 3 ?????? 4 ??????? 5 ??????? 6 ?????? 7 ??? 8 ? 9 ?

If B1 box contains clues configuration

Code: Select all: . . x . . x x x x

resulting pattern has no valid puzzles, because it is subset of the pattern

Code: Select all: +-----+-----+-----+ |. . x|x x x|x x x| |. . x|x x x|x x x| |x x x|x x x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+

having no valid puzzles (see thread Investigation of one-band-free patterns). So, we can mark by "-" cells of "validity diagram", corresponding to clues-in-the-box configurations which are subset of considered 5-clue configuration. For example, clues-in-the-box configuration

Code: Select all: . . . . . x x x x

is subset of

Code: Select all: . . x . . x x x x

configuration, hence second cell in the row "4" (see my first post in this thread) must be marked by "-". Accounting for all possible subsets considered 5-clue configuration, we'll come to this validity diagram:

Code: Select all: 0 - 1 - 2 --- 3 -----? 4 ---???? 5 -?????? 6 ?????? 7 ??? 8 ? 9 ?

If a pattern having crossing with 4 empty boxes has valid puzzles, that pattern will have valid puzzles too when we'll add 1 clue in any empty box. So, we can mark by "+" validity diagram cells, corresponding to 4-empty-boxes patterns, having valid puzzles. For example, pattern

Code: Select all: P5 +-----+-----+-----+ |. . x|. . .|. . .| |. x x|. . .|. . .| |x x x|. . .|. . .| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|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, hence patterns

Code: Select all: P6 P7 P8 +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . x|. . .|. . .| |. . x|. . .|. . .| |. . x|. . x|. . .| |. x x|. . .|. . .| |. x x|. . x|. . .| |. x x|. . .|. . .| |x x x|. . x|. . .| |x x x|. . .|. . .| |x x x|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+

will have valid puzzles too. So, we should mark by "+" validity diagram cells lying under asterisk line (see my first post in this thread). Validity diagram will look like this

Code: Select all: 0 - 1 - 2 --- 3 -----? 4 ---???? 5 -??++++ 6 ++++++ 7 +++ 8 + 9 +

We can mark by "-" last cell in "3" row, because pattern

Code: Select all: +-----+-----+-----+ |. . x|x x x|x x x| |. x .|x x x|x x x| |x . .|x x x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+

has no valid puzzles (see thread Investigation of one-band-free patterns).
Validity diagram:

Code: Select all: 0 - 1 - 2 --- 3 ------ 4 ---???? 5 -??++++ 6 ++++++ 7 +++ 8 + 9 +

Now we should investigate remaining patterns, having 5 clues in B1 box.

Code: Select all: P9 P10 P11 +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|. . .|. . .| |. . .|. . .|. . .| |. . .|. . x|. . .| |. x x|. . .|. . .| |. x x|. . x|. . .| |. x x|. . .|. . .| |x x x|. . x|. . .| |x x x|. . .|. . .| |x x x|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ P12 P13 +-----+-----+-----+ +-----+-----+-----+ |. . x|. . .|. . .| |. . x|. . x|. . .| |. x x|. . .|. . .| |. x x|. . .|. . .| |. x x|. . x|. . .| |. x x|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|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** » Sat Feb 16, 2013 12:04 pm

Hi!
I continue.
It turns out, pattern P9 has no valid puzzles.

Code: Select all: P9 +-----+-----+-----+ |. . .|. . .|. . .| |. x x|. . .|. . .| |x x x|. . x|. . .| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|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 P10 and P11 have valid puzzles. Patterns P12 and P13 have valid puzzles too. Here are examples.

Code: Select all: ......... .58..9... 976...... ...365789 ...892164 ...147325 ...924678 ...583912 ...671453 .....9... .87...... 956...... ...536879 ...297146 ...841532 ...984627 ...723951 ...165483 ..9...... .85...... .76..1... ...156897 ...489263 ...723514 ...672458 ...518932 ...934671 ..7..9... .86...... .95...... ...165789 ...497326 ...823145 ...584962 ...932571 ...716834

So, 2nd cell in "5" row of validity diagram must be marked by "*" (mixed configuration) and 3rd cell in "5" row of validity diagram must be marked by "+".

Code: Select all: 0 - 1 - 2 --- 3 ------ 4 ---???? 5 -*+++++ 6 ++++++ 7 +++ 8 + 9 +

Now we should investigate remaining patterns, having 4 clues in B1 box.

Code: Select all: P14 P15 +-----+-----+-----+ +-----+-----+-----+ |. . .|. . .|. . .| |. . .|. . x|. . .| |. x x|. . .|. . .| |. x x|. . .|. . .| |x . x|. . x|. . .| |x . x|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ P16 P17 +-----+-----+-----+ +-----+-----+-----+ |. . .|. . .|. . .| |. . .|. . x|. . .| |. x x|. . .|. . .| |. x x|. . .|. . .| |. x x|. . x|. . .| |. x x|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ P18 P19 P20 +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . x|. . .|. . .| |. . x|. . .|. . .| |. . x|. . x|. . .| |. x .|. . .|. . .| |. x .|. . x|. . .| |. x .|. . .|. . .| |x . x|. . x|. . .| |x . x|. . .|. . .| |x . x|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ P21 P22 +-----+-----+-----+ +-----+-----+-----+ |. . x|. . .|. . .| |. . x|. . x|. . .| |. x .|. . .|. . .| |. x .|. . .|. . .| |. x x|. . x|. . .| |. x x|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+

It turns out, that patterns P14-P17 have no valid puzzles, patterns P18-P22 have valid puzzles.
Here are examples.

Code: Select all: ..9...... .8....... 7.6..9... ...154698 ...896327 ...732145 ...568931 ...473862 ...921574 ..8...... .7...9... 9.6...... ...154687 ...826539 ...937412 ...492871 ...781365 ...563924 ..7..9... .8....... 9.6...... ...154897 ...697243 ...823165 ...976452 ...531978 ...482631 ..9...... .8....... .76..9... ...416897 ...798235 ...253614 ...961378 ...834562 ...572941 ..8..9... .7....... .69...... ...134786 ...578249 ...692351 ...827693 ...915824 ...463175

Now we can finish validity diagram markup.

Code: Select all: 0 - 1 - 2 --- 3 ------ 4 ----+-+ 5 -*+++++ 6 ++++++ 7 +++ 8 + 9 +

So, investigation of patterns

Code: Select all: M1 A 1 0 0 9 9 0 9 9

is finished. Patterns of such type have no valid puzzles if they can be morphed to subset of the following patterns. Otherwise they have 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 x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|. . x|. . .| |. . .|. . x|. . .| |. x x|. . .|. . .| |. x x|. . .|. . .| |x . x|. . .|. . .| |. x x|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|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 found a "gap" in my post - 2 possible configurations were not considered (patterns P21 and P22).]

by **Serg** » Sat Feb 16, 2013 10:10 pm

Hi!
Further I'll describe my investigation more briefly.
Using described above technique for finding patterns having no valid puzzles for map

Code: Select all: A 1 0 0 9 9 0 9 9

we shall come to ultimate validity diagram

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

It will be observed when we'll consider map

Code: Select all: A 4 0 0 9 9 0 9 9

Investigation of patterns having 3 empty boxes in a crossing, i.e. patterns having map

Code: Select all: A B 0 0 9 9 0 9 9

is finished. Patterns of such type have no valid puzzles if they can be morphed to subset of the following patterns. Otherwise they have 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 x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|. . x|. . .| |. . .|. . x|. . .| |. x x|. . x|. . .| |. x x|. . x|. . .| |x . x|. . x|. . .| |. x x|. . x|. . .| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|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** » Sun Feb 17, 2013 8:08 am

Hi!
It's time to study crossings having 2 empty boxes only.
There are 3 essentially different variants of placing remaining (non-empty) boxes denoted by A, B, C:

Code: Select all: V1 V2 V3 A B C A B 0 0 0 A 0 9 9 C 9 9 B 9 9 0 9 9 0 9 9 C 9 9

Let's consider variant V1 first.
Because stack B147 contains 2 empty boxes, we can start with position just after finish of map

Code: Select all: A 1 0 0 9 9 0 9 9

analysis. So, we have validity diagram

Code: Select all: 0 - 1 - 2 --- 3 ------ 4 ----+-+ 5 -*+++++ 6 ++++++ 7 +++ 8 + 9 +

and collection of patterns having 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 x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|. . x|. . .| |. . .|. . x|. . .| |. x x|. . .|. . .| |. x x|. . .|. . .| |x . x|. . .|. . .| |. x x|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+

at starting point. Let's consider simplest possible map

Code: Select all: A 1 1 0 9 9 0 9 9

We should add 1 clue to empty B3 box and check following patterns for having valid puzzles (other possible combinations definitely have valid puzzles):

Code: Select all: P23 P24 P25 +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|. . .|. . .| |. . .|. . .|. . .| |. . .|. . x|. . x| |. x x|. . .|. . .| |. x x|. . .|. . .| |. x x|. . .|. . .| |x x x|. . x|. . x| |x . x|. . x|. . x| |x . x|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ P26 P27 P28 +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|. . .|. . .| |. . .|. . .|. . x| |. . .|. . .|. . .| |. x x|. . .|. . x| |. x x|. . .|. . .| |. x x|. . .|. . .| |x . x|. . x|. . .| |x . x|. . x|. . .| |. x x|. . x|. . x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ P29 P30 P31 +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|. . x|. . x| |. . .|. . .|. . .| |. . .|. . .|. . x| |. x x|. . .|. . .| |. x x|. . .|. . x| |. x x|. . .|. . .| |. x x|. . .|. . .| |. x x|. . x|. . .| |. x x|. . x|. . .| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|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 an error in validity diagram.]

by **Serg** » Sun Feb 17, 2013 4:57 pm

Hi!
I continue.
It turns out, pattern P23 has no valid puzzles.

Code: Select all: P23 +-----+-----+-----+ |. . .|. . .|. . .| |. x x|. . .|. . .| |x x x|. . x|. . x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|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 P24 and P28 have no valid puzzles too, because they are subsets of the pattern P23. Remaining patterns (P25-P27 and P29-P31) have valid puzzles. Here are examples.

Code: Select all: .....9..7 .87...... 9.6...... ...536789 ...297416 ...841253 ...764928 ...923571 ...185634 ......... .96.....5 8.7..3... ...365789 ...187426 ...924351 ...672948 ...831572 ...549613 ........7 .96...... 8.7..3... ...365789 ...187426 ...924315 ...642978 ...871532 ...539641 .....9..7 .87...... .69...... ...536789 ...197254 ...284613 ...745928 ...863471 ...921536 ......... .69.....5 .87..3... ...365789 ...179452 ...824613 ...542978 ...687341 ...931526 ........7 .69...... .87..3... ...365789 ...179425 ...824631 ...587942 ...641378 ...932516

So, we have such validity diagram.

Code: Select all: 0 - 1 - 2 --- 3 ------ 4 ---*+*+ 5 -*+++++ 6 ++++++ 7 +++ 8 + 9 +

We should increase number of clues in B2, B3 boxes till configurations marked by "*" in validity diagram posted above will be changed by "+". If we want preserve property "no valid puzzles" after clues addition, clues cannot be placed in r1/r2 rows, because we'll come to patterns definetly having valid puzzles.

It turns out, pattern P32 has no valid puzzles.

Code: Select all: P32 +-----+-----+-----+ |. . .|. . .|. . .| |. x x|. . .|. . .| |x x x|x x x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+

This is ultimate configuration. Futher adding a clue to B2/B3 boxes will produce patterns having valid puzzles.

So, investigation of variant

Code: Select all: V1 A B C 0 9 9 0 9 9

(A > 0, B > 0, C > 0) is finished. Patterns of such type have no valid puzzles if they can be morphed to subset of the following patterns. Otherwise they have 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 x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|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 a typo.]

by **Serg** » Tue Feb 19, 2013 8:43 am

Hi!
It's time to consider variant 2 of arranging 3 non-empty boxes in a crossing:

Code: Select all: V2 A B 0 C 9 9 0 9 9

A good starting point will be family of patterns having maps

Code: Select all: A 1 0 0 9 9 0 9 9

If a pattern of this family has valid puzzles, the patterns having maps

Code: Select all: A X 0 Y 9 9 0 9 9

(X > 0, Y > 0) will have valid puzzles too.
Family of patterns

Code: Select all: A 1 0 0 9 9 0 9 9

has such validity diagram (see one of my previous posts):

Code: Select all: 0 - 1 - 2 --- 3 ------ 4 ----+-+ 5 -*+++++ 6 ++++++ 7 +++ 8 + 9 +

So, we are starting with such diagram (possible configurations of B1 box).

Code: Select all: . . . 0 filled cells . . . . . . . . . 1 filled cells . . . x . . . . . . . . . . . 2 filled cells . . x . . . . . x . x . . x x . . x . . . . . . . . x . . . . . x . . x 3 filled cells . . x . . . . . x . . x . . x . x . . x x x x x . . x x x . . x . x . . ********* *********** . . x . . . . . x . . . * . . x * . . . * . . x 4 filled cells . . x . . x . . x . x x * . x . * . x x * . x . x x . x x x . x x x . x * . x x * . x x * x . x ***************** ********* . . x . . . * . . x . . x . . x . . x . . x 5 filled cells . . x . x x * . x x . x x . x . x x . . x x x x x x x x * . x x x . x x x x x x . x x . ******************************** . . x . . . . x x . x x . . x . x x 6 filled cells . x x x x x . x x . x x x x . x . x x x x x x x . x x x . x x x x x x . . x x . . x . x x 7 filled cells x . x x x x . x x x x x x x x x x x . x x 8 filled cells x x x x x x x x x 9 filled cells x x x x x x

If B1 box configuration is placed under asterisk line, pattern has valid puzzles, but if it is placed above asterisk line, we don't know has pattern valid puzzles or no. Starting validity diagram:

Code: Select all: 0 ? 1 ? 2 ??? 3 ?????? 4 ????+?+ 5 ??+++++ 6 ++++++ 7 +++ 8 + 9 +

Let's begin with simplest map:

Code: Select all: A 1 0 1 9 9 0 9 9

In this case we can state that if B1 box configuration is marked by "+" in validity diagram, its "conjugate" (transposed) configuration must be marked by "+" too. So, we have such validity diagram (2 additional configurations are marked by "+"):

Code: Select all: 0 ? 1 ? 2 ??? 3 ?????? 4 ???++?+ 5 ?++++++ 6 ++++++ 7 +++ 8 + 9 +

Continuation follows ...

Serg

by **Serg** » Thu Feb 21, 2013 7:02 am

Well, I continue.
I am studying patterns having maps

Code: Select all: A B 0 C 9 9 0 9 9

(A > 0, B > 0, C > 0). There exists only one variant of B1 box filling by 5 (or more) clues to get a pattern having no valid puzzles (see my previous post):

Code: Select all: . . x . . x x x x

Let's consider this case in more details. If B=1 and C=1, then there will be 3 essentially different variants of such patterns:

Code: Select all: P33 P34 P35 +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . x|. . .|. . .| |. . x|. . .|. . .| |. . x|. . .|. . .| |. . x|. . .|. . .| |. . x|. . .|. . .| |. . x|. . x|. . .| |x x x|. . x|. . .| |x x x|. . x|. . .| |x x x|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . x|x x x|x x x| |. x .|x x x|x x x| |. x .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+

It turns out, that pattern P33 has no valid puzzles, but patterns P34 and P35 have valid puzzles. So, if we'll consider general case with B > 1 and C > 1, we'll see that patterns have valid puzzles when B2 box contains clues in r1/r2 rows OR B4 box contains clues in c1/c2 columns. Patterns can have no valid puzzles when B2 box contains clues in r3 row only AND B4 box contains clues in c3 column only. It turns out, that next pattern has no valid puzzles.

Code: Select all: P36 +-----+-----+-----+ |. . x|. . .|. . .| |. . x|. . .|. . .| |x x x|x x x|. . .| +-----+-----+-----+ |. . x|x x x|x x x| |. . x|x x x|x x x| |. . x|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, when B1 box contains clue configuration

Code: Select all: . . x . . x x x x

patterns will have no valid puzzles if they can be morphed to P36 pattern subset, otherwise they will have valid patterns.
(Patterns having maps

Code: Select all: A B 0 C 9 9 0 9 9

are considered now.)

Continuation follows ...

Serg

[Edited. I corrected a typo.]

by **Serg** » Fri Feb 22, 2013 7:29 am

Hi, I continue.
I am studying patterns having maps

Code: Select all: A B 0 C 9 9 0 9 9

(A > 0, B > 0, C > 0). Now it's time to study patterns having 4 clues in B1 box. Let's start with B1 box configuration

Code: Select all: . . x . . x x x .

If B=1 and C=1, then there will be 3 essentially different variants of such patterns:

Code: Select all: P37 P38 P39 +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . x|. . .|. . .| |. . x|. . .|. . .| |. . x|. . .|. . .| |. . x|. . .|. . .| |. . x|. . .|. . .| |. . x|. . x|. . .| |x x .|. . x|. . .| |x x .|. . x|. . .| |x x .|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . x|x x x|x x x| |. x .|x x x|x x x| |. x .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|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 P37 has no valid puzzles, because it is subset of P36 pattern (see previous post). Search shows the patterns P38 and P39 have valid puzzles. So, if we'll consider general case with B > 1 and C > 1, we'll see that patterns have valid puzzles when B2 box contains clues in r1/r2 rows OR B4 box contains clues in c1/c2 columns. Patterns can have no valid puzzles when B2 box contains clues in r3 row only AND B4 box contains clues in r3 column only. Ultimate pattern

Code: Select all: P40 +-----+-----+-----+ |. . x|. . .|. . .| |. . x|. . .|. . .| |x x .|x x x|. . .| +-----+-----+-----+ |. . x|x x x|x x x| |. . x|x x x|x x x| |. . x|x x x|x x x| +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+

is subset of P36 pattern, so it has no valid puzzles. Therefore B1 box configuration considered cannot add something new to general case (patterns having maps

Code: Select all: A B 0 C 9 9 0 9 9

A > 0, B > 0, C > 0).

Continuation follows ...

Serg

by **Serg** » Fri Feb 22, 2013 11:07 pm

Hi, I continue.
I'll study patterns having next 4-clue configuration in B1 box.

Code: Select all: . . . . . x x x x

There are 6 essentially different variants of such patterns, having 1 clue in B2 and B4 boxes:

Code: Select all: P41 P42 P43 +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|. . .|. . .| |. . .|. . .|. . .| |. . .|. . .|. . .| |. . x|. . .|. . .| |. . x|. . .|. . .| |. . x|. . x|. . .| |x x x|. . x|. . .| |x x x|. . x|. . .| |x x x|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . x|x x x|x x x| |. x .|x x x|x x x| |. . x|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ P44 P45 P46 +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|. . .|. . .| |. . .|. . x|. . .| |. . .|. . x|. . .| |. . x|. . x|. . .| |. . x|. . .|. . .| |. . x|. . .|. . .| |x x x|. . .|. . .| |x x x|. . .|. . .| |x x x|. . .|. . .| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. x .|x x x|x x x| |. . x|x x x|x x x| |. x .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|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 P41 has no valid puzzles, because it is subset of P36 pattern (see previous posts). Search shows the pattern P42 has no valid puzzles too, but patterns P43-P46 have valid puzzles. BTW, pattern P42 is the search duration champion - it took my program almost 4 hours to do exhaustive search for this pattern. Next 2 patterns

Code: Select all: P47 P48 +-----+-----+-----+ +-----+-----+-----+ |. . .|. . .|. . .| |. . .|. . .|. . .| |. . x|. . .|. . .| |. . x|. . .|. . .| |x x x|. . x|. . .| |x x x|. . x|. . .| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . x|x x x|x x x| |. x .|x x x|x x x| |. x .|x x x|x x x| |x . .|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|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: P49 P50 +-----+-----+-----+ +-----+-----+-----+ |. . .|. . .|. . .| |. . .|. . .|. . .| |. . x|. . .|. . .| |. . x|. . .|. . .| |x x x|. . x|. . .| |x x x|. . x|. . .| +-----+-----+-----+ +-----+-----+-----+ |. . x|x x x|x x x| |. . .|x x x|x x x| |. . x|x x x|x x x| |. . .|x x x|x x x| |. . x|x x x|x x x| |x x x|x x x|x x x| +-----+-----+-----+ +-----+-----+-----+ |. . .|x x x|x x x| |. . .|x x x|x x x| |. . .|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: P51 +-----+-----+-----+ |. . .|. . .|. . .| |. . x|. . .|. . .| |x x x|. . x|. . .| +-----+-----+-----+ |. x .|x x x|x x x| |. x .|x x x|x x x| |. x .|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: P52 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| +-----+-----+-----+ +-----+-----+-----+

P52 pattern is subset of P36 pattern, so it is not interesting. But P53 is new pattern having no valid puzzles in 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

[Edited. I missed a pattern (P51) - corrected.]

The New Sudoku Players' Forum

Investigation of one-crossing-free patterns

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