## Need help with a "diabolical" puzzle!

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

### Need help with a "diabolical" puzzle!

I've made it through Easy, Tricky, and Tough, but am having a very hard time with Diabolical! I'm missing something, I'm sure, and would really appreciate some help. Here is the puzzle so far:

* 5 * / * * 1 / 6 * *
3 * 6 / * * 2 / * * *
* * 9 / 3 * * / 2 * 4
-----------------------
* * 4 / 5 3 * / 1 8 2
* * * / 8 * 4 / * * *
8 * 5 / 1 2 * / 4 * *
-----------------------
6 * 1 / * * 5 / 3 * *
* * * / 6 * * / 9 * 1
* * 7 / 2 1 * / * 4 6

Thanks!
mediamom99

Posts: 1
Joined: 04 January 2006

### Try one of two possible values

I could not find any obvious continuation. But looking at row 9 and column 7 you find that there are only two possible values: 5 and 8. Try one of these values and you will either get to an invalid sudoku or to the solution. Since I selected 5 I found the solution quite easy.
NicklasE

Posts: 2
Joined: 03 January 2006

I can't see anything straightforward. I'd be interested to hear from anyone who spots a clearer solution.

Code: Select all
`   247       5   28 |  479   4789    1 |    6    379  3789      3    1478    6 |  479  45789    2 |  578   1579  5789     17     178    9 |    3   5678  678 |    2    157     4 --------------------+------------------+------------------     79     679    4 |    5      3  679 |    1      8     2   1279  123679   23 |    8    679    4 |   57  35679  3579      8    3679    5 |    1      2  679 |    4   3679   379 --------------------+------------------+------------------      6    2489    1 |  479   4789    5 |    3     27    78    245    2348  238 |    6    478  378 |    9    257     1     59     389    7 |    2      1  389 |   58      4     6 1. Consider the chain r1c3-2-r1c1-4-r8c1-5-r8c8~5~r3c8-<5|8>-r3c2.When the cell r1c3 contains the value 8, so does the cell r3c2 - a contradiction.Therefore, the cell r1c3 cannot contain the value 8.- The move r1c3:=8 has been eliminated.The value 2 is the only candidate for the cell r1c3.2. The value 3 is the only candidate for the cell r5c3.3. The value 8 is the only candidate for the cell r8c3.4. The values 1 and 2 occupy the cells r5c1 and r5c2 in some order.- The moves r5c1:=7, r5c1:=9, r5c2:=6, r5c2:=7 and r5c2:=9 have been eliminated.Consider the chain r1c5-8-r1c9~8~r7c9-8-r7c5.The cell r7c5 must contain the value 8 if the cell r1c5 doesn't.Therefore, these two cells are the only candidates for the value 8 in Column 5.- The moves r2c5:=8 and r3c5:=8 have been eliminated.Consider the chain r1c9-8-r1c5-8-r7c5-8-r7c9.The cell r7c9 must contain the value 8 if the cell r1c9 doesn't.Therefore, these two cells are the only candidates for the value 8 in Column 9.- The move r2c9:=8 has been eliminated.`

The Almost Locked Set used in the first chain covers the cells {r3c1,r3c2,r3c8}. Then the solver finds an X-Wing in the 8s.

Code: Select all
`   47     5  2 |  479  4789    1 |    6   379  3789     3  1478  6 |  479  4579    2 |  578  1579   579    17   178  9 |    3   567  678 |    2   157     4 ---------------+-----------------+-----------------    79   679  4 |    5     3  679 |    1     8     2    12    12  3 |    8   679    4 |   57  5679   579     8   679  5 |    1     2  679 |    4  3679   379 ---------------+-----------------+-----------------     6   249  1 |  479  4789    5 |    3    27    78   245   234  8 |    6    47   37 |    9   257     1    59    39  7 |    2     1  389 |   58     4     6 1. Consider the chain r2c2-8-r2c7-8-r9c7-<8|9>-r9c1-<5|1>-r3c1.When the cell r2c2 contains the value 1, so does the cell r3c1 - a contradiction.Therefore, the cell r2c2 cannot contain the value 1.- The move r2c2:=1 has been eliminated.The cell r2c8 is the only candidate for the value 1 in Row 2.2. The values 3, 6 and 9 occupy the cells r1c8, r5c8 and r6c8 in some order.- The moves r1c8:=7, r5c8:=5, r5c8:=7 and r6c8:=7 have been eliminated.`

