Investigation of one-crossing-free patterns

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Wed Mar 20, 2013 1:10 pm

Hi, coloin!
coloin wrote:Actually i cant see anywhere [in his posts] that Serg has made maximal his "magic pattern" to
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|
+-----+-----+-----+


I haven't consider such class of patterns yet. To my classification, this is "variant 2 of patterns containing one empty box". Now I study "variant 1 of patterns containing one empty box" (and hope to post results coming days). Then I'll study "variant 2 of patterns containing one empty box", finally I'll study "patterns containing no empty boxes".
coloin wrote:I will have a look at those one clue boxes ..... looks like there are only 6 ED patterns.
But as you have found one valid pattern it probably is less of significance ....

"One clue boxes" pattern cited doesn't fit your pattern. blue done great work finding valid puzzle for some variant of your pattern and proving some other variants don't have valid puzzles. I think nobody can do more in this case.

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

Re: Investigation of one-crossing-free patterns

Postby blue » Fri Mar 22, 2013 9:29 am

Hi Colin,

coloin wrote:I will have a look at those one clue boxes ..... looks like there are only 6 ED patterns.
But as you have found one valid pattern it probably is less of significance ....

I looks as though I misunderstood your original post -- specifically, where you said:
maybe the solitary clue can be anywhere in Boxes 1379

Are these the "6 ED patterns" you had in mind ?
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 | . . .


I've found puzzles for the last 4. (You've already seen the 1st one).
Code: Select all
3 . . | 6 . 8 | . . 2     . . . | 3 . 1 | . . 4
. . . | 1 . 9 | . . .     . 9 . | 8 . 2 | . . .
. . . | 5 . 3 | . . .     . . . | 5 . 9 | . . .
------+-------+------     ------+-------+------
2 9 5 | 7 6 1 | 4 3 8     1 5 8 | 6 2 3 | 4 9 7
. . . | 4 9 5 | . . .     . . . | 1 9 4 | . . .
6 4 1 | 3 8 2 | 5 9 7     4 2 9 | 7 8 5 | 6 1 3
------+-------+------     ------+-------+------
. . . | 2 . 7 | . . .     . . . | 2 . 6 | . . .
. . . | 9 . 6 | . 5 .     . . . | 9 . 8 | . 5 .
7 . . | 8 . 4 | . . .     3 . . | 4 . 7 | . . .

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

3..6.8..2...1.9......5.3...295761438...495...641382597...2.7......9.6.5.7..8.4...
...3.1..4.9.8.2......5.9...158623497...194...429785613...2.6......9.8.5.3..4.7...
.6.2.4..8...3.5......1.7...587649312...851...641723859...9.6......4.8...1..5.2.3.
.6.1.2..3...8.4......5.7...325719846...258...978346152...6.5......4.1.8.2..9.3...


The first two don't have puzzles.
I managed to come up with a good trick to do the testing in a reasonable amount of time.
The first one took ~2.5 hours, and the 2nd one, about 16 times that.
They are also "maximal no-puzzle patterns" -- "magic patterns" !

Below are diagrams showing a set of ED positions for "one extra given" for them, and a puzzle for each option.

Code: Select all
   (magic pattern)
x . . | x . x | . . x     x , . | x . x | . . x
. . . | x . x | . . .     . , . | x . x | . . .
. . . | x . x | . . .     . . . | x . x | . . .
------+-------+------     ------+-------+------
x x x | x x x | x x x     x x x | x x x | x x x
. . . | x x x | . . .     . . . | x x x | . c c
x x x | x x x | x x x     x x x | x x x | x x x
------+-------+------     ------+-------+------
. . . | x . x | . . .     . . . | x . x | . .
. . . | x . x | . . .     . . . | x . x | . c c.
x . . | x . x | . . x     x . . | x . x | . . x

8..2.9..1...4.5......3.7...739854126...936...645172389...5.3......6.1..72..7.8..4
3..6.8..2...5.3......1.9...295761438...495...641382597...2.7......9.6.5.7..8.4..3
3..7.8..1...2.5......6.9...142397658...451..9759826413...1.2......5.4...8..9.3..6
6..1.8..9...5.3......2.7...934625871...974.2.572831496...7.9......4.2...1..3.6..5


Code: Select all
   (magic pattern)
