Another KrazyDad Stumper

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

Another KrazyDad Stumper

Postby EnderGT » Tue Mar 25, 2008 9:41 pm

I'm stuck.. I know the final answer, but I'm at a loss for how to get there.

Rated as "Super Tough" by KrazyDad.

Anyone want to give it a go?

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



Stuck State:
Code: Select all
7     156   456   | 2     458   16    | 3     458   9
19    3     45    | 458   7     19    | 2     48    6
269   269   8     | 3     45    69    | 14    7     15
------------------+-------------------+----------------
3     2678  267   | 178   9     4     | 5     26    128   
689   4     5679  | 157   258   27    | 169   3     18
289   2589  1     | 58    6     3     | 49    249    7
------------------+-------------------+----------------
18    18    69    | 469   24    5     | 7     269   3
4     679   3     | 679   1     27    | 8     2569  25
5     2679  2679  | 679   3     8     | 69    1     4
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby ncantoral » Wed Mar 26, 2008 3:01 am

Code: Select all
   |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9--
-----------------------------------------------------------------------------
r1 |     7 |   156 |   456 ||     2 |   458 |   146 ||     3 |  1458 |     9
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r2 |    19 |     3 |   459 || 14589 |     7 |   149 ||     2 |  1458 |     6
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r3 |   269 |   269 |     8 ||     3 |    45 |    69 ||    14 |     7 |    15
===========================||=======================||=======================
r4 |     3 |  2678 |   267 ||  1478 |     9 |  1247 ||     5 |  1246 |   128
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r5 |  2689 |     4 | 25679 ||  1578 |   258 |   127 ||  1689 |     3 |   128
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r6 |   289 |  2589 |     1 ||   458 |     6 |     3 ||   489 |   249 |     7
===========================||=======================||=======================
r7 | 12689 | 12689 |   269 ||   469 |    24 |     5 ||     7 |  1269 |     3
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r8 |     4 |  2679 |     3 ||   679 |     1 |   279 ||   689 |  2569 |   258
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r9 |     5 | 12679 |  2679 ||   679 |     3 |     8 ||   169 |  1269 |     4
.............................................................................


i am goin to take the first advanced move as a finned swordfish on 2
ncantoral
 
Posts: 26
Joined: 18 October 2007

Postby EnderGT » Wed Mar 26, 2008 7:56 pm

ncantoral wrote:i am goin to take the first advanced move as a finned swordfish on 2


I wouldn't even begin to know how to look for that...

I ended up making a few reductions based on some long convoluted chains that I'm not going to try to document. A few more implication chains, forcing chains, probably nice loops, etc and I finally got it reduced down and solved to my satisfaction (without using any step that could be thought of as a guess).

Wow, that was hard. on to the next one.


Edit:

Ok, just looked up Finned Fish, and I think I can see how to apply this in the future. Edit 2: I don't, however, see it in this puzzle. Could you point it out? Thanks. Edit 3: I see that you used the state before I found a few additional reductions - the hidden pair in R7C1,2 and the box claim in R9C2,3 I think spoil the opportunity for the fish.

That's the best part of this board - learning these new techniques.

Thanks for the help.
EnderGT
 
Posts: 69
Joined: 19 February 2008

Re: Another KrazyDad Stumper

Postby hobiwan » Wed Mar 26, 2008 9:34 pm

EnderGT wrote:Stuck State:
Code: Select all
7     156   456   | 2     458   16    | 3     458   9
19    3     45    | 458   7     19    | 2     48    6
269   269   8     | 3     45    69    | 14    7     15
------------------+-------------------+----------------
3     2678  267   | 178   9     4     | 5     26    128   
689   4     5679  | 157   258   27    | 169   3     18
289   2589  1     | 58    6     3     | 49    249    7
------------------+-------------------+----------------
18    18    69    | 469   24    5     | 7     269   3
4     679   3     | 679   1     27    | 8     2569  25
5     2679  2679  | 679   3     8     | 69    1     4


In the above state you can find a rather easy move:
Skyscraper: 5 in [r2c3],[r6c2] (connected through [r26c4]) => [r1c2],[r5c3]<>5

The rest is really tough...
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Re: Another KrazyDad Stumper

Postby EnderGT » Thu Mar 27, 2008 2:50 am

hobiwan wrote:
EnderGT wrote:Stuck State:
Code: Select all
7     156   456   | 2     458   16    | 3     458   9
19    3     45    | 458   7     19    | 2     48    6
269   269   8     | 3     45    69    | 14    7     15
------------------+-------------------+----------------
3     2678  267   | 178   9     4     | 5     26    128   
689   4     5679  | 157   258   27    | 169   3     18
289   2589  1     | 58    6     3     | 49    249    7
------------------+-------------------+----------------
18    18    69    | 469   24    5     | 7     269   3
4     679   3     | 679   1     27    | 8     2569  25
5     2679  2679  | 679   3     8     | 69    1     4


In the above state you can find a rather easy move:
Skyscraper: 5 in [r2c3],[r6c2] (connected through [r26c4]) => [r1c2],[r5c3]<>5

