The New Sudoku Players' Forum

[blue]

Hi Serg,

Maybe I missed something. But when we'll split 2-row minimal UA set to 2 pieces and split 2-column minimal UA set to 2 pieces (the case when both r1/r2 rows and c1/c2 columns contain minimal UA18 sets), we'll obtain 2 independent UA (let call them "rows+columns" UA sets) - the first UA contains r1c1 and r2c2 (plus one 2-row piece and one 2-column piece), the second (complementary) UA must contain r1c2 and r2c1 (plus another 2-row piece and another 2-column piece).

There are actually 4 UA sets that we can construct (when the two UA18s are present): (A-rows)+(A-cols), (A-rows)+(B-cols), (B-rows)+(A-cols), and (B-rows)+(B-cols).
[ Note: "(A-rows)", here, is short for "the type-A rows fragment". It is not a UA set by itself, but must be joined with either a type-A or type-B columns fragment. Either one will work ! ]

For the 4th shape, the "B+B" combination will always miss the clues, since the only clue in R12C12, is in R2C2, and the type B fragments don't include R2C2.
For the other patterns, the story is this: first, one of the type-A or type-B row fragments must be chosen. The type-A fragement, contains R1C1, R2C2, and some set of R12Cn segments with n >= 3. The type-B fragment, contains R1C2, R2C1, and all of the R12Cn segments not contained in the type-A fragment. The (1st 3) puzzle patterns, contain just one R12Cn segment and nothing from R12C12. We need to choose the fragment, that doesn't contain that R12Cn segment. If R12Cn is part of the type-A fragment, it won't be part of the type-B fragment, and vica-versa. Then we need to make a similar choice for a columns fragment, and join the two fragments together, to produce the final UA set.

To ease confusion, I probably should have shown the 4 UA sets that can be constructed from the two "sample" UA18s.

Code: Select all

(A-rows, A-cols)              (A-rows, B-cols)
+-------+-------+-------+     +-------+-------+-------+
| 5 . 7 | 4 . 2 | 3 9 . |     | 5 6 7 | 4 . 2 | 3 9 . |
| . 3 2 | 7 . 9 | 4 5 . |     | 8 3 2 | 7 . 9 | 4 5 . |
| 9 1 . | . . . | . . . |     | . . . | . . . | . . . |
+-------+-------+-------+     +-------+-------+-------+
| . . . | . . . | . . . |     | 7 8 . | . . . | . . . |
| 3 2 . | . . . | . . . |     | . . . | . . . | . . . |
| . . . | . . . | . . . |     | 6 4 . | . . . | . . . |
+-------+-------+-------+     +-------+-------+-------+
| 2 9 . | . . . | . . . |     | . . . | . . . | . . . |
| 1 5 . | . . . | . . . |     | . . . | . . . | . . . |
| . . . | . . . | . . . |     | 4 7 . | . . . | . . . |
+-------+-------+-------+     +-------+-------+-------+

(B-rows, A-cols)              (B-rows, B-cols)
+-------+-------+-------+     +-------+-------+-------+
| 5 6 . | . 1 . | . . 8 |     | . 6 . | . 1 . | . . 8 |
| 8 3 . | . 6 . | . . 1 |     | 8 . . | . 6 . | . . 1 |
| 9 1 . | . . . | . . . |     | . . . | . . . | . . . |
+-------+-------+-------+     +-------+-------+-------+
| . . . | . . . | . . . |     | 7 8 . | . . . | . . . |
| 3 2 . | . . . | . . . |     | . . . | . . . | . . . |
| . . . | . . . | . . . |     | 6 4 . | . . . | . . . |
+-------+-------+-------+     +-------+-------+-------+
| 2 9 . | . . . | . . . |     | . . . | . . . | . . . |
| 1 5 . | . . . | . . . |     | . . . | . . . | . . . |
| . . . | . . . | . . . |     | 4 7 . | . . . | . . . |
+-------+-------+-------+     +-------+-------+-------+


I hope that helps,

Blue.

[Serg]

Hi, blue!
I accepted your proof. Well done!
Can you generalize this result to a theorem stating requirements to any pattern (class of patterns) not to have valid puzzles?

