Dead Ends

Post the puzzle or solving technique that's causing you trouble and someone will help

Dead Ends

Postby JC » Fri Feb 10, 2006 3:15 pm

Hi, I’m stuck on a diabolic puzzle from Michael Mepham. This is the original version:
Code: Select all
|.9.|7..|86.|
|.31|..5|.2.|
|8.6|...|...|
|..7|.5.|..6|
|...|3.7|...|
|5..|.1.|7..|
|...|...|1.9|
|.2.|6..|35.|
|.54|..8|.7.|

Then this is what I’ve got so far:
Code: Select all
|295|7..|861|
|.31|865|92.|
|8.6|...|...|
|..7|.5.|..6|
|...|387|...|
|5..|.16|7..|
|...|5..|1.9|
|.2.|6..|35.|
|.54|..86|72|

I've just got so little clues, the puzzle is only half way of completion.
Please teach me the next steps because I can’t see any further solution. All I can see is that there are about 3 probabilities for almost every cell by my pencil marks.
JC
 
Posts: 10
Joined: 02 January 2006

Postby vidarino » Fri Feb 10, 2006 3:30 pm

Since you didn't post them, I will assume these are your pencilmarks:
Code: Select all
      2      9      5 |       7     34     34 |       8      6      1
     47      3      1 |       8      6      5 |       9      2     47
      8     47      6 |    1249   2349  12349 |      45     34   3457
----------------------+-----------------------+----------------------
   1349    148      7 |     249      5    249 |      24  13489      6
   1469    146     29 |       3      8      7 |     245    149     45
      5     48   2389 |     249      1      6 |       7   3489    348
----------------------+-----------------------+----------------------
    367    678     38 |       5   2347    234 |       1     48      9
    179      2     89 |       6    479    149 |       3      5     48
    139      5      4 |      19     39      8 |       6      7      2


First of all, there is a naked pair 34 in box 2, which means you can erase the rest of the 3s and 4s in that box.

Now, you have a couple of Locked Candidates hidden in there. Look at the 1s in column 2. They are both inside box 4, which means that the rest of the 1s in box 4 can be eliminated.

Also, you have a naked triple (249+249+24) in row 4, which means that you can erase 2, 4 and 9 from the rest of the row.

The last two operations will unlock a single number which should pave the road to the solution. ;)
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby JC » Fri Feb 10, 2006 4:14 pm

which means that the rest of the 1s in box 4 can be eliminated

Well, do you mean that is the elimination of 1s in column 1 box 4? If so, I have done it before but doesn’t give me a brighter sight.
The naked triple you’ve mentioned, I found out something different on my pencil marks. In row 8 there is 4 which eliminate the possibilities of other 4s in row 8. So 4 will only be on row 5&6 in column 8.
Back to the second box, we understand that the first row has 34, 34 possibilities. Hence box 5 will have the 4 in only column 4 which makes r4c6 is 29 not 249. So, does this change make an effect to the solution you gave? I mean, can we still eliminate the 2,4,9 on the rest of the row?
I’m sorry that I don’t understand the theories such as naked triple, etc well. I hope you don’t mind to explain it further.
JC
 
Posts: 10
Joined: 02 January 2006

Postby vidarino » Fri Feb 10, 2006 5:33 pm

Yep, I meant the 1s in column 1, box 4. Good to hear you got them already.:)

The 34-pair in box 2 doesn't affect the rest of the solution at this point, no. I just worked from the assumption that these were the current pencil marks.

JC wrote:I’m sorry that I don’t understand the theories such as naked triple, etc well. I hope you don’t mind to explain it further.


Sure, I'll try.:)

The naked triple I mentioned is the three cells in R4 containing 249, 249 and 24. Since there are three values spread over three cells (and this holds true for sets of any size, including pairs), it means that the candidates are "locked" in these cells, and therefore no other cells in R4 can contain a 2, 4 or 9.

So, if you already eliminated the 1 from R4C1 (row 4, column 1), you should have a "349" there. However, thanks to the aforementioned naked triple, you can now eliminate 4 and 9 from that cell, leaving a single 3.

After setting that 3 and eliminating the 3s from the rest of the column, you should be able to find another naked pair, which will yield a few more eliminations, which will eventually lead to a solution.:)
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby tso » Fri Feb 10, 2006 6:58 pm

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


Code: Select all
 
2      9      5      | 7      34     34     | 8      6      1   
47     3      1      | 8      6      5      | 9      2      47   
8      47     6      | 1249   2349   12349  | 45     34     3457
---------------------+----------------------+-------------------
1349   148    7      | 249    5      249    | 24     13489  6   
1469   146    29     | 3      8      7      | 245    149    45 
5      48     2389   | 249    1      6      | 7      3489   348
---------------------+----------------------+-------------------
367    678    38     | 5      2347   234    | 1      48     9   
179    2      89     | 6      479    149    | 3      5      48 
139    5      4      | 19     39     8      | 6      7      2   