The Almost Locked Set in the link r9c1-<5|1>-r3c1 involves the cells {r3c1,r4c1,r9c1}.

Code: Select all
`   47    5  2 |  479  4789    1 |    6   39  3789     3  478  6 |  479  4579    2 |  578    1   579    17  178  9 |    3   567  678 |    2   57     4 --------------+-----------------+----------------    79  679  4 |    5     3  679 |    1    8     2    12   12  3 |    8   679    4 |   57   69   579     8  679  5 |    1     2  679 |    4  369   379 --------------+-----------------+----------------     6  249  1 |  479  4789    5 |    3   27    78   245  234  8 |    6    47   37 |    9  257     1    59   39  7 |    2     1  389 |   58    4     6 1. Consider the chain r2c7-8-r9c7-<5|7>-r7c9=7=r3c8.When the cell r2c7 contains the value 7, so does the cell r3c8 - a contradiction.Therefore, the cell r2c7 cannot contain the value 7.- The move r2c7:=7 has been eliminated.The cell r5c7 is the only candidate for the value 7 in Column 7.2. The cell r5c9 is the only candidate for the value 5 in Row 5.3. The value 7 in Column 6 must lie in Box 5.- The moves r3c6:=7 and r8c6:=7 have been eliminated.The value 3 is the only candidate for the cell r8c6.4. The cell r9c2 is the only candidate for the value 3 in Row 9.`

The Almost Locked Set used in the chain here is trivial, i.e.
r9c7=8 => r7c9=7 => (r7c8 and r8c8)<>7 => r3c8=7

Code: Select all
`   47    5  2 |  479  4789    1 |   6   39  3789     3  478  6 |  479  4579    2 |  58    1    79    17  178  9 |    3   567   68 |   2   57     4 --------------+-----------------+---------------    79  679  4 |    5     3  679 |   1    8     2    12   12  3 |    8    69    4 |   7   69     5     8  679  5 |    1     2  679 |   4  369    39 --------------+-----------------+---------------     6  249  1 |  479  4789    5 |   3   27    78   245   24  8 |    6    47    3 |   9  257     1    59    3  7 |    2     1   89 |  58    4     6 1. Consider the chain r2c7-8-r2c2-8-r3c2-<8|5>-r3c8.When the cell r2c7 contains the value 5, so does the cell r3c8 - a contradiction.Therefore, the cell r2c7 cannot contain the value 5.- The move r2c7:=5 has been eliminated.The value 8 is the only candidate for the cell r2c7.`

The Almost Locked Set here has already been used - it's {r3c1,r3c2,r3c7} again.

The puzzle is straightforward to solve from here.
rubylips

Posts: 149
Joined: 01 November 2005

Below is as far as I got by hand so far. Not very far and not much hope for anything more.

Are you able to find the Almost Locked Sets and the other complex implication chains you found by hand? Is there a human-implemental algorithm you could describe?

Code: Select all
`  247     5       28      | 479     4789    1       | 6       379     3789      3       1478    6       | 479     45789   2       | 578     1579    5789      17      178     9       | 3       5678    678     | 2       157     4        -------------------------+-------------------------+-------------------------  79      679     4       | 5       3       679     | 1       8       2         1279    123679  23      | 8       679     4       |(57)     35679  x3579      8       3679    5       | 1       2       679     | 4       3679   x379      -------------------------+-------------------------+-------------------------  6       2489    1       | 479     4789    5       | 3       27     (78)       245     2348    238     | 6       478     378     | 9       257     1         59      389     7       | 2       1       389     |(58)     4       6       `

There is an (xy-wing). It eliminates the 7's from both r5c9 and r6c9, marked with an 'x'.

