Another "Monster" Puzzle

Advanced methods and approaches for solving Sudoku puzzles

Another "Monster" Puzzle

Postby Carcul » Mon Feb 13, 2006 5:28 pm

Now is my turn to offer a monster puzzle (at least it looked a monster to me) for all those who like very hard puzzles:

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

I have picked up this grid some time ago in the progammers forum.

Have fun.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Re: Another "Monster" Puzzle

Postby aeb » Tue Feb 14, 2006 12:28 pm

Carcul wrote:
Code: Select all
 . . . | 3 . . | . 1 .
 . 1 4 | . 2 7 | . . .
 . . . | . . 5 | . . 6   
-------+-------+-------
 6 5 3 | . . . | 1 . 7
 4 7 . | . . . | . . .
 1 . . | . . . | . 8 .
-------+-------+-------
 . . . | . . 4 | 9 . 5
 8 . . | . . . | . 2 .
 . . . | 5 . . | . . .


Hmm, yes, a difficult one. It starts out easy:

(2,8)9 > (4,8)4 > (6,679)356 > (5,8)!5 > (2,8)5
shows (2,8)!9.
(As an aside to ronk and jeff: if you feel happier about having closed loops, then add (2,8)!9 at the end.)

Then (5,5)!5 > (6,5)5 > (6,4)7 > (58,4)19 > (3,4)!1 > (3,5)1 > (5,5)!1
shows (5,5)!1.
(Same aside: prefix the chain with (5,5)1 if you prefer.)

Next a forcing net that shows that (2,9)!3 because (3,5) must be both 1 and 9:
a) (2,9)3 > (6,9)4 > (6,4)7
b) (2,9)3 > (9,9)8 > (8,9)1
c) a+b > (8,4)9 > (5,4)1 >> (3,4)!19
d) (2,9)3 > (6,9)4 > (4,8)9 > (3,8)!9
e) (2,9)3 + d > (1,9)9
Now in box 2 both 1 and 9 can only be at (3,5), contradiction.
(Of course this can be written in such a way that the word contradiction is avoided. For example, conclude (3,5)1 and (1,[56])9 and (2,9)9 > (2,9)!3 to close the loop.)

Next a more messy reasoning that shows that (5,9)!3, and after that the way (my way) is still long.
aeb
 
Posts: 83
Joined: 29 January 2006

Postby Carcul » Tue Feb 14, 2006 1:44 pm

Very good Aeb.

Aeb wrote:Next a more messy reasoning that shows that (5,9)!3, and after that the way (my way) is still long.


My solution is also long (20 steps), so don't worry about it.:D

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby maria45 » Wed Feb 15, 2006 5:40 pm

Hi Carcul,

this didn't seem a "monster" to me. My solution uses 15 forcing chains:

