Hard puzzle

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

Hard puzzle

Postby joram » Mon Jun 05, 2006 4:00 pm

Hi,

here is a puzzle from a magazine classified as hard which cannot be solved by Simple Sudoku while SudoCue needs brute force at a certain point. Needless to say that I don't have a clue too...

Here is the original puzzle:

Code: Select all
 *-----------*
 |.5.|...|8.9|
 |..8|...|4..|
 |..4|..3|..6|
 |---+---+---|
 |...|.4.|..2|
 |.4.|279|.5.|
 |6..|.3.|...|
 |---+---+---|
 |8..|6..|1..|
 |..6|...|7..|
 |7.1|...|.6.|
 *-----------*


Here is how far I got:

Code: Select all
*-----------*
|.57|.6.|8.9|
|.68|...|4..|
|.14|..3|5.6|
|---+---+---|
|5.9|.46|3.2|
|143|279|658|
|6.2|.3.|94.|
|---+---+---|
|835|627|194|
|426|...|78.|
|791|...|26.|
*-----------*

 
*-----------------------------------------------------------*
| 23    5     7     | 14    6     124   | 8     123   9     |
| 239   6     8     | 579   159   125   | 4     1237  17    |
| 29    1     4     | 789   89    3     | 5     27    6     |
|-------------------+-------------------+-------------------|
| 5     78    9     | 18    4     6     | 3     17    2     |
| 1     4     3     | 2     7     9     | 6     5     8     |
| 6     78    2     | 158   3     158   | 9     4     17    |
|-------------------+-------------------+-------------------|
| 8     3     5     | 6     2     7     | 1     9     4     |
| 4     2     6     | 359   159   15    | 7     8     35    |
| 7     9     1     | 3458  58    458   | 2     6     35    |
*-----------------------------------------------------------*



Any hints?
joram
 
Posts: 2
Joined: 05 June 2006

Postby tarek » Mon Jun 05, 2006 4:15 pm

I couldn't emulate your candidate grid, however starting form scratch, these seem to be the toughest steps
Code: Select all
*--------------------------------------------------------*
| 23    5     7    |*14    6    #124  | 8    *123   9    |
| 239   6     8    |-1579  159   125  | 4     1237  17   |
| 29    1     4    | 789   89    3    | 5     27    6    |
|------------------+------------------+------------------|
| 5     78    9    |*18    4     6    | 3    *17    2    |
| 1     4     3    | 2     7     9    | 6     5     8    |
| 6     78    2    | 158   3     158  | 9     4     17   |
|------------------+------------------+------------------|
| 8     3     5    | 6     2     7    | 1     9     4    |
| 4     2     6    | 1359  159   15   | 7     8     35   |
| 7     9     1    | 3458  58    458  | 2     6     35   |
*--------------------------------------------------------*
Eliminating 1 From r2c4 (Finned XWing in Rows 1,4 with 1 fin in Box 2)
*--------------------------------------------------------*
| 23    5     7    | 14    6     124  | 8     123   9    |
| 239   6     8    | 579  -159   125  | 4     1237  17   |
| 29    1     4    | 789  *89    3    | 5     27    6    |
|------------------+------------------+------------------|
| 5     78    9    | 18    4     6    | 3     17    2    |
| 1     4     3    | 2     7     9    | 6     5     8    |
| 6     78    2    | 158   3     158  | 9     4     17   |
|------------------+------------------+------------------|
| 8     3     5    | 6     2     7    | 1     9     4    |
| 4     2     6    |-1359 ^159  ^15   | 7     8     35   |
| 7     9     1    |-3458 *58   -458  | 2     6     35   |
*--------------------------------------------------------*
Eliminating 9 from r2c5(ALS-XZ A=589 in r3c5, r9c5 B=159 in r8c6, r8c5  x=5 z=9)
Eliminating 5 from r8c4(ALS-XZ A=589 in r3c5, r9c5 B=159 in r8c6, r8c5  x=9 z=5)
Eliminating 5 from r9c4(ALS-XZ A=589 in r3c5, r9c5 B=159 in r8c6, r8c5  x=9 z=5)
Eliminating 5 from r9c6(ALS-XZ A=589 in r3c5, r9c5 B=159 in r8c6, r8c5  x=9 z=5)


ronk would love the doubley-linked xz...:D

tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby Viggo » Mon Jun 05, 2006 4:26 pm

It is a hard puzzle you have got here, so therefore I think some advanced methods must be used:

You have got a unique rectangle in r89c49 with the candidates 3 and 5.
At the same time the only place for 3 in column 4 is in this rectangle. Therefore neither of r8c4 nor r9c4 can be 5.

Then you have got a discontinuous Nice Loop like this:

[r1c4]=4=[r9c4]=3=[r8c4]=9=[r8c5]=1=[r2c5]-1-[r1c4] => r1c4<>1 => r1c4=4

Then the rest is simple.

/Viggo
Viggo
 