1) r1c56=[34][34]; this is a "naked pair"; it eliminates other 3's and 4's from the rest of box 2.
2) After (1), r46c4 are the only two cells in column 4 that can hold a 4; This is "locked candidates"; eliminate the other 4 from box 5
3) r78c1 are the only two cells that can hold a 1 in box 7. This are "locked candidates"; elimiate other 1's from column 1
4) r4c7+r5c7+r5c9=[24][245][45]; this is a "naked triple"; it eliminates other 2s, 4s and 5s from box 6.
5) r4c467=[249][249][24]; another "naked triple"; it eliminates other 2s, 4s and 9s from from row 4.

After these eliminations, several singles are possible. Updating the grid:

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


Code: Select all
2     9     5     | 7     4     3     | 8     6     1   
47    3     1     | 8     6     5     | 9     2     47 
8     47    6     | 129   29    129   | 45    34    3457
------------------+-------------------+-----------------
3    *18    7     | 249   5     29    | 24   *18    6   
469   146   29    | 3     8     7     | 245   19    45 
5    x48    289   | 249   1     6     | 7    x389   38 
------------------+-------------------+-----------------
67   *678   3     | 5     27    24    | 1    *48    9   
179   2     89    | 6     79    149   | 3     5     48 
19    5     4     | 19    3     8     | 6     7     2   


6) There are only two places for a 9 in row 4, both of which are in box 5. This is locked candidates. The other 4 in box 5 is excluded.
7) There are only two cells in ROWS 4 and 7 that can hold an 8 (marked above with '*') -- all are in COLUMNS 2 and 8. This is an "x-wing". All other 8s in those two COLUMNS are eliminated (marked above with 'x')

After these eliminations, several singles are possible. Updating the grid:


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




Code: Select all
2    9    5    | 7    4    3    | 8    6    1 
4    3    1    | 8    6    5    | 9    2    7 
8    7    6    | 19   29   12   | 45   34   345
---------------+----------------+--------------
3    18   7    | 4    5    9    | 2    18   6 
69   16   2    | 3    8    7    | 45   19   45
5    4    89   | 2    1    6    | 7    39   38
---------------+----------------+--------------
67   68   3    | 5    27   24   | 1    48   9 
179  2    89   | 6    79   14   | 3    5    48
19   5    4    | 19   3    8    | 6    7    2 


There are lots of fun ways to finish off the puzzle. Which to use is a matter of taste.

The four cells r35c79 form a UNIQUE RECTANGLE. If r3c9 was [45] the puzzle would have multiple soltions. This is not allowed. Therefore, r3c9=3. After this, the rest of the puzzle is singles.

OR

r8c1+r8c5+r9c1 form an XYZ-wing. No matter WHAT value you place in ANY one of these three cells, the immediate result is that r8c3<>9. Therefore, r8c3=8 and the rest of the puzzle is just singles.

OR

8c) There are dozens of simple xy-type forcing chains of various lengths, all of which will solve the puzzle. For example, here's a five cell chain:


r9c1=1 -> r9c4=9
r9c1=9 -> r8c3=8 -> r8c9=4 -> r8c6=1 -> r9c4=9
Therefore, r9c4=9

This can be expressed as a nice loop:

[r9c1]-9-[r8c3]-8-[r8c9]-4-[r8c5]-1-[r9c4]-9-[r9c1] --> r9c1<>1


OR

There only two unsolved cells with three candidates, the rest have only two. The 'tri-value' cells are r8c1 and r3c9. If r8c1 were [17] instead of [179] and r3c9 were [35] instead of [345], the puzzle would have mutliple solutions (this is BUG -- bivalue universal grave). Therefore, either r8c1=9 OR r3c9=4 OR both.

This allows another 5 cell forcing chain using BUG avoidance as one link:
r8c9=8 -> r8c2=9 -> r8c5=7
r8c9=4 -> r3c9<>4 -> r8c9=9 -> r8c5=7
Therefore, r8c5=7
tso
 
Posts: 798
Joined: 22 June 2005

Thanks

Postby JC » Sat Feb 11, 2006 8:12 am

Hi, Thank's a lot for the solutions. I can now finish the puzzle and able to understand the function of naked triple which (I just know it now) is very useful. Btw, where can such Sudoku techniques to learn?:D
The final answer:
Code: Select all
|295|743|861|
|431|865|927|
|876|192|543|
-------------
|387|459|216|
|612|387|495|
|549|216|738|
-------------
|863|524|189|
|928|671|354|
|154|938|672|
JC
 