Code: Select all
`  247     5       28      | 479     4789    1       | 6       379     3789      3       1478    6       | 479     45789   2       | 578     1579    5789      17      178     9       | 3       5678   +678     | 2       157     4        -------------------------+-------------------------+-------------------------  79      679     4       | 5       3       679     | 1       8       2         1279    123679  23      | 8      +679     4       | 57      35679   359       8       3679    5       | 1       2       679     | 4      +3679    39       -------------------------+-------------------------+-------------------------  6       2489    1       | 479     4789    5       | 3       27      78        245     2348    238     | 6      -478    -378     | 9      -257     1         59      389     7       | 2       1       389     | 58      4       6       `

There is a Nishio exclusion in 7s.
If r3c6=7, then r5c5=7.
If r5c5=7, then r6c8=7.
There is nowhere left in row 8 to place a 7.
Therefore, r3c6<>7

Code: Select all
`   247     5      -28      | 479     4789    1       | 6       379    +3789      3       1478    6       | 479    +45789   2       | 578     1579    5789      17      178     9       | 3       5678    68      | 2       157     4        -------------------------+-------------------------+-------------------------  79      679     4       | 5       3       679     | 1       8       2         1279    123679  23      | 8       679     4       | 57      35679   359       8       3679    5       | 1       2       679     | 4       3679    39       -------------------------+-------------------------+-------------------------  6       2489    1       | 479     4789    5       | 3       27      78        245     2348   -238     | 6       478    +378     | 9       257     1         59      389     7       | 2       1       389     |+58      4       6       `

There is a Nisho exclusion in 8s.

If (a)r2c5=8, then
(b)r1c9=8, then
(c)r9c7=8

If (a)r2c5=8 AND (b)r9c7=8, then
(c)r8c6=8

There is nowhere left in column 3 to place an 8.
Therefore, r2c5<>8.

Code: Select all
`  247     5       28      | 479     4789    1       | 6       379     3789      3       1478    6       | 479     4579    2       | 578     1579    5789      17      178     9       | 3       5678    68      | 2       157     4        -------------------------+-------------------------+-------------------------  79      679     4       | 5       3       679     | 1       8       2         1279    123679  23      | 8       679     4       | 57      35679   359       8       3679    5       | 1       2       679     | 4       3679    39       -------------------------+-------------------------+-------------------------  6       2489    1       | 479     4789    5       | 3       27      78        245     2348    238     | 6       478     378     | 9       257     1         59      389     7       | 2       1       389     | 58      4       6       `
tso

Posts: 798
Joined: 22 June 2005

### Re: Try one of two possible values

NicklasE wrote:I could not find any obvious continuation. But looking at row 9 and column 7 you find that there are only two possible values: 5 and 8. Try one of these values and you will either get to an invalid sudoku or to the solution. Since I selected 5 I found the solution quite easy.

heh - yep. That's my new technique except for one thing.

When stuck, make a copy of the puzzle. Try a random guess in the copy. If it leads to a solution, the try the other guess to insure there is a unique solution. If you are lucky, however, the first guess will lead to an invalid solution and you can remove a pencilmark and proceed as usual to solve.

Trying pencilmark 8 in cell r9c7 leads to such an invalid solution.

Great. Remove 8 and solve.

Mac
QBasicMac

Posts: 441
Joined: 13 July 2005

Here is my solution:

1. [r3c6]=6=[r3c5]=5=[r2c5]-5-[r2c9]=5=[r5c9]-5-[r5c7]-7-[r5c5]=7=[r4c6|r6c6]-7-[r3c6], => r3c6<>7.

2. [r4c2]=6=[r4c6]-6-[r3c6]-8-[r3c2]=8|5=[r3c8]-5-[r8c8]=5=[r8c1]-5-[r9c1]-9-[r4c1]-7-[r4c2], => r4c2<>7.

3. [r1c3]=2=[r1c1]=4=[r8c1]=5=[r8c8]-5-[r3c8]=5|8=[r3c2]-8-[r1c3]
=> r1c3<>8.

4. X-Wing on "8".

5. [r8c6]=3=[r9c6]-3-[r9c2]-9-[r9c1]=9=[r4c1]=7=[r4c6]-7-[r8c6]
=> r8c6<>7.

6. [r4c6]=7=[r4c1]=9=[r9c1]-9-[r9c6]-8-[r3c6]-6-[r4c6], => r4c6<>6.

