View previous topic :: View next topic 
Author 
Message 
CT Yankee
Joined: 17 Jul 2006 Posts: 11 Location: New England

Posted: Tue Sep 12, 2006 10:24 pm Post subject: Stumped  old krazydad sudoku 


Hi. I'm having trouble with an old sudoku from the Krazydad site. This one's from Super Tough book 50, and it's just labeled #8 so I don't know when it was originally published... But who cares about that, this thing is just plain driving me nuts! Here's the puzzle at the point where I got stuck:
Code: 
....
 79 169 2  19 36 37  4 8 5 
 57 3 56  1679 4 8  2 19 17 
 4 19 8  2 79 5  6 139 137 
:++:
 2 579 59  4 5789 1  358 357 6 
 3 5679 1569  79 5789 2  158 157 4 
 8 457 145  3 57 6  15 2 9 
:++:
 6 2 3  5 1 9  7 4 8 
 59 459 7  8 2 34  1359 6 13 
 1 8 459  67 36 347  359 35 2 
''''

I've looked at it and analyzed it and looked at it some more, and I just don't see anything that would take me any further. Hidden sets, x and xy wings, coloring, fishing, URs  I've tried just about everything I could think of... None of those techniques seem to help. I'm sure I could solve the puzzle easily enough by following long forcing chains, but that's essentially trial and error and I want to solve it with logic. Much as it pains me to do so, I think I have to ask for help with this one. I don't necessarily want the answer handed to me on a platter, but I'd really appreciate it if someone could just give me a hint that points me to the right technique that will crack this open. And if it's a technique I don't know, well, obviously I should know it.
I should add that I do all my sudoku completely by hand, so it's entirely possible that I've screwed up somewhere in making my candidate reductions. But I suspect that that's not the case. I just know there's something totally obvious that's staring me in the face, and I'm not seeing it. I'd really appreciate a hint.
Thanx,
Dave
EDIT: OK, just having the numbers all lined up on the screen made me see almost immediately that focusing on r6c5 allows one to eliminate the 5 from r4c7. This is done through a combination of a UR and a very short forcing chain, depending on whether r6c5 is a 7 (allowing the UR) or a 5. At least I think that's right, anyway. Assuming that's correct, now I have to see if this reduction helps any with the rest of the puzzle... Doesn't look like it does at first glance, but I'll have to study it some more to be sure... 

Back to top 


David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

Posted: Wed Sep 13, 2006 1:02 pm Post subject: A "DIC" will crack it 


Hi, CTYankee! Those Krazydad puzzles are pretty tough, aren't they?
I solved this one with a single "doubleimplication chain"  the chains involve seven different cells, as explained below. Maybe you'll think of this as "trial and error". Maybe not. I'll make it as logical as I can.
Code:  ....
 79* 169 2  19 36 37B  4 8 5 
 57 3 56  1679 4 8  2 19 17 
 4 19 8  2 79AB 5  6 139 137 
:++:
 2 579 59  4 5789 1  358 357 6 
 3 5679 1569  79 5789 2  158 157 4 
 8 457A 145  3 57A 6  15 2 9 
:++:
 6 2 3  5 1 9  7 4 8 
 59 459 7  8 2 34  1359 6 13 
 1 8 459A  67 36 347A  359 35 2 
'''' 
I started my analysis in r1c1. I've marked the two chains of inference "A" and "B" in the grid above.
A. r1c1 = 7 ==> r9c6 = 7 ==> r9c3 = 4 ==> r6c2 = 4 ==> r6c5 = 7 ==> r3c5 = 9
B. r1c1 = 9 ==> r1c6 = 7 ==> r3c5 = 9
So whichever value is placed at r1c1 we must have a "9" at r3c5, and that's enough to crack it wide open.
Oh  I wasn't able to reproduce all your candidate reductions. So the chain I actually found for case B was a bit longer, but led to the same result. I've used the grid you presented for this explanation because it's a little neater with shorter chains.
Just for grins I ran the puzzle through Ruud's "SudoCue" program, which has more solving algorithms than any other solver I'm aware of. It found seven different instances of the "ALS XZ rule" plus one "XY Chain" before placing a "7" and a "9" in the puzzle. If you want me to reproduce that explanation I will, but it's probably quite a bit longer than the "DIC" I presented above, and it apparently concentrates on the same pair of digits. dcb 

Back to top 