Posts: 10
Joined: 02 January 2006

Postby Carcul » Sat Feb 11, 2006 12:33 pm

Hi JC.

I have a much more quicker (but complicated) solution in the case you are interested in advanced techniques. Consider the initial grid:

Code: Select all
2      9      5      | 7      34     34     | 8      6      1   
47     3      1      | 8      6      5      | 9      2      47   
8      47     6      | 1249   2349   12349  | 45     34     3457
---------------------+----------------------+-------------------
1349   148    7      | 249    5      249    | 24     13489  6   
1469   146    29     | 3      8      7      | 245    149    45 
5      48     2389   | 249    1      6      | 7      3489   348
---------------------+----------------------+-------------------
367    678    38     | 5      2347   234    | 1      48     9   
179    2      89     | 6      479    149    | 3      5      48 
139    5      4      | 19     39     8      | 6      7      2   

First we have:

[r3c9]-7-[r2c9](-4-[r5c9]-5-[r4c7|r5c7]-4-[r6c8|r6c9])-4-[r8c9]-8-[r8c3]-9-[r5c3]-2-[r5c7]-4-[r4c7]-2-[r4c4|r4c6]-4-[r6c4]=4=[r6c2]-4-[r3c2]-7-[r3c9], => r3c9<>7.

This complicated notation means that r3c9 cannot be “7”. Let me try to explain. Let’s consider that r3c9 is “7”: then, r2c9 is “4” – (1) now, on one hand, this means that r5c9 is “5” which eliminates this value from r5c7: but now we have a naked pair on “2,4” in cells r4c7/r5c7 that eliminates the “4” from r6c8 and r6c9, leaving r6c2/r6c4 as the only two places in row 6 for “4”; (2) on the other hand, this means that r8c9 is “8”, and then r8c3 is “9”, and then r5c3 is “2”, which means that r5c7 [which from (1) does not have already a “5”] is “4”, then r4c7 is “2”, which eliminates this value from r4c4/r4c6 and we have now in these two cells a naked pair on “4,9” that eliminates “4” from r6c4 – but this now means that the only place for “4” in row 6 is r6c2, which in turn makes r3c2 =7: but we have started all this reasoning by assuming that r3c9=7, and now we have concluded that if r3c9=7 also r3c2=7, which is a contradiction. In conclusion, r3c9 cannot be “7”.

In second place we have:

[r3c9]=3|2=[r5c7]-2-[r5c3]-9-[r8c3]-8-[r8c9](-4-[r3c9])-4-[r5c9]-5-[r3c9], => r3c9<>4,5 => r3c9=3 and that solve the puzzle.

Let me try to explain this also. In cells r3c7/r3c9/r5c7/r5c9 we have now what I call an Almost Unique Rectangle (check this link and read a thread about this issue, if you like): if r3c9 is not “3” then in order for the puzzle have only one solution we must have r5c7=2; conversely, if r5c7 is not “2” then for just one solution we must have r3c9=3 – these two pieces of information are “encoded” in the notation “[r3c9]=3|2=[r5c7]”. But we also have the following: if r3c9 is not “3”, then, as we have already seen, r5c7 is “2”, which makes r5c3=9, and then r8c3=8, and then r8c9=4, and then r5c9=5 – but r8c9=4 and r5c9=5 eliminates “4” and “5” from r3c9, which does not have already a “3” because we have started this reasoning with the assumption that r3c9 is not “3”: so, we have a situation in which if r3c9 is not “3” then r3c9 will have no possible candidate! This is of course a contradiction, and so r3c9 must be “3”, which solves the puzzle (only naked and hidden singles from here).
If you like, check this link about nice loops, and this link for some good definitions. If you have any doubt or question, please feel free to post them.

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

Re: Dead Ends

Postby Cec » Sun Feb 12, 2006 6:27 am

JC wrote:Hi, Thank's a lot for the solutions. I can now finish the puzzle and able to understand the function of naked triple which (I just know it now) is very useful. Btw, where can such Sudoku techniques to learn?:D


Hi JC,
The following sites (just click on them) are popular for explaining various solving techniques:
http://www.angusj.com/sudoku/hints.php
http://www.simes.clara.co.uk/programs/sudokutechniques.htm

Cec
Cec
 
Posts: 1039
Joined: 16 June 2005

Postby Neunmalneun » Sun Feb 12, 2006 1:48 pm

I think I understand most of your deductions. But what I cannot understand is how you found the "1" in r1c9 before you had the the "4" and the "3" in r1c56.
Neunmalneun
 
Posts: 52
Joined: 22 December 2005

Postby TKiel » Sun Feb 12, 2006 2:59 pm