7. X-Wing on "9".

8. [r8c1]=5=[r8c8]-5-[r3c8]=5|8=[r3c2]-8-[r3c6]-6-[r3c6]-7-[r4c6]
=7=[r4c1]=9=[r9c1]=5=[r8c1], => r8c1=5 and that solve the puzzle.

Carcul
Carcul

Posts: 724
Joined: 04 November 2005

tso wrote:Are you able to find the Almost Locked Sets and the other complex implication chains you found by hand? Is there a human-implemental algorithm you could describe?

The algorithm first searches for all the single-step links in the candidate grid - strong links, weak links, extended links and links that involve Almost Locked Sets - then attempts to join these links together to form cyclic chains. It continues to look for cyclic chains until it exhausts all possible chains or it finds a chain that, after its associated elimination, leaves just a single candidate for a cell or a sector (i.e. a row, column or box).

I think the algorithm is similar to the procedure described by Jeff, except that most humans probably have to restrict their searches to strong links. The main benefit of computational power is the ability to consider a greater number of link types.

I like to post chains in order that they might be 'shot down' by the more talented human solvers, which enables me to 'improve' (this term is necessarily slightly subjective - some people prefer longer chains made from straightforward link types whereas others prefer shorter chains that involve Almost Locked Sets) the chains the solver presents. For instance, recent work by bennys et al has led me to lean towards shorter, more complicated, chains.
rubylips

Posts: 149
Joined: 01 November 2005

In fact three chains can break it like this:
Code: Select all
`Elide 8 from r7c5 because to fix it forces a chain of inferences via 8@{r7c5} - (r7) - (!8)@{r7c9} - (b9) - 8@{r9c7} - (!5)@{r9c7} - (b9) - 5@{r8c8} - (c8) - (!5)@{r3c8} - (r3) - 5@{r3c5} - (!6)@{r3c5} - (r3) - 6@{r3c6} - (!8)@{r3c6} - (b2) - 8@{r3c5,r2c5,r1c5} to a clash in c5.Elide 8 from r3c6 because to fix it forces a chain of inferences via 8@{r3c6} - (!6)@{r3c6} - (r3) - 6@{r3c5} - (!5)@{r3c5} - (r3) - 5@{r3c8} - (c8) - (!5)@{r8c8} - (r8) - 5@{r8c1} - (!4)@{r8c1} - (c1) - 4@{r1c1} - (!2)@{r1c1} - (r1) - 2@{r1c3} - (!8)@{r1c3} - (c3) - 8@{r8c3} - (r8) - (!8)@{r8c5} - (b8) - 8@{r9c6,r8c6} to a clash in c6.Fix 8 in r7c9 because to elide it forces a chain of inferences via (!8)@{r7c9} - (r7) - 8@{r7c2} - (c2) - (!8)@{r3c2} - (r3) - 8@{r3c5} - (!5)@{r3c5} - (r3) - 5@{r3c8} - (c8) - (!5)@{r8c8} - (b9) - 5@{r9c7} - (!8)@{r9c7} to a clash in b9.`

I'm sure you can all redraft the notation to your own. My program reports inference chains, but finds clashes when building the directed graph of what I call level-1 inferences, which are those where each link in the chain is independent of all other links. So I do not at the moment find cases where, for example, a combination of chains clears more than two entries in a cell. And I haven't finished what I can do at level one yet either.

Also in the original position, there is a very simple loop that looks as though it should have a name and be a recognisable pattern, although it hardly helps in this case.
Code: Select all
`Elide 9 from r5c2 because to fix it forces a chain of inferences via 9@{r5c2} - (!1)@{r5c2} - (r5) - 1@{r5c1} - (c1) - (!1)@{r3c1} - 7@{r3c1} - (c1) - (!7)@{r4c1} - 9@{r4c1} to a clash in b4.`

Pep
Pep

Posts: 12
Joined: 29 November 2005

### Re: Need help with a "diabolical" puzzle!

mediamom99 wrote:I've made it through Easy, Tricky, and Tough, but am having a very hard time with Diabolical! I'm missing something, I'm sure, and would really appreciate some help. Here is the puzzle so far:

* 5 * / * * 1 / 6 * *
3 * 6 / * * 2 / * * *
* * 9 / 3 * * / 2 * 4
-----------------------
* * 4 / 5 3 * / 1 8 2
* * * / 8 * 4 / * * *
8 * 5 / 1 2 * / 4 * *
-----------------------
6 * 1 / * * 5 / 3 * *
* * * / 6 * * / 9 * 1
* * 7 / 2 1 * / * 4 6

Thanks!

I was going to plug this into my program and play it out to see what I could get from it, but two different programs I use show that this is an invalid puzzle.

What was the original source?
dhoffman_98

Posts: 3
Joined: 05 January 2006

### Re: Need help with a "diabolical" puzzle!

dhoffman_98 wrote:I was going to plug this into my program and play it out to see what I could get from it, but two different programs I use show that this is an invalid puzzle.

What was the original source?

What programs did you try? Pappocom certainly won't verify this puzzle but both Sadman and Simple Sudoku confirm there is only one solution. It's too hard for me - I spotted the XY wing r5c7, r7c9 and r9c7 which allowed elimination of 7s in r5c9 and r6c9 but that was all. Sadman and Simple Sudoku also get stuck at this point which (so far in my experience) always means forcing chains or other techniques beyond me are required.
CathyW

Posts: 316
Joined: 20 June 2005

### Re: Need help with a "diabolical" puzzle!

CathyW wrote:
dhoffman_98 wrote:I was going to plug this into my program and play it out to see what I could get from it, but two different programs I use show that this is an invalid puzzle.

What was the original source?

What programs did you try? Pappocom certainly won't verify this puzzle but both Sadman and Simple Sudoku confirm there is only one solution. It's too hard for me - I spotted the XY wing r5c7, r7c9 and r9c7 which allowed elimination of 7s in r5c9 and r6c9 but that was all. Sadman and Simple Sudoku also get stuck at this point which (so far in my experience) always means forcing chains or other techniques beyond me are required.

Pappocom was one that I used. The other was Resco Sudoku for the Pocket PC. They both failed to verify this one as a valid puzzle.

As a disclaimer: These are the only two pieces of software that I have actually tried so far. I'm VERY new to Sudoku (Less than a week and already SEVERELY HOOKED).

I'm looking at this site for examples of what other people run into and ways to think of the logic for working them out. I do pretty well with most of the ones I have done, even the more difficult ones, but I sometimes end up having to do some trial and error. If I understand correctly, most Sudoku's are supposed to be solvable by logic alone and shouldn't need trial and error... does anyone find that to be false?
dhoffman_98

Posts: 3
Joined: 05 January 2006

It is VERY addictive isn't it

As far as I understand it ALL sudokus are solvable with logic alone, but sometimes you get a really, really difficult one - such as the puzzle above - where, for me at least, the technique required is beyond me so T&E is the only way forward. There have been plenty of discussions previously about logic/T&E.
CathyW

Posts: 316
Joined: 20 June 2005

My http://www.axcis.com.au/numbler solver also resorts to T&E for this puzzle.
masb

Posts: 16
Joined: 17 November 2005