e4=1 or e4=9, d8=9, d45=4, f4=7, h4=1 > cg4!=1 > c5=1, g3=1
d4=2 or g4=2, g5=8, d58=49 > d4!=49
c4=4 or f4=4, d8=4 > c8!=4
c4=4 or c7=4, a5=4, f4=4, d8=4, d56=9, e4=1, f5=7, f9=3, f6=6, e5=5, e6=3, f7=5, hk9=14, k7=8, b7=3 > c7!=3
e9!=9, bc8!=9 or e9=9, d8=4, f9=3, f6=6, f7=5, e7=2, b9=8, b7=3, ac7=47, c8=9 > b8!=9
b8=5, a1=5 or e8=5, b8=3, f5=5, f4=7, d5=4, d8=9, c8=7, c4=4, c7=2, c3=9, b1=5 > a1!=9, b7!=5
e9=2 or a9=2, f9=4, d9=9 > e9!=9 > c8!=9
f9=3 or f9=4, c4=4, a56=89, a9=2, e9=3 > bhk9!=3, e78!=3, f7!=3
f6=6 or f6=3, f9=4, c4=4, a7=4, e9=3, e7=2, f7=5, f5=6 > f56=6
f4=4 or f4=7, d8=9, k8=4, c4=4, c2=8, bc1=3, c13=9, b9=9, b7=8, bc8=3, k9=8, h9=1, k6=1, g4=2, g1=7, c8=7, g8=6, e8=5, f7=4 > f59!=4 etc.
e5=5 or f5=5, f7=4, d8=9, f4=7, c4=4, c2=8, bc1=3, a56=89, a9=4, b9=9, b7=8, bc8=3, k9=8, k6=1, g4=2, g1=7, g8=6, e8=5 > e7!=5 > e7=6
e8=9 or e8=5, f7=4, a9=4, h9=1, k6=1, e4=1, g4=2, g5=8, a5=9, e6=9 > e45!=9 > e4=1
d4=8 or d4=2, k6=2, k9=1, b9=8, a9=9, a6=8 > d6!=8 > a6=8, c2=8
b8=3 or b8=5, e8=9, d8=4, f4=4, a5=4, a9=9, b9=8, b7=3 > c8!=3 > c8=7 > c1=3 > cf3=29 > a59=49 > acf7=245
h7=3 or h7=7, h4=9, a5=9, b9=9, b7=8, k7=3 > gk8!=3 etc.

Kind regards, Maria
maria45
 
Posts: 54
Joined: 23 October 2005

Postby tso » Sat Feb 18, 2006 5:05 pm

maria45 wrote:Hi Carcul,

this didn't seem a "monster" to me. My solution uses 15 forcing chains:


First, are you being ironic? If 15 mostly long, convoluted and complex 'chains' do not a monster make, what is? Are you saying this is just another trivial puzzle for you, aren't we the slow ones? (Even calling them '15' chains is misleading -- many are actually multiple deductions combined.)

Second, some of these are not forcing chains. In a forcing chain, each step must follow from the previous and lead to the next. If one step requires two or more of the previous steps, you've got something else -- a forcing NET at best. It's confusing to try to follow your logic if you secretly redefine long accepted terms. The point of forcing chains is that they can be followed along by eye without having to make any marks or erasures -- and if it turns out the chain doesn't work -- no backtracking is needed and the puzzle is not spoiled. Forcing nets do NOT have this capability. I forcing chain can also be marked with a single, simply connected closed loop that visits each cell used. Many of your thingy's cannot be marked this way -- attempting to do so leaves a creats a multiply connected spider web, not a closed loop.

For example, your first statement:


maria45 wrote:e4=1 or e4=9, d8=9, d45=4, f4=7, h4=1 > cg4!=1 > c5=1, g3=1



(I don't understand how you decide when to use ',' and when to use '>' in your notation. It seems arbitrary.)

But f4=7 does NOT imply that h4=1, only that h4<>7. If (e4=9 AND f4=7), then h4=1. But this step is not part of your given solution -- I only see it because I'm actually marking my puzzle -- solving it as I go. Ok, from that point ...

Either e4=1 or h4=1, therefore cg4<>1, therefore c5=1, then g3=1

But again, c5=1 does NOT imply that g3=1, only that g34=1. If (c5=1 AND (e4=1 OR h4=1)), then g3=1. But you didn't state this.


What is the arbitrary limitation you are using that would prevent me from starting with a cell chosed at random in the puzzle, solving at will from each candidate in turn, with a dozen or more links, half of which are only implied by two or more previous links taken together, and calling it a forcing chain?

This was one of your shortest and simplest "forcing chains" -- and I cannot follow by eye without crossing out and circling candidates as I go.

Code: Select all
 *--------------------------------------------------------------------*
 | 259    2689   2679   | 3      489    89     | 2457   1      249    |
 | 359    1      4      | 6      2      7      | 358    359    389    |
 | 239    2389   279    | 1489   1489   5      | 2347   3479   6      |
 |----------------------+----------------------+----------------------|
 | 6      5      3      | 2489   489    289    | 1      49     7      |
 | 4      7      8      | 19     13569  1369   | 2356   3569   239    |
 | 1      29     29     | 47     34567  36     | 3456   8      34     |
 |----------------------+----------------------+----------------------|
 | 7      236    126    | 128    1368   4      | 9      36     5      |
 | 8      3469   5      | 179    13679  1369   | 3467   2      134    |
 | 239    23469  1269   | 5      13679  12369  | 34678  3467   1348   |
 *--------------------------------------------------------------------*


Ok -- I'll fill in the conclusions from your first three "forcing chains" and make any other trivial deductions:

e4=1 or e4=9, d8=9, d45=4, f4=7, h4=1 > cg4!=1 > c5=1, g3=1
d4=2 or g4=2, g5=8, d58=49 > d4!=49
c4=4 or f4=4, d8=4 > c8!=4


Code: Select all
 *--------------------------------------------------------------------*
 | 2579   2689   2679   | 3      489    89     | 2457   1      249    |
 | 359    1      4      | 6      2      7      | 358    359    389    |
 | 2379   2389   279    | 489    1      5      | 2347   379    6      |
 |----------------------+----------------------+----------------------|
 | 6      5      3      | 28     489    289    | 1      49     7      |
 | 4      7      8      | 19     3569   1369   | 2356   3569   239    |
 | 1      29     29     | 47     34567  36     | 3456   8      34     |
 |----------------------+----------------------+----------------------|
 | 237    236    1      | 278    3678   4      | 9      367    5      |
 | 8      3469   5      | 179    3679   1369   | 3467   2      134    |
 | 2379   23469  2679   | 5      3679   12369  | 34678  3467   1348   |
 *--------------------------------------------------------------------*


Apparantly, you looked at this candidate grid and this monstrosity was clearly obvious to you:

c4=4 or c7=4, a5=4, f4=4, d8=4, d56=9, e4=1, f5=7, f9=3, f6=6, e5=5, e6=3, f7=5, hk9=14, k7=8, b7=3 > c7!=3

Ok, the first few links seem fine:

c4=4 or c7=4, a5=4, f4=4, d8=4, d56=9, e4=1, f5=7 -- say what? Exactly how does e4=1 imply that f5=7? Stumped? It *doesn't*. But f4=4 (from three links earlier in the 'chain') DOES imply f5=7.

Continuing from f5=7, f9=3 --- What's that you say? f5=7 does NOT imply f9=3. Again, f4=4 does, but you didn't say that. This 'chain' is increasingly looking like a 'web' in which the links could have been written in many other arbtirary sequences, as the sequence doesn't matter.

Continuing from f9=3, f6=6, e5=5 -- Not again. f6=6 doesn't imply e5=5, f5=7 does.

Continuing from e5=5, e6=3. I give up. Not only does e5=5 not impley e6=3 -- NONE of the previous steps imply it either! Instead, you must have figured that if (e5<>3 AND f5<>3 AND f6<>3), then e6=3. How exactly is that a chain? How exactly does one *see* that without actually solving the puzzle, crossing out candidates and filling in numbers as you go? And if it turns out to be a dead end, how exactly do you backtrack without having made a copy in advance?

I cannot finish to the end of this 'chain'. It is too convoluted, too much of a web, too much for me to follow even using pencil and paper. It appears to me that you just bifurcated the puzzle by placing c4=4 in one copy and c7=7 in another, then solved at will, making whatever exclusions as you went. Then, seeing where the two paths overlapped, you created this 'chain'.

Theses 'chains' are not 'chains' -- nor are they a solution. They are an partial record of an arbitrary brute force search.

It would have been no less valid and no more difficult to follow if you had simply stated that your fourth forcing chain was:

c4=4 or c7=4, therefore c7!=3.



1) KP to KP4. Mate in 22.
tso
 
Posts: 798
Joined: 22 June 2005


Return to Advanced solving techniques