I'm wondering the same thing as Neunmalneum. From the initial clue set playing nothing but singles leads to here:
Code: Select all
 
 *--------------------------------------------------------------*
 | 2      9      5    | 7      34     134  | 8      6      134  |
 | 47     3      1    | 8      6      5    | 9      2      47   |
 | 8      47     6    | 1249   2349   12349| 45     134    13457|
 |----------------+----------------------+----------------------|
 | 1349   148    7    | 249    5      249  | 24     13489  6    |
 | 1469   146    29   | 3      8      7    | 245    149    145  |
 | 5      48     2389 | 249    1      6    | 7      3489   348  |
 |---------------+----------------------+----------------------|
 | 367    678    38   | 5      2347   234  | 1      48     9    |
 | 179    2      89   | 6      479    149  | 3      5      48   |
 | 139    5      4    | 19     39     8    | 6      7      2    |
 *------------------------------------------------------------*

The locked candidate 1's in box 7 allows exclusion of candidate 1's in box4c1. The naked triple in r4c4,6,7 excludes all candidates from r4c1 except 3. Placement of that 3 reveals two other 3 singles, the second of which makes r1c5 a single 4, which makes 1,3 the only unassigned candidates in row 1.

Tracy
TKiel
 
Posts: 209
Joined: 05 January 2006

Postby ronk » Sun Feb 12, 2006 3:37 pm

Carcul wrote:I have a much more quicker (but complicated) solution in the case you are interested in advanced techniques.
...................
First we have:

[r3c9]-7-[r2c9](-4-[r5c9]-5-[r4c7|r5c7]-4-[r6c8|r6c9])-4-[r8c9]-8-[r8c3]-9-[r5c3]-2-[r5c7]-4-[r4c7]-2-[r4c4|r4c6]-4-[r6c4]=4=[r6c2]-4-[r3c2]-7-[r3c9], => r3c9<>7.

...................
In second place we have:

[r3c9]=3|2=[r5c7]-2-[r5c3]-9-[r8c3]-8-[r8c9](-4-[r3c9])-4-[r5c9]-5-[r3c9], => r3c9<>4,5 => r3c9=3 and that solve the puzzle.

But just a few days ago you wrote here ...

Carcul wrote:Very good: a solution in only two steps. Mine has a lot more (simple) steps: personally, I only try more complex deductions like those two when I cannot spot simpler ones.

... so I'm wondering, which approach do you actually prefer?

Multiple simple steps? Or fewer more complex steps?

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Carcul » Sun Feb 12, 2006 5:03 pm

Hi Ronk.

Ronk wrote:... so I'm wondering, which approach do you actually prefer?


Why is important to you the approach that I prefer? Yes, a few days ago I have written that. But I should have said: "personally, in very hard and extremely hard puzzles, I only try more complex deductions like those two when I cannot spot simpler ones". In easier puzzles like this one, it is too easy to find nice loops that will solve the puzzle, and so part of the challenge of solving such a puzzle is lost: so, I propose a challenge to myself - try to solve the puzzle in just one or two steps but with more complex logical deductions. Instead of using imediatly a deduction made by the first loop that I identify, I prefer not to use it and think for a longer time and try to identify a more "important" deduction (one that allows the puzzle to be solved or considerably advanced). You should try Ronk, is a very good exercise.
Of course, regarding very hard puzzles I will use every "simple" deduction that I find, because finding one is already a victory.
And BTW, the deductions that I have posted are not that complex: please compare them with, for example, the last step in my solution of Vidarino's puzzle - that is a really complex deduction.

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

Postby ronk » Mon Feb 13, 2006 2:31 pm

Carcul wrote:
Ronk wrote:... so I'm wondering, which approach do you actually prefer? Multiple simple steps? Or fewer more complex steps?

Why is important to you the approach that I prefer?

When a newbie starts a thread, is having difficulty with a naked triple, for a puzzle that requires nothing more difficult than an xyz-wing ...

... and a solution step is presented using a "single implication network", with an aggregate length of 13 links, in the relatively obscure shorthand notation of nice loops ...

... I suspect many question the motives for that presentation. I'm just the one that asked.

Carcul wrote:Instead of using imediately a deduction made by the first loop that I identify, I prefer not to use it and think for a longer time and try to identify a more "important" deduction (one that allows the puzzle to be solved or considerably advanced). You should try Ronk, is a very good exercise.

No thanks. There are too many difficult puzzles which require complex steps for me to waste my time finding complex steps in puzzles that don't require them.

Carcul wrote:And BTW, the deductions that I have posted are not that complex ...

Complexity is relative and subjective, of course. As noted above and in the context of a newbie's question, it seems obvious your solution was complex.

Anyway, I guess the short answer to my question is ... your personal preference is fewer solution steps despite their relative increased complexity.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA


Return to Help with puzzles and solving techniques