CT Yankee
Joined: 17 Jul 2006 Posts: 11 Location: New England

Posted: Wed Sep 13, 2006 10:41 pm Post subject: 


Thanks for the reply. Your solution is, as you surmised, right on the border of what I consider to be a logicbased solution, but it does work and I sure don't see any other way to complete the puzzle. It's nice to know that I wasn't overlooking something obvious after all... At least, I assume I wasn't overlooking anything  if anyone does know of a more elegant way to solve the puzzle, please post your solution and method. I admit I'm not really familiar with the Almost Locked Sets technique that the solver program recommended, perhaps that's something I should read up on.
It's interesting that both you and the solver both focused on r1c1. Almost the very last thing I did before posting the puzzle was to use that exact cell to eliminate 6 and 7 from r1c4 (a relatively straightforward IC). The very last thing I did was to eliminate 1,9 from r2c3 and also 9 from r2c1. Now, I did that very late at night in a extremely sleepdeprived state. Looked at in the cold light of day, I confess I can't seem to duplicate the logic I used, so if those are among the reductions you couldn't duplicate, they're probably just plain wrong.
The REALLY scary thing is that this puzzle wasn't even taken from krazydad's highest sudoku difficulty level. There's a whole category that's even harder still, I think it's called "Insane", and IMO that's what you have to be to want to try and solve one of them. 

Back to top 


Steve R
Joined: 24 Oct 2005 Posts: 289 Location: Birmingham, England

Posted: Thu Sep 14, 2006 12:12 am Post subject: 


Dave
I am not going to enter into a debate about the meaning of "logic based" other than to say that David’s solution seems excellent to me. Several alternatives are nevertheless available.
If an XYwing is acceptable, it may be that an XYchain will also pass muster. In this event, starting from the grid you posted, the elimination of 3 as a candidate for r8c6 by means of r1c6  7 r1c1 9 r8c1 5 r2c1 – 7 r2c9 1 r8c9 also solves the puzzle.
Steve 

Back to top 


CT Yankee
Joined: 17 Jul 2006 Posts: 11 Location: New England

Posted: Thu Sep 14, 2006 12:46 am Post subject: 


Steve R wrote:  Dave
I am not going to enter into a debate about the meaning of "logic based" other than to say that David’s solution seems excellent to me. Several alternatives are nevertheless available.
If an XYwing is acceptable, it may be that an XYchain will also pass muster. In this event, starting from the grid you posted, the elimination of 3 as a candidate for r8c6 by means of r1c6  7 r1c1 9 r8c1 5 r2c1 – 7 r2c9 1 r8c9 also solves the puzzle.
Steve 
I wasn't trying to criticize David's solution, it is indeed an excellent and logical way to solve the puzzle, as is your solution. I have resorted to similar inference chains in the past to solve other very difficult sudoku, and I've always still felt like I was using logic. I apologize if it seemed I was somehow putting down that method of solving. Sometimes, no question it's definitely the best way to go.
I guess it's true that I'm just the slightest bit disappointed that there isn't some esoteric but supremely elegant method that I've never heard of that solves the puzzle in a strange and beautiful manner that I never would have considered... But hey, you can't have everything.
The solutions that have been given are perfectly valid, and I appreciate you both posting them. 

Back to top 


AZ Matt
Joined: 03 Nov 2005 Posts: 63 Location: Hiding under my desk in Phoenix AZ USA

Posted: Thu Sep 14, 2006 5:02 pm Post subject: Hmmm... 


David
Can you give us any insight as to how you "found" the DIC. This is how I determined that the <7> and the <9> were the numbers to be looking at, but I don't think I ever would have discovered the "loop" on the <4> inherent to your DIC.
You can tell there is something going on with the <79> and the <19> because there are 6 cells with those possibilities, and the 4 in boxes 1 and 2 are strongly connected. I looked at the stray <79> and <19> cells to see if there was a "loop," i.e., a number that could affect cells that looped around back to affect cells in boxes 1 or 2, and I see the <7> from the <79> in r4c4 loops around the bottom of box 8; it collects, conveniently a <3> and a <36> locked set in column 5 (boxes 8 and, surprise surprise, 2), and connects again in column 6  r9c6 to r1c6.
So this is a beautiful puzzle, and I am certain I am going to solve it, and I struggled mightily (I spent a lot of time trying to "loop" the <3> through box 9 up to box 3, row 3, but I failed).
So I finally work out your chain, and I smack my forehead. I was right there. But the loop on the <4> from r9c6 to r5c5 is so tenuous. It relies on the observation that the <4> can only fit twice in box 8, box 7, and row 6. It's beautiful, but I think I have met my match (with my admittedly inexplicable way of solving). I'll hope if I just would have kept at it (before I resorted to what to my mind is true trial and error  simply forcing a chain and following it wherever it goes until you spot a contradiction) I would have "gotten it."
Do you have a secret? What do you look for? 