x . . | x . x | . . x     x , . | x c x | . c x
. . . | x . x | . . .     . , . | x c x | . c c
. . . | x . x | . . .     . . . | x . x | . . .
------+-------+------     ------+-------+------
x x x | x x x | x x x     x x x | x x x | x x x
. . . | x x x | . . .     . . . | x x x | . c c
x x x | x x x | x x x     x x x | x x x | x x x
------+-------+------     ------+-------+------
. . . | x . x | . . .     . . . | x c x | . c c
. . . | x . x | . . x     . . . | x c x | . c x
x . . | x . x | . . .     x . . | x . x | . c c

8..2.9..1...4.5......3.7...739854126...936...645172389...5.3......6.1..72..7.8..4 - c9
8..7.1..9...5.6......2.4...458129637...648...196357842...8.2..5...9.5..62..4.3...
3..2.7..5...9.3......1.4...789516423...478.9.614329578...8.1......6.5..19..7.2...
5..6.8..2...9.2..6...7.5...234591678...483...891267453...8.4......1.9..47..3.6...

1..6.2..3...7.8......5.9...632157894...924...495386172...4.3......2.5..97..8.1.5. - c8
6..2.5..7...7.8......4.1...917352486...184...843976215...8.9......5.7.435..6.3...
7..8.5..2...9.7......3.2...186574923...629...429138675...2.1.9....4.3..83..7.6...
8..7.1..2...3.9......6.4...295168437...593.6.613472895...9.5......2.7..94..8.6...
9..8.5..6...2.3.9....1.7...146528379...314...523679184...7.1......4.2..37..9.6...
1..9.6.34...3.7......8.5...673451829...732...421689357...5.3......2.8..67..1.4...

2..9.7..6...4.1......5.6...936174582...859...857362149...6.3......298..31..7.5... - c5
1..8.4..5...6.7......2.9...589321674...975...327468591...792......1.3..64..5.6...
7..4.9..5...261......5.3...143925867...614...596738214...1.2......3.6..92..8.7...
8..976..3...5.8......1.3...941635278...214...632789145...4.2......8.1..65..3.7...


"Good call" on your part :!:

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Fri Mar 22, 2013 4:20 pm

Hi!
Congratulations to blue! Excellent work (and surprisingly fast)! So, we got to know 2 new maximal patterns! Unfortunately I cannot confirm both patterns have no valid puzzles (my searching program processes only "one-free-crossing" patterns yet).

Congratulations to coloin too! In what way did you invented such non-trivial and fruitful shape?

I feel it's time to collect and publish all known maximal patterns (about 30 patterns).

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

Re: Investigation of one-crossing-free patterns

Postby coloin » Fri Mar 22, 2013 9:55 pm

Thanks blue for doing that - curious that only 2 of the 6 Ed ways with one clue in each of B1379 dont have puzzles.
The pattern came from years back - and i suppose i lacked the back up of you programmers
from here

any pattern with a large number of clues - if a puzzle isnt found straight away - its likely to be without puzzles
proving it is another matter ..... well done.

the follow on thread surely will be more definitive.

C
coloin
 
Posts: 1629
Joined: 05 May 2005

Re: Investigation of one-crossing-free patterns

Postby Serg » Tue Apr 09, 2013 6:37 am

Hi!
I wasn't able to consider manually all possible configurations having 1 empty box in a crossing. Too many variants to process. So, I am planning to write searching program to do it. BTW I implemented check for "two-row plus two-column UA of mixed type (A-row + B-cols and vice versa)" - blue's discovery posted in this thread. The technique works well, increasing number of rejected configurations up to 2 times (depending on clues configuration in B1 box), especially well for "sparse" B1 box (having 0 or 1 clues). That additional rejection of "false" configurations accelerates overall search up to 4 times (practically observed).

So, I need 2-3 weeks to write new searching program (or to invent new algorithm allowing manual analysis of the problem).

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Thu May 09, 2013 10:40 pm