Posts: 60
Joined: 21 April 2006

Postby QBasicMac » Tue Jun 06, 2006 12:31 am

Easy puzzle!

You somehow eliminated a 1 in r8c4 that I couldn't. Otherwise, we get to the same point.

I copied the puzzle and in one copy set r9c9=3 and the other r9c9=5.

5 led easily in an invalid puzzle.
3 led easily to a solution.

Conclusion r9=3 and the puzzle is solved.

Mac
Last edited by QBasicMac on Mon Jun 05, 2006 10:43 pm, edited 1 time in total.
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Postby ronk » Tue Jun 06, 2006 1:55 am

tarek wrote:
Code: Select all
*--------------------------------------------------------*
| 23    5     7    | 14    6     124  | 8     123   9    |
| 239   6     8    | 579  -159   125  | 4     1237  17   |
| 29    1     4    | 789  *89    3    | 5     27    6    |
|------------------+------------------+------------------|
| 5     78    9    | 18    4     6    | 3     17    2    |
| 1     4     3    | 2     7     9    | 6     5     8    |
| 6     78    2    | 158   3     158  | 9     4     17   |
|------------------+------------------+------------------|
| 8     3     5    | 6     2     7    | 1     9     4    |
| 4     2     6    |-1359 ^159  ^15   | 7     8     35   |
| 7     9     1    |-3458 *58   -458  | 2     6     35   |
*--------------------------------------------------------*
Eliminating 9 from r2c5(ALS-XZ A=589 in r3c5, r9c5 B=159 in r8c6, r8c5  x=5 z=9)
Eliminating 5 from r8c4(ALS-XZ A=589 in r3c5, r9c5 B=159 in r8c6, r8c5  x=9 z=5)
Eliminating 5 from r9c4(ALS-XZ A=589 in r3c5, r9c5 B=159 in r8c6, r8c5  x=9 z=5)
Eliminating 5 from r9c6(ALS-XZ A=589 in r3c5, r9c5 B=159 in r8c6, r8c5  x=9 z=5)

ronk would love the doubley-linked xz...:D

I love it, I love it.:D That's the first doubly-linked ALS xz-rule I've noticed that could be constructed three different ways with the same cells.
  • A={r3c5,r9c5}={589}, B={r8c5,r8c6}={159}; x,z and z,x=5,9 (as you posted)
  • A={r3c5,r8c5,r9c5}={1589}, B={r8c6}={15}; x,z and z,x=1,5
  • A={r3c5}={89}, B={r8c5,r8c6,r9c5}={1589}; x,z and z,x=8,9
As you might surmise, each construction yields the same exclusions ... which suggests you could improve your implementation by picking up the exclusion r8c4<>1. In your construction, digit 1 is locked in set B due to the doubly-linked sets. The same thing is true for digit 8 in set A, but there aren't any 8s available in c5.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Tue Jun 06, 2006 3:32 am

Everything is relative. Each of the following cells contains two values. Chose any cell and value on the left and you can solve the puzzle with a cascade of singles. Chose the companion value and it leads to a easy contradiction.
Code: Select all
r3c1    =  9     [r3c1]=2 => [r9c5]=EMPTY
r3c5    =  8     [r3c5]=9 => [r4c8]=EMPTY
r3c8    =  2     [r3c8]=7 => [r9c5]=EMPTY
r8c9    =  5     [r8c9]=3 => [r4c8]=EMPTY
r9c5    =  5     [r9c5]=8 => [r4c8]=EMPTY
r9c9    =  3     [r9c9]=5 => [r4c8]=EMPTY

I sure wish there was an elegant technique for uncovering these pairs.
Last edited by daj95376 on Wed Sep 13, 2006 5:38 am, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Another Solution

Postby Carcul » Tue Jun 06, 2006 9:32 am

Daj95376 wrote:I sure wish there was an elegant technique for uncovering these pairs.


Here it is for r3c8:

Code: Select all
 *-----------------------------------------------------------*
 | 23    5     7     | 14    6     124   | 8     123   9     |
 | 239   6     8     | 1579  159   125   | 4     1237  17    |
 | 29    1     4     | 789   89    3     | 5     27    6     |
 |-------------------+-------------------+-------------------|
 | 5     78    9     | 18    4     6     | 3     17    2     |
 | 1     4     3     | 2     7     9     | 6     5     8     |
 | 6     78    2     | 158   3     158   | 9     4     17    |
 |-------------------+-------------------+-------------------|
 | 8     3     5     | 6     2     7     | 1     9     4     |
 | 4     2     6     | 1359  159   15    | 7     8     35    |
 | 7     9     1     | 3458  58    458   | 2     6     35    |
 *-----------------------------------------------------------*

We have an Almost Nice Loop in cells {r6c246|r9c56|r1c468|r8c6|r3c45|
|r4c24} if r1c8 is not "1":

