Investigation of one-crossing-free patterns

Everything about Sudoku that doesn't fit in one of the other sections

Investigation of one-crossing-free patterns

Postby 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
Last edited by Serg on Thu Feb 14, 2013 5:24 pm, edited 1 time in total.
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby 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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8023
Joined: 15 May 2006
Location: Berlin

Re: Investigation of one-crossing-free patterns

Postby 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
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby 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.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8023
Joined: 15 May 2006
Location: Berlin

Re: Investigation of one-crossing-free patterns

Postby 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
coloin
 
Posts: 1547
Joined: 05 May 2005

Re: Investigation of one-crossing-free patterns

Postby 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
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby 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
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby 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).]
Last edited by Serg on Tue Feb 19, 2013 11:33 am, edited 2 times in total.
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby 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
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby 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.]
Last edited by Serg on Tue Feb 19, 2013 11:34 am, edited 2 times in total.
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby 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.]
Last edited by Serg on Fri Feb 22, 2013 3:26 pm, edited 2 times in total.
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby 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
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby 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.]
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby 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
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby 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.]
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

Next

Return to General