The rest is really tough...


skyscraper... that's a new one for me, I'll have to read about that tomorrow. Thanks.

Edit: Couldn't wait until tomorrow. Doesn't the 5 in R5C4 prevent it from being the skyscraper pattern? Edit 2: never mind, I see it now. Thanks!
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby Draco » Fri Mar 28, 2008 1:04 am

Using my solver (which only handles the simpler mutant fish) and working from your PM's:

First a forcing chain: r2c3=5=r2c4 and r2c3-5-r5c3=5=r6c2, which force r6c4<>5, creating some singletons we can harvest. These in turn lead to an open pair in r1, which finally leave us with:

Code: Select all
7   16   45   | 2   8  16 | 3   45   9 
19  3    45   | 45  7  19 | 2   8    6 
269 269  8    | 3   45 69 | 14  7    15
--------------+-----------+-------------
3   2678 267  | 17  9  4  | 5   26   128
689 4    679  | 157 25 27 | 169 3    18
29  5    1    | 8   6  3  | 49  249  7 
--------------+-----------+-------------
18  18   69   | 469 24 5  | 7   269  3 
4   679  3    | 679 1  27 | 8   2569 25
5   2679 2679 | 679 3  8  | 69  1    4 



Time for another chain: r3c6-6-r3c1=6=r5c1 and r3c6-9-r2c6=9=r2c1, which force r5c1<>9. And then a forcing net (but a rather neat one): r5c5-2-r7c5=2=r8c6, (picking up at r7c5 again) r7c5=2=r7c8=6=r4c8. Then a single chain to complete the force: r5c5-5-r3c5=5=r3c9=2=r8c9=5=r8c8. This leads to r8c8<>2,6.