Back to top 


David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

Posted: Thu Sep 14, 2006 10:20 pm Post subject: It's not a secret 


Hi, Matt! It's always nice to hear from you.
No, I don't think I have a secret. I do have a lot of practice with the "DIC" technique  someone_somewhere pointed it out on this forum last November, and I've been using it ever since. Here's what I usually look for.
I generally start by looking at the patterns formed by the various missing digits. What I want is a bivalued cell that will cause a sort of "spiral" to occur when I assign one of the two values in that cell. In other words, if a particular cell has possibilities {a, b} I'm hoping that setting that cell to "a" will determine where all the rest of the "a"s in the puzzle will fit.
I've even started using colors to keep track of this. In my initial analysis of a "DIC" possibility I'll color all the result cells corresponding to "a" blue, and all those corresponding to "b" green. If I can place quite a few "a" and "b" cells and color them this way, it's pretty easy to visualize additional implications of the two base cell assumptions.
Anyway, in this puzzle the "7"s caught my eye because the skeleton of possible "7"s was attractive.
Code:  **
 7? x x  7? x 7?  x x x 
 7? x x  7? x x  x x 7? 
 x x x  x 7? x  x x 7? 
++
 x 7? x  x 7? x  x 7? x 
 x 7? x  7? 7? x  x 7? x 
 x 7? x  x 7? x  x x x 
++
 x x x  x x x  7 x x 
 x x 7  x x x  x x x 
 x x x  7? x 7?  x x x 
** 
Clearly if I place a "7" at r1c1 I'll also have to put a "7" at r9c6, and there will then be only two possibilities in each of box 2 and box 3. So I may be able to place some more of the "7"s by considering the values that are possible in the x'edout cells above.
This is the grid I was looking at.
Code:  **
 79* 169 2  1679 36 37  4 8 5 
 579 3 1569  1679A 4 8  2 19 17 
 4 19 8  2 79 5  6 139 137A 
++
 2 579 59  4 5789 1  358 357 6 
 3 15679 1569  79 5789 2  158 157 4 
 8 1457 145  3 57A 6  15 2 9 
++
 6 2 3  5 1 9  7 4 8 
 59 459 7  8 2 34  1359 6 13 
 1 8 459  67 36 347A  359 35 2 
** 
Now I didn't notice that r9c6 = 7 ==> r9c3 = 4, at least, not right away. What I saw was the ripple effect on bivalued cells in row 9:
r9c6 = 7 ==> r9c4 = 6 ==> r9c5 = 3 ==> r9c8 = 5 ==> r9c7 = 9 ==> r9c3 = 4
It was only after I'd let this sink in for a while that I noticed the shorter way to write the implication. And the next thing I really noticed went like this:
r9c3 = 4 ==> {1, 5} pair in row 6 ==> r6c5 = 7
Of course, with r6c5 = 7 I was able to place two more of the "7"s in the puzzle right away (assuming that r1c1 = 7, of course)  see the letters "A" in the grid above.
I tried, for a little while, to locate the positions of "7" in boxes 4 and 6, but finally gave that up as a bad effort. So then I started chasing the chain that results when r1c1 = 9, with good results:
r1c1 = 9 ==> r3c2 = 1 ==> r1c2 = 6 ==> r1c5 = 3 ==> r1c6 = 7 ==> r3c5 = 9
So if I have a "secret" for finding a "DIC" I guess it's just that I dig into it as deeply as I can, and I try to find "spiral" patterns that will allow one assumption to ripple through the puzzle as far as possible. dcb 

Back to top 


AZ Matt
Joined: 03 Nov 2005 Posts: 63 Location: Hiding under my desk in Phoenix AZ USA

Posted: Fri Sep 15, 2006 3:56 pm Post subject: Cool... 


