The New Sudoku Players' Forum

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The New Sudoku Players' Forum

Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns

Re: Investigation of one-crossing-free patterns