Some remarks. I confirm all 4 patterns used in the proof have no valid puzzles. (I've done exhaustive search.)

I get to know important new idea from your proof. I use checking for "2 rows + 2 columns" UA sets in my searching program to reduce search space and speed up the search. (This technique speeds up the search 2 times.) But I checked only UA set consisting of "similar" parts ("A-rows"+"A-cols" and "B-rows"+"B-cols" only). So, your result can potentially speeds up my searching program twice. Fantastic!

Serg

[blue]

Hi Serg,

I get to know important new idea from your proof. I use checking for "2 rows + 2 columns" UA sets in my searching program to reduce search space and speed up the search. (This technique speeds up the search 2 times.) But I checked only UA set consisting of "similar" parts ("A-rows"+"A-cols" and "B-rows"+"B-cols" only). So, your result can potentially speeds up my searching program twice. Fantastic!

That's pleasing to hear!

Can you generalize this result to a theorem stating requirements to any pattern (class of patterns) not to have valid puzzles?

Probably the only thing I can say, is what you already know: If there is a UA set in every way of filling the empty cells that has an extension to a full grid, then the pattern has no puzzles (and vica-versa).
This was just a case where it was relatively easy to show that the a UA set could always be found. To be honest, the only other case like that, that I know of, is "two empty rows".

This is off-topic, but I do know of a few other families of "magic pattern", where it looks like some details involving 2-row UA sets, might be useful in a "proof". Something else is needed too, though.

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


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

Code: Select all

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


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


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


Blue.

[Serg]

Hi, blue!
Impressive results! You found 14 new patterns having no valid puzzles. Many of them have vertical symmetry, so seem to be useful for filtering out extra 18-clue symmetric patterns. In what way did you find these patterns? Are they maximal (can they be extended further by adding clues preserving property not having valid puzzles)?

Serg

[Serg]

Hi!
I reconsidered variant V3 of patterns containing 2 empty boxes, i.e. patterns having map

Code: Select all

  V3

0 0 A
B 9 9
C 9 9


because blue found missed pattern in my publication, not having valid puzzles (for this class of patterns). I analyzed possible configurations more carefully and found only one new pattern - namely pattern posted by blue. Below are final results of exhaustive search.

Code: Select all

Patterns having no valid puzzles:

         P98                        P99                       P100
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|. . .|x x x|        |. . .|. . .|x x x|        |. . .|. . .|. x x|
|. . .|. . .|x x x|        |. . .|. . .|x x x|        |. . .|. . .|. x x|
|. . .|. . .|x x x|        |. . .|. . .|x x x|        |. . .|. . .|. x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . x|x x x|x x x|        |. . .|x x x|x x x|
|. . .|x x x|x x x|        |. . x|x x x|x x x|        |. . x|x x x|x x x|
|x x x|x x x|x x x|        |. . x|x x x|x x x|        |. x .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|. . .|x x x|x x x|        |. . x|x x x|x x x|        |. . .|x x x|x x x|
|x x x|x x x|x x x|        |. . x|x x x|x x x|        |. . x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|        |. x .|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+


I'll edit my post with summary of 2 empty boxes searching case.

Serg

[Edited. I corrected a typo.]

[coloin]

Excellent - although i dont completely follow it
Well maybe there is furthur patterns which you can use your theory to confirm that this pattern always has an unavoidable in the empty cells

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

maybe the solitary clue can be anywhere in Boxes 1379
C

[blue]

Hi Serg,

Impressive results! You found 14 new patterns having no valid puzzles. Many of them have vertical symmetry, so seem to be useful for filtering out extra 18-clue symmetric patterns. In what way did you find these patterns? Are they maximal (can they be extended further by adding clues preserving property not having valid puzzles)?

A lot of hard work -- to find them ... a long time ago, now.
They are maximal -- assuming I didn't make any mistakes.

For the 14 in that post, I had written something to track of a pair of flags for all of the ED patterns that could be built up from non-overlapping 3-cell "box intersect line" segments -- "has puzzles", and "can't have puzzles" flags. I also had some code to mark supersets of patterns as having puzzles (when I found one), and to mark subsets of patterns as not having puzzles (when I could show it). And finally I had some code to print out the patterns that didn't have either flag set, but where each of its "superset patterns" had "known" puzzles. Then I had some crude code to search for puzzles with a variety of shapes (masking down random solution grids), and also some more refined code, that could focus on a pattern at a time, looking for puzzles, but without doing an exhaustive search. I ran all of that for a while ... updating "has puzzles" flags ... until it was a long time between new puzzles being found. Then started working by hand with the "maximal" cases -- expanding them a few "odd" cells at a time (moving away from the "built from line-box intersections" shapes), and trying to find puzzles for the larger shapes. When I had a hard time with a shape, I'ld try checking whether it would be a maximal no-puzzle shape, assuming it didn't have puzzles -- trying to find puzzles for each of the ED "one extra cell" shapes. If that was true, then finally I'ld write some code to do the kind of "UA sets in ED empty cell fills" test, that we've both mentioned (and both learned from Red Ed's posts). If that code found an empty cell fill with no UA set, then it would produce a puzzle for the patterm, that I could feed back into the "flags" list -- at least if the pattern hadn't been expanded yet. Otherwise, I'ld have to re-evaluate my progress with the "cell-by cell" expansions, and try something else. On the other hand, if every empty cell with an extension to a full grid, had a UA set in it, I'ld flag the original shape and its subsets, as having no puzzles, and, or course, record the new "magic pattern". When everything was done, I had all of the original shapes flagged one way or another -- as having puzzles, or not having puzzles. For the largest ones without puzzles, I had an "expansion by single cells" to a maximal/"magic" pattern (one, at least ... probably never two). For the "families" of patterns that I showed, I think the story was probably that one of the "pending" shapes built from line-box segments, would look similar to a finished magic pattern, and I'ld try something similar for the "cell by cell" expansion for that one.