Hi, people!
I've done at last search for patterns not having valid puzzles for the "variant 1 of patterns containing one empty box", i.e. I've checked patterns containing exactly 1 empty box which is placed at "periphery" (B7 empty box). Here are 20 possible such patterns.
Code: Select all
Patterns having no valid puzzles:

        P101                       P102                       P103
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . x|. . .|. . .|        |. . .|. . .|. . .|        |. . .|. . .|. . x|
|. . x|. . .|. . .|        |. . x|. . .|. . .|        |. . .|. . .|. . x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . x|x x x|x x x|        |. . .|x x x|x x x|        |. . x|x x x|x x x|
|. . x|x x x|x x x|        |. . .|x x x|x x x|        |. . x|x x x|x x x|
|. . x|x x x|x x x|        |x x x|x x x|x x x|        |. . x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P104                       P105                       P106
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . x|        |. . x|. . .|. . .|        |. . x|. . x|. . x|
|. . .|. . .|. . x|        |. . x|. . .|. . .|        |. . x|. . x|. . x|
|x x x|x x x|x x x|        |. . x|x x x|x x x|        |. . x|. . x|. . x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . x|x x x|x x x|        |. . x|x x x|x x x|
|x x x|x x x|x x x|        |. . x|x x x|x x x|        |. . x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P107                       P108                       P109
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . x|. . x|        |. . .|. . .|. . .|
|. . x|. . .|. . .|        |. . x|. . .|. . .|        |. . .|. . x|. . x|
|. x .|x x x|x x x|        |. x .|. . .|. . .|        |. x x|. . .|. . .|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. x .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. x .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. x .|x x x|x x x|        |x . .|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P110                       P111                       P112
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . x|x x x|        |. . .|. . .|. x x|        |. . .|. . .|. . x|
|. . .|. . x|x x x|        |. . .|. . .|. x x|        |. . .|x x x|x x x|
|. . x|. . x|x x x|        |. . x|x x x|x x x|        |. . x|. . .|. . x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. x .|x x x|x x x|        |. x .|x x x|x x x|        |. x .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P113                       P114                       P115
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . x|. . x|        |. . .|. x x|. x x|        |. . .|. . .|. . .|
|. . .|. . x|. . x|        |. . .|. x x|. x x|        |. . .|. . .|. x x|
|. . x|x x x|x x x|        |. . x|. x x|. x x|        |. . x|. . x|. . .|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . x|x x x|x x x|
|. x .|x x x|x x x|        |. x .|x x x|x x x|        |. x .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P116                       P117                       P118
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . x|. . x|        |. . .|. . x|. . x|
|. . .|. . .|. x x|        |. . .|. . x|. . x|        |. . .|. . x|. . x|
|. . x|. . x|. . .|        |. . x|. . x|. . x|        |. . x|. . x|. . x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. x .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. x .|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |. x .|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P119                       P120
+-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . .|. . x|
|. . .|x x x|x x x|        |. . .|. . .|. . x|
|. . x|. . .|. . .|        |. . x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . x|x x x|x x x|
|x x x|x x x|x x x|        |. . x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+

Serg
[Edited: I added pattern P120 missing in original post. Thanks to Blue for this correction.]
[Edited: I changed terminogy - some published above patterns are not maximal in the strict sense, i.e. they can be extended by adding clues in B7 box.]
Last edited by Serg on Mon May 13, 2013 10:41 am, edited 2 times in total.
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby blue » Fri May 10, 2013 8:25 pm

Hi Serg,

Well done !
I can confirm that they don't have puzzles.