Thanks David. That was helpful for me, and instructive. "Spiral" is a better word than "loop"  it implies more imagination  and in the future I will look not only for direct links, but for links that expose hidden and naked sets. The <4> in r9c3 was sitting right in front of me, but I didn't have the imagination to follow its lead. I was right that the interplay of boxes 1, 2, and 8 held the key (or a key) to the puzzle, but it was like the <4> was a secret agent you had to send out on a mission to bring home the needed information.
I know  geek. Hey, I like to think of Sudoku as more art than science. I'm a literature major, not an engineer... 

Back to top 


CT Yankee
Joined: 17 Jul 2006 Posts: 11 Location: New England

Posted: Sun Sep 17, 2006 2:36 am Post subject: 


OK, I’ve been reading some old posts in the General Discussion area and I think I understand some things a bit better now. When I made my comments about logic and trial and error, I had no idea that entire flame wars had already been fought in the sudoku community over the issue. I can see now how I might have offended some people with my casually arrogant assertion that this is what I consider to be logic while that isn’t logic at all. My apologies, this is actually a deep and complex topic and I shouldn’t have just made my pronouncements as if I knew everything there was to know. The truth is that I hadn’t really given the matter much thought. Just reading David’s excellent post above has changed my thinking quite a bit. I now agree completely that looking for and working with long inference chains can be 100% purely logical, as long as you are following a logically thoughtout strategy and don’t just pick cells randomly.
David, your method of seeking out the best targets for a forcing chain seems to work quite well. In fact I believe I've stumbled upon a good example grid that works well as a very simple proofofconcept. This is an old newspaper puzzle, the Universal Syndicate from August 12, that I'd started to work on while on vacation but had put aside upon reaching an impasse. I happened to pick it up again recently, and this time I made a deliberate effort to implement a logical strategy rather than just searching randomly for possible attacks. Almost immediately I realized that there is one truly elegant move available that relies on nothing more advanced than knowledge of strong links, but which cracks the puzzle wide open through the removal of a single candidate. Can you spot it?
Code: 
....
 7 69 569  8 45 1  346 2 346 
 15 3 2  49 459 6  48 7 18 
 16 4 8  3 2 7  9 16 5 
:++:
 8 1 346  46 7 9  346 5 2 
 3456 69 34569 2 46 8  7 134 19 
 2 7 469  5 1 3  468 46 89 
:++:
 9 2 7  1 36 4  5 8 36 
 346 5 346  7 8 2  1 9 346 
 346 8 1  69 369 5  2 346 7 
''''

Looking at the puzzle, there are a number of features that stand out, particularly the large number of cells containing 346, but there is one thing that is literally staring you in the face. I used David’s strategy and asked, “What cell is likely to be a good target?”, and immediately the conjugates in the center box caught my eye. I reasoned that cells in the center box are likely to be open to more lines of attack then a cell on the periphery, and indeed in this case the central cell stands out, as it has open avenues of attack on all 4 sides. Furthermore, its values are ideal, you can see that solving for this cell will almost certainly lead to swift completion of the rest of the puzzle  a process I think of as “crystallization”, which is my term for what happens when a certain critical mass of solved cells has been reached and the puzzle suddenly falls into place, one solved value forcing the next until the whole grid is in a solved state, very much along the lines of the “spirals” described by David above. In this case, the move that will begin to effect this phasechange is the removal of a 5 from r1c3. This is basically another bifurcated implication chain attack, one that attacks the center cell via very short and elegant 2cell chains that attack symmetrically around the corners of a square. You can see that because of the strongly linked 9s in row 1, placing a 5 in r1c3 forces: r1c3=5 –> r1c2=9 –> r5c2=6 –> r5c5=4, while the other arm of the attack goes: r1c2=5 –> r1c5=4 –> r5c5=6 ...and a contradiction is quickly reached! So r1c3 cannot hold a 5, and its removal generates not one but two separate conjugate pairs (naked doubles) in row 1 of 69s and 34s, which force the remaining cell r1c5 to the value 5. From there, the naked pair in box 3 should make the rest of the puzzle relatively easy, and that’s without even considering the newly formed Unique Rectangle in boxes 1 and 4...
I really felt good about finding this attack. It's a beautiful and completely logical move, and I might never have spotted it if I hadn't read David's post and changed my thinking a bit about how to approach a seemingly logicproof grid. There is just no way you can call this kind of thing trial and error. 

Back to top 




You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