I should probably confess that I did something similar for the "4 filled corner boxes" shapes, but where every shape was handled, and the "cell by cell" expansions weren't necessary -- shapes of the type that you're working with in this thread. I think I have the complete list of magic patterns for that class. My code to do the final detailed checks for the final patterns, was custom tailored for each pattern (or sometimes 2 or 3 related patterns). It was very easy to introduce a bugs into it, and so it's possible that my list isn't correct. The code wasn't "bug prone", but it wasn't "foolproof" either. I've been following your posts on this forum, hoping that you would eventually confirm some of my findings. When you published your list of "2 empty boxes" patterns, I compared it with the patterns in my list, pruned down to have two empty boxes (in various ways, as necessary). That's how I came up with the missing case.

Do keep up the good work !

Regards,
Blue.

[blue]

Hi Colin,

Excellent - although i dont completely follow it
Well maybe there is furthur patterns which you can use your theory to confirm that this pattern always has an unavoidable in the empty cells

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

maybe the solitary clue can be anywhere in Boxes 1379

I wish I had a "magic bullet", to test any pattern, but unfortunately I don't.

I was able to find a puzzle for the pattern that you posted -- oddly enough -- but none for any of the cases where the extra clue is someplace else in B1379.

Code: Select all

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


When the odd clue is in any of these positions ('c's):

Code: Select all

x c . | 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 . x | . . .
c . . | x . x | . . .
x . . | x . x | . . .


... I know that it won't have puzzles, since those patterns can be transformed to subsets of this (easier to verify) "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 x x | x x x


When it's in any of these positions, I can't say anything definite, but I can't find a puzzle either.

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 | . . .
. c . | x . x | . . c
x c . | x . x | . . c


I went as far as I could, with the "empty cell fills" and "extension to full grid + has a UA set" tests, but I think there are too many ED fills to handle, to complete the task in a reasonable time. For the method that I use, usually I try to work with fills for some subset of the empty cells, first ... weeding out cases with UA sets, and keeping only ED cases. Then I extend those to the fills for the full set of empty cells -- typically doing extensions bt a set of pre-computed fills that has also been puned of cases with UA sets. That can dramitically reduce the amount of testing that is required. But I haven't been able to come up with a trick that works -- just focusing on the pattern where the isolated clues are all in the corners. It's looking like 100's to 1000's of Gigs of "fills" would need to be tested. I may yet come up with the right trick ... one more idea ... but maybe there just aren't any to be had. Serg may have some ideas, that are completely unrelated to my approach.

I've been polluting the topic of Serg's thread, for a several posts now -- it's getting uncomfortable.
Sorry Serg.

Regards,
Blue.

[Serg]

Hi!
blue, I am under impression of your work, concerning coloin's pattern analysis. You found results so quickly!

Serg may have some ideas, that are completely unrelated to my approach.

I can only state, that patterns having map

Code: Select all

1 1 9
1 1 9
9 9 9


has valid puzzles at least for some configuration of the clues in B1, B2, B4, B5 boxes. This map is not applicable for the pattern considered, because given pattern is it's subset. I have no other ideas now concerning given pattern. Instead I am planning to finish my investigation (consider "one empty box" and "no empty boxes" crossings).

I've been polluting the topic of Serg's thread, for a several posts now -- it's getting uncomfortable.
Sorry Serg.

It's curious for me to hear such thing from you, blue. Please, feel free to post something in my threads! Your posts are usually rich of valuable ideas. I am always reading them with great interest. You know - one of the most interesting themes for me is study of maximal patterns. In fact, this thread is dedicated to maximal patterns. So, any ideas concerning patterns not having valid puzzles are very interesting for me.

Serg

[coloin]

Thanks blue glad Serg doesnt mind.
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 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 ....

C

[Serg]

Hi, coloin!

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".

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

[blue]

Hi Colin,

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.

[Serg]

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

[coloin]

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

[Serg]

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