Code: Select all
`*--------------------------------------------------------------------------*| 247     5       28     | 479     4789    1      | 6       379     3789   || 3       1478    6      | 479     45789   2      | 578     1579    5789   || 17      178     9      | 3       5678    678    | 2       157     4      ||------------------------+------------------------+------------------------|| 79      679     4      | 5       3       679    | 1       8       2      || 1279    123679  23     | 8       679     4      | 57      35679   3579   || 8       3679    5      | 1       2       679    | 4       3679    379    ||------------------------+------------------------+------------------------|| 6       2489    1      | 479     4789    5      | 3       27      78     || 245     2348    238    | 6       478     378    | 9       257     1      || 59      389     7      | 2       1       389    | 58      4       6      |*--------------------------------------------------------------------------*Eliminating 7 From r5c9 (XY wing)Eliminating 7 From r6c9 (XY wing)*--------------------------------------------------------------------------*| 247     5       28     | 479     4789    1      | 6       379     3789   || 3       1478    6      | 479     45789   2      | 578     1579    5789   || 17      178     9      | 3       5678    678    | 2       157     4      ||------------------------+------------------------+------------------------|| 79      679     4      | 5       3       679    | 1       8       2      || 1279    123679  23     | 8       679     4      | 57      35679   359    || 8       3679    5      | 1       2       679    | 4       3679    39     ||------------------------+------------------------+------------------------|| 6       2489    1      | 479     4789    5      | 3       27      78     || 245     2348    238    | 6       478     378    | 9       257     1      || 59      389     7      | 2       1       389    | 58      4       6      |*--------------------------------------------------------------------------*7 in r7c8 would make placing other 7s impossible (Nishio)*--------------------------------------------------------------------------*| 247     5       28     | 479     4789    1      | 6       379     3789   || 3       1478    6      | 479     45789   2      | 578     1579    5789   || 17      178     9      | 3       5678    678    | 2       157     4      ||------------------------+------------------------+------------------------|| 79      679     4      | 5       3       679    | 1       8       2      || 1279    123679  23     | 8       679     4      | 57      35679   359    || 8       3679    5      | 1       2       679    | 4       3679    39     ||------------------------+------------------------+------------------------|| 6       489     1      | 479     4789    5      | 3       2       78     || 245     2348    238    | 6       478     378    | 9       57      1      || 59      389     7      | 2       1       389    | 58      4       6      |*--------------------------------------------------------------------------*Any Candidate in r3c8 forces r1c3 to have only 2 as valid Candidates (Forcing Chains)Any Candidate in r3c8 forces r3c2 to have only 8 as valid Candidates (Forcing Chains)Any Candidate in r3c8 forces r3c6 to have only 6 as valid Candidates (Forcing Chains)Any Candidate in r3c8 forces r5c3 to have only 3 as valid Candidates (Forcing Chains)Any Candidate in r3c8 forces r8c3 to have only 8 as valid Candidates (Forcing Chains)`

& that solves it

tarek

Posts: 2699
Joined: 05 January 2006

tarek wrote:
7 in r7c8 would make placing other 7s impossible (Nishio)

This does not appear to be a valid Nisio exclusion. If r7c8=7, there are 6 ways to place all the rest of the 7s, for example:

Code: Select all
`*--------------------------------------------------------------------------* | 247     5       28     |+479     4789    1      | 6       379     3789   | | 3       1478    6      | 479     45789   2      | 578     1579   +5789   | |+17      178     9      | 3       5678    678    | 2       157     4      | |------------------------+------------------------+------------------------| | 79      679     4      | 5       3      +679    | 1       8       2      | | 1279    123679  23     | 8       679     4      |+57      35679   359    | | 8      +3679    5      | 1       2       679    | 4       3679    39     | |------------------------+------------------------+------------------------| | 6       2489    1      | 479     4789    5      | 3      +27      78     | | 245     2348    238    | 6      +478     378    | 9       257     1      | | 59      389     7      | 2       1       389    | 58      4       6      | *--------------------------------------------------------------------------* `

dhoffman_98 wrote:I was going to plug this into my program and play it out to see what I could get from it, but two different programs I use show that this is an invalid puzzle.

"Invalid" from Papppocom is an unfortunate misnomer that has lead to much confusion. Puzzles with a single solution are by definition valid.

dhoffman_98 wrote:If I understand correctly, most Sudoku's are supposed to be solvable by logic alone and shouldn't need trial and error... does anyone find that to be false?

All valid Sudokus -- as well as any other similar logic puzzles -- are solvable by logic alone. That doesn't mean that YOU or I or any specific piece of software will always be able to solve it -- only that it is theoretically solvable by logic. In a contest sitution, where speed is an issue, trial and error will often be the quickest way to the solution at a specific point, even on puzzles that aren't the most difficult possible. Also, a mammoth sudoku, say 1000x1000 might be so complex that no computer -- even using the most efficient combination of tactics and brute force searching will not be able to solve it before the Sun novas -- even that puzzle would be technically solvable by logic.

There are also some sudokus that many of us thought were very difficult that now are nearly trivial because of new discoveries -- especially BUG.
tso

Posts: 798
Joined: 22 June 2005

Next