It looks like you forgot to include one.
(I'm sure you have it).

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

It isn't a subset of one of the others is it ?
(It isn't maximal).

Except for that one, your list matches mine.
Thank you for the confirmations.

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Sun May 12, 2013 7:09 am

Hi, Blue!
Thank you for confirmation of my results.
blue wrote:Hi Serg,
It looks like you forgot to include one.
(I'm sure you have it).

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

It isn't a subset of one of the others is it ?
(It isn't maximal).

I missed this pattern. Patterns P101, P103, P105 and P107 were produced "artificially", by hand, from already published 4 maximal patterns which were proven by you not to have valid puzzles, so I can be wrong. But remaining patterns were produced by true exhaustive search (and cross-checks), so I am sure there are no other patterns not having valid puzzles with empty B7 box and filled boxes B5, B6, B8 and B9. Maybe it would be better to publish true maximal patterns only, because at the end of this investigation maximal patterns only will participate final list of patterns not having valid puzzles with free crossing. Nevertheless, thank you for correction (I'll edit my previous post).

I checked remaining 15 published pattern for maximality. It turns out, patterns P102, P104, P108-P116, P118-P119 (totally 13 patterns) are really maximal, but patterns P106 and P117 are not maximal. Both patterns can be extended futher to maximal patterns
Code: Select all
+-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . x|     |. . .|. . .|. . .|
|. . .|. . .|. . x|     |. . .|x x x|x x x|
|x x x|x x x|x x x|     |. . x|. . .|. . .|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|x x x|x x x|x x x|     |x x x|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|x x x|x x x|x x x|     |x x x|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+

So, only published below 13 patterns with empty B7 box are really maximal.
Code: Select all
Maximal patterns with empty B7 box:

        P102                       P104                       P108
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . .|. . x|        |. . .|. . x|. . x|
|. . x|. . .|. . .|        |. . .|. . .|. . x|        |. . x|. . .|. . .|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |. x .|. . .|. . .|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |x x x|x x x|x x x|        |. . .|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |x . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P109                       P110                       P111
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . x|x x x|        |. . .|. . .|. x x|
|. . .|. . x|. . x|        |. . .|. . x|x x x|        |. . .|. . .|. x x|
|. x x|. . .|. . .|        |. . x|. . x|x x x|        |. . x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|x x x|x x x|x x x|        |. x .|x x x|x x x|        |. x .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P112                       P113                       P114
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . x|        |. . .|. . x|. . x|        |. . .|. x x|. x x|
|. . .|x x x|x x x|        |. . .|. . x|. . x|        |. . .|. x x|. x x|
|. . x|. . .|. . x|        |. . x|x x x|x x x|        |. . x|. x x|. x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. x .|x x x|x x x|        |. x .|x x x|x x x|        |. x .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P115                       P116                       P118
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . .|. . .|        |. . .|. . x|. . x|
|. . .|. . .|. x x|        |. . .|. . .|. x x|        |. . .|. . x|. . x|
|. . x|. . x|. . .|        |. . x|. . x|. . .|        |. . x|. . x|. . x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . x|x x x|x x x|        |. . .|x x x|x x x|        |x x x|x x x|x x x|
|. x .|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

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

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Wed May 22, 2013 5:43 am

Hi, people!
I've done search for patterns not having valid puzzles for the "variant 2 of patterns containing one empty box", i.e. I've checked patterns containing exactly 1 empty box which is placed at the "centre" of crossing (B1 empty box). There are 7 possible such patterns only.
Code: Select all
Patterns having no valid puzzles, which cannot be expanded by adding clues in the B2, B3, B4 and B7 boxes:

        P121                       P122                       P123
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . .|. x x|        |. . .|. x x|x x x|
|. . .|. . .|. x x|        |. . .|. . .|. x x|        |. . .|. x x|x x x|
|. . .|. . x|. . .|        |. . .|x x x|x x x|        |. . .|. x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . x|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. x .|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . x|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. x .|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P124                       P125                       P126
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . x|        |. . .|. . x|. x x|        |. . .|. . x|. . x|
|. . .|. . .|. . x|        |. . .|. . x|. x x|        |. . .|. . x|. . x|
|. . .|x x x|x x x|        |. . .|. . x|. x x|        |. . .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |. . .|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P127
+-----+-----+-----+
|. . .|. . .|. . x|
|. . .|. . .|. . x|
|. . .|x x x|x x x|
+-----+-----+-----+
|. . x|x x x|x x x|
|. . x|x x x|x x x|
|. . x|x x x|x x 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, all these patterns, but P127, are maximal, i.e. adding 1 clue to B1 box brokes their property "not having valid puzzes".

So, all possible crossing patterns containing exactly 1 empty box were considered. I should check the last (the most complicated) case of crossings pattern - crossing patterns without empty boxes.

Serg

[Edited. I corrected 2 errors - P126 pattern contained extra clues, P127 pattern was missed. (Manual error.) Thanks to blue for his correction.]
Last edited by Serg on Fri May 24, 2013 6:16 am, edited 1 time in total.
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby blue » Thu May 23, 2013 7:17 pm

Hi Serg,

Great work again !
I have one differnce from your results.

In place of this patten:

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

I have this one, as a maximal 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|
+-----+-----+-----+

and the (non-maximal) pattern that's a subset of this (maximal) pattern from our earlier discussions:

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

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Fri May 24, 2013 6:07 am

Hi, blue!
blue wrote:I have one differnce from your results.

In place of this patten:

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

I have this one, as a maximal 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|
+-----+-----+-----+

and the (non-maximal) pattern that's a subset of this (maximal) pattern from our earlier discussions:

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

Best Regards,
Blue.

You are right, as usually. I copied wrongly P126 pattern from program listing, and then decided that subset of your last maximal pattern can be excluded. Manual error again! :evil: I'll edit my previous post to fix the error.

Thank you for confirmation of my results!

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Fri May 24, 2013 6:49 am

Hi, people!
I've done search for patterns without empty boxes not having valid puzzles. There are 8 possible such patterns only. One pattern is new, the rest were published earlier. All these patterns are maximal.
Code: Select all
Maximal patterns containing no empty boxes:

        P128                       P129                       P130
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . x|. . .|. . .|        |. . .|. . .|. . x|        |. . .|. . .|. . x|
|. . x|. . .|. . .|        |. . .|. . .|. . x|        |. . .|. . .|. . x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |. . x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . x|x x x|x x x|        |. . x|x x x|x x x|        |. . x|x x x|x x x|
|. . x|x x x|x x x|        |. . x|x x x|x x x|        |. . x|x x x|x x x|
|. . x|x x x|x x x|        |. . x|x x x|x x x|        |. . x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . x|x x x|x x x|        |. . x|x x x|x x x|        |. . x|x x x|x x x|
|. . x|x x x|x x x|        |. . x|x x x|x x x|        |. . x|x x x|x x x|
|. . x|x x x|x x x|        |. . x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P131                       P132                       P133
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|. . .|        |. . .|. . .|. . x|        |. . .|. . .|. . .|
|. x .|. . .|. . .|        |. . .|. . .|. . x|        |. . .|x x x|x x x|
|. . x|x x x|x x x|        |x x x|x x x|x x x|        |. . x|. . .|. . .|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . x|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . x|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . x|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . x|x x x|x x x|        |. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . x|x x x|x x x|        |x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+

        P134                       P135
+-----+-----+-----+        +-----+-----+-----+
|. . .|. . x|. . x|        |. . .|. . .|. . .|
|. . .|. . x|. . x|        |. . .|. . .|. x x|
|. . x|. . x|. . x|        |. . x|. . x|. . .|
+-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . .|x x x|x x x|
|x x x|x x x|x x x|        |. x .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x 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, all possible maximal crossing patterns were considered.

I should mention for the sake of completeness one more maximal pattern:
Code: Select all
        P136
+-----+-----+-----+
|. . .|. . .|x x x|
|. . .|. . .|x x x|
|. . .|. . .|x x x|
+-----+-----+-----+
|. . .|x x x|x x x|
|. . .|x x x|x x x|
|. . .|x x x|x x x|
+-----+-----+-----+
|x x x|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 is well known that this pattern has no valid puzzles. It turns out it is maximal.

Hope, I am not wrong this time :) .

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

Re: Investigation of one-crossing-free patterns

Postby Serg » Fri May 24, 2013 8:11 am

Hi, blue!
Would you clarify the way of splitting posted below two-column UA18 to Type-A and Type-B pieces? (Two-row UA18 is splitted easily.) Published fragment is part of real solution grid.
Code: Select all
+-----+-----+-----+
|9 1 2|3 4 5|6 8 7|
|3 8 4|1 6 7|5 2 9|
|5 6 .|. . .|. . .|
+-----+-----+-----+
|1 5 .|
|6 4 .|
|2 7 .|
+-----+
|4 2 .|
|8 3 .|
|7 9 .|
+-----+

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

Re: Investigation of one-crossing-free patterns

Postby coloin » Fri May 24, 2013 1:27 pm

Fantastic work Serg

Now the fun starts

There will be many 16 clue patterns which are within each one of your "proven impossible" patterns.

What are the reductions on the symmetric 18s - perhaps the main incentive for this work ?

Many patterns with 9 clues plus 12 will be impossible too [either 9 clues in a box or 9 clues in a row].

Currently i have found 105 vertical-9plus12s [ongoing] and 143 box-9plus12s [stopped]. here

C
coloin
 
Posts: 1629
Joined: 05 May 2005

Re: Investigation of one-crossing-free patterns

Postby blue » Fri May 24, 2013 2:49 pm

Hi Serg,

Serg wrote:Would you clarify the way of splitting posted below two-column UA18 to Type-A and Type-B pieces? (Two-row UA18 is splitted easily.) Published fragment is part of real solution grid.
Code: Select all
+-----+-----+-----+
|9 1 2|3 4 5|6 8 7|
|3 8 4|1 6 7|5 2 9|
|5 6 .|. . .|. . .|
+-----+-----+-----+
|1 5 .|
|6 4 .|
|2 7 .|
+-----+
|4 2 .|
|8 3 .|
|7 9 .|
+-----+

I'm confused -- it's UA4+UA14 in the columns.

Blue.
blue
 
Posts: 573
Joined: 11 March 2013

PreviousNext

Return to General