The New Sudoku Players' Forum

by **mediamom99** » Wed Jan 04, 2006 5:40 pm

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!

by **NicklasE** » Wed Jan 04, 2006 8:52 pm

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.

by **rubylips** » Wed Jan 04, 2006 10:28 pm

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.

by **tso** » Thu Jan 05, 2006 12:18 am

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

by **QBasicMac** » Thu Jan 05, 2006 3:15 am

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

by **Carcul** » Thu Jan 05, 2006 11:04 am

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

by **rubylips** » Thu Jan 05, 2006 12:28 pm

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.

by **Pep** » Thu Jan 05, 2006 7:16 pm

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

by **dhoffman_98** » Thu Jan 05, 2006 9:15 pm

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?

by **CathyW** » Thu Jan 05, 2006 9:42 pm

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.

by **dhoffman_98** » Thu Jan 05, 2006 10:40 pm

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?

by **CathyW** » Thu Jan 05, 2006 10:48 pm

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.

by **masb** » Fri Jan 06, 2006 12:01 am

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

by **tarek** » Fri Jan 06, 2006 12:38 am

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

by **tso** » Fri Jan 06, 2006 2:27 am

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.

The New Sudoku Players' Forum

Need help with a "diabolical" puzzle!

Need help with a "diabolical" puzzle!

Try one of two possible values

Re: Try one of two possible values

Re: Need help with a "diabolical" puzzle!

Re: Need help with a "diabolical" puzzle!

Re: Need help with a "diabolical" puzzle!