Another chain: r7c3-6-r7c8=6=r4c8 (which using colors on 6's also forces r9c7=6) and r7c3-9-r5c3=9=r6c1 (which, using colors on 9, also forces r5c7=9) Sorry if the notation is a little odd, but I couldn't figure out how to show these using ALS alone. This leads to r5c7<>6, r9c7<>9, and Singletons plus a locked set in c8. We now have:

Code: Select all
7   16  45  | 2   8  16 | 3  45 9 
19  3   45  | 45  7  19 | 2  8  6 
269 269 8   | 3   45 69 | 14 7  15
------------+-----------+----------
3   278 27  | 17  9  4  | 5  6  128
68  4   679 | 157 25 27 | 19 3  18
29  5   1   | 8   6  3  | 49 24 7 
------------+-----------+----------
18  18  69  | 469 24 5  | 7  29 3 
4   679 3   | 679 1  27 | 8  59 25
5   279 279 | 79  3  8  | 6  1  4 


Hang on for one last triple forcing chain that will break the puzzle. Starting with r1c2-6-r3c1=6=r7c3, and similarly r1c2=1=r7c2=8=r3c2. The second bivalue shows us r1c2-1-r2c1-9-r6c1=9=r5c3. This very nicely knocks out 3 important values: r4c2<>2, r5c3<>6, and r7c3<>9.


Several more singletons fall out for at this point, along with a locked set in C3 and an XY-Wing (centered on r9c3). SSTS.

[edit -- fixed r7c3 chain]
Draco
 
Posts: 143
Joined: 14 March 2008

Postby eleven » Fri Mar 28, 2008 1:10 pm

EnderGT, you already had made the hard part. How e.g. could you place the 4 in r4c6 and 1 in r9c8, and eliminate 5 in r2c8 ?

From your grid after Draco's kite only one chain is needed:

Code: Select all
7   16   45   | 2   8  16 | 3   45   9
19  3    45   | 45  7  19 | 2   8    6
269 269  8    | 3   45 69 | 14  7    15
--------------+-----------+-------------
3   2678 267  | 17  9  4  | 5   26   128
689 4    679  | 157 25 27 | 169 3    18
29  5    1    | 8   6  3  | 49  249  7
--------------+-----------+-------------
18  18   69   | 469 24 5  | 7   269  3
4   679  3    | 679 1  27 | 8   2569 25
5   2679 2679 | 679 3  8  | 69  1    4

There is a xyz-wing 269 in r47c8 and r9c7, which eliminates 6 in r8c8. Then

Either r1c2=6 or r1c2=1 -> r2c1=9 -> r5c3=9 -> r7c3=6, i.e. r89c2<>6

It can be solved then with a w-wing 69 and a xy-wing 279.
eleven
 
Posts: 1578
Joined: 10 February 2008

Postby EnderGT » Fri Mar 28, 2008 2:15 pm

eleven wrote:EnderGT, you already had made the hard part. How e.g. could you place the 4 in r4c6 and 1 in r9c8, and eliminate 5 in r2c8 ?


Basically my approach is to pick a bivalue cell and see where each value takes me. If both values lead to some other cell having the same value, then that must be the correct value for that cell. Likewise, if both values lead to a candidate being locked into two cells, then any other cells that see those two can have that candidate removed.

Specifically for this puzzle, I used R7C5 as my bivalue. This forced the 4 in R4C6, the 8 in R8C7, and the 1 in R9C8. It also locked the 5 b3 into either R1C8 or R3C9, which means I can remove the 5 from R2C8.

I'm not sure if there's a name for this approach, but it worked.
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby eleven » Fri Mar 28, 2008 2:40 pm

Maybe multidigit coloring. I dont really like this method. The reason you can see here:
If i set R5C7=4, it solves with singles.

Btw if i set it to 2, i need a xy-wing and a kite to get 1 in r9c8.
eleven
 
Posts: 1578
Joined: 10 February 2008

Postby EnderGT » Fri Mar 28, 2008 3:33 pm

eleven wrote:Maybe multidigit coloring. I dont really like this method. The reason you can see here:
If i set R5C7=4, it solves with singles.

Btw if i set it to 2, i need a xy-wing and a kite to get 1 in r9c8.


I think you meant R7C5? And yes, I don't like it either, but it works when I can't find anything else.

Also, what's a kite? another one for me to go look up...
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby daj95376 » Fri Mar 28, 2008 4:45 pm

EnderGT,

I first encountered your approach in an old post in the Programmers Forum. I believe it was called a Double Implication Chain. Since then, names have changed and Double Implication Chain has a new definition (I believe). Now, I think your approach falls under the catch-all heading of forcing chain. (others will probably post a more accurate name soon.)

Anyway, I use a similar approach as my last-stop way of getting past what I can't solve otherwise -- of which I have many missing techniques. In my implementation, I look for common assignments/eliminations along the two paths. That's basically equivalent to what you described. However, I also check paths from mulit-value cells.

Yes, there is a philosophical issue about using a cell when one of the candidates results in the puzzle being solved with singles. I've been debating limiting the length of the paths -- say to 10 nodes. This way, commonality between the two paths is limited to something I can reasonably list in a solution.

Finally, I hope you aren't making the same mistake that I made in implementing this technique. I didn't understand the distinction between a chain and a network, and my solver uses networks instead of chains. Now, I have to manually examine my solver's output and only select the results that can be expressed as chains. I've yet to implement chains in my new solver.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby EnderGT » Fri Mar 28, 2008 6:32 pm

daj95376 wrote:EnderGT,

I first encountered your approach in an old post in the Programmers Forum. I believe it was called a Double Implication Chain. Since then, names have changed and Double Implication Chain has a new definition (I believe). Now, I think your approach falls under the catch-all heading of forcing chain. (others will probably post a more accurate name soon.)

Anyway, I use a similar approach as my last-stop way of getting past what I can't solve otherwise -- of which I have many missing techniques. In my implementation, I look for common assignments/eliminations along the two paths. That's basically equivalent to what you described. However, I also check paths from mulit-value cells.

Yes, there is a philosophical issue about using a cell when one of the candidates results in the puzzle being solved with singles. I've been debating limiting the length of the paths -- say to 10 nodes. This way, commonality between the two paths is limited to something I can reasonably list in a solution.

Finally, I hope you aren't making the same mistake that I made in implementing this technique. I didn't understand the distinction between a chain and a network, and my solver uses networks instead of chains. Now, I have to manually examine my solver's output and only select the results that can be expressed as chains. I've yet to implement chains in my new solver.


Before a few weeks ago, I considered myself a pretty good sudoku solver. I could spot hidden pairs, triples, even quads. I understood box claims and virtual crosshatching, and could solve most puzzles rated as hard in common publications.

Then I discovered a few puzzle sources that made it clear to me that I was just beginning to learn how to solve sudoku.

In the past few weeks, I've gotten comfortable with normal Fish, XY-Wing, XYZ-Wing, XY-Chains, and some uniqueness methods such as BUG.

I have yet to get comfortable with coloring, nice loops, finned fish, ALS, and the more advanced forcing patterns.

I'm using the technique I described earlier simply because I've run out of the options that I know how to look for. I don't understand the difference between a network and a chain, nor do I understand the significance of that difference. I do, however, feel that what I'm doing is brute-forcing it, and that there really should be a more elegant, more logical, way for me to solve these puzzles.

I am not currently implementing a solver. I do all of my puzzles either with pen and paper, or using the paul's pages SudokuXP solver, which I've found to be pretty good.

But enough about me...
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby eleven » Fri Mar 28, 2008 8:04 pm

EnderGT wrote:Also, what's a kite? another one for me to go look up...
There is a good collection of solving techniqes in the "Advanced solving techniques" forum here (especially the one by Mike Barker): http://forum.enjoysudoku.com/viewtopic.php?t=3315.

You can find kites here: http://forum.enjoysudoku.com/viewtopic.php?t=3326

and w-wings here: http://www.dailysudoku.co.uk/sudoku/forums/viewtopic.php?t=2008.

They both have other names also:(
eleven
 
Posts: 1578
Joined: 10 February 2008


Return to Help with puzzles and solving techniques