[r3c8]-7-[r2c9]-1-[r1c8]-{Nice Loop: [r6c2](-8-[r6c4])-8-[r6c6]=8=[r9c6]
=4=[r1c6]=1=[r1c4]-1-[r6c4]-5-[r6c6]-1-[r8c6]-5-[r9c5]-8-[r3c5]=8=
[r3c4]-8-[r4c4]=8=[r4c2]-8-[r6c2]}-8-[r6c2]-7-[r6c9]=7=[r4c8]-7-[r3c8],

which implies that r3c8<>7 and that solves the puzzle.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby joram » Tue Jun 06, 2006 10:40 am

Thanks for the answers. I will be trying to understand the suggestions.
For now I used the only one I understand yet which is the one which looks like trial & error for me and was posted by QBasicMac and daj95376.
After excluding 5 from r9c9 the puzzle solves easily.
joram
 
Posts: 2
Joined: 05 June 2006

Postby Neunmalneun » Tue Jun 06, 2006 11:18 am

There is an easy solution by applying the rule "If a cell contains the candidates 'abc' and 'ab' leads to 'a' > 'b' is wrong in any case" (because if 'c' is right 'b' is wrong too)

R3C4 has the candidates 789. Assuming it had only the pair 89 > R3C8= 7 > R4C8=1 > R4C4=8 > R3C4 cannot be 8. This leaves the single 8 in R3C5 which solves the rest easily.
Neunmalneun
 
Posts: 52
Joined: 22 December 2005

Postby ronk » Tue Jun 06, 2006 11:39 am

Neunmalneun wrote:There is an easy solution by applying the rule "If a cell contains the candidates 'abc' and 'ab' leads to 'a' > 'b' is wrong in any case" (because if 'c' is right 'b' is wrong too)

R3C4 has the candidates 789. Assuming it had only the pair 89 > R3C8= 7 > R4C8=1 > R4C4=8 > R3C4 cannot be 8.

How is that better than just saying ... Assuming R3C4 had only the single 8 > R3C5=9 > R3C1=2 > R3C8= 7 > R4C8=1 > R4C4=8 > R3C4 cannot be 8?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Tue Jun 06, 2006 12:09 pm

ronk wrote:How is that better than just saying ... Assuming R3C4 had only the single 8 > R3C5=9 > R3C1=2 > R3C8= 7 > R4C8=1 > R4C4=8 > R3C4 cannot be 8?

Its a matter of taste.
Neunmalneuns way only needs the strong link in 7 in row 3, not the bivalue cells 89 in r3c5 and 29 in r3c1.
Denoted as
[r3c4]=7=[r3c8]-7-[r4c8]-1-[r4c4]-8-[r3c4] => r3c4<>8
you can see, that this is the shortest solution in this thread (needing only 4 cells).
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Neunmalneun » Tue Jun 06, 2006 12:29 pm

Ronk, you are right of course. Assuming the right candidate for elimination is certainly better than assuming only the half of the truth. As Ravel pointed out it's a matter of taste. But it is also a matter of your own skills or of the logical simplicity that lies in the next steps. For me it is much more easier to see a pattern (for consequential exclusions) if I assume a cell to contain only a pair (preferably leading to two identical pairs in one unit or - even better - to an AUR). Without the 89-pair I would not have seen the much more elegant solution Ravel saw in row 3.

In other words: some of us know where the key is, some of us - like me - have to check every drawer before they find it.
Neunmalneun
 
Posts: 52
Joined: 22 December 2005

Postby tarek » Tue Jun 06, 2006 3:31 pm

ronk wrote:As you might surmise, each construction yields the same exclusions ... which suggests you could improve your implementation by picking up the exclusion r8c4<>1. In your construction, digit 1 is locked in set B due to the doubly-linked sets. The same thing is true for digit 8 in set A, but there aren't any 8s available in c5.


I did those in my head, but I didn't program my solver to do that yet, I'm thinking that the best way for these doubly-linked xz & xy rules, is to apply The counting method elimination on them.......

So identify ALSs that POTENTIALLY have an xz or a xy rule & apply counting on them..that should handle the basic rules & any extras

tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby ronk » Tue Jun 06, 2006 3:39 pm

ravel wrote:Neunmalneuns way only needs the strong link in 7 in row 3, not the bivalue cells 89 in r3c5 and 29 in r3c1.

Thanks. I didn't notice the strong link and couldn't figure out why Neunmalneun didn't mention those two cells.

ravel wrote:Denoted as
[r3c4]=7=[r3c8]-7-[r4c8]-1-[r4c4]-8-[r3c4] => r3c4<>8
you can see, that this is the shortest solution in this thread (needing only 4 cells).

Shorter is definitely better. The implication stream "r3c4<>7 -> ... -> r3c4<>8" implying r3c4<>8 still doesn't come natural to me. Always have to stop and mentally add the other half ... r3c4=7 -> r3c4<>8 ... for r3c4<>8 in either case.

Neunmalneun, thanks for your explanation.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA


Return to Help with puzzles and solving techniques