dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Stumped - old krazydad sudoku

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles
View previous topic :: View next topic  
Author Message
CT Yankee



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

PostPosted: Tue Sep 12, 2006 10:24 pm    Post subject: Stumped - old krazydad sudoku Reply with quote

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
View user's profile Send private message
David Bryant



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

PostPosted: Wed Sep 13, 2006 1:02 pm    Post subject: A "DIC" will crack it Reply with quote

Hi, CTYankee! Those Krazydad puzzles are pretty tough, aren't they?

I solved this one with a single "double-implication 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
View user's profile Send private message Send e-mail Visit poster's website
CT Yankee



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

PostPosted: Wed Sep 13, 2006 10:41 pm    Post subject: Reply with quote

Thanks for the reply. Your solution is, as you surmised, right on the border of what I consider to be a logic-based 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 sleep-deprived 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. Wink
Back to top
View user's profile Send private message
Steve R



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

PostPosted: Thu Sep 14, 2006 12:12 am    Post subject: Reply with quote

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 XY-wing is acceptable, it may be that an XY-chain 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
View user's profile Send private message
CT Yankee



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

PostPosted: Thu Sep 14, 2006 12:46 am    Post subject: Reply with quote

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 XY-wing is acceptable, it may be that an XY-chain 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. Wink

The solutions that have been given are perfectly valid, and I appreciate you both posting them.
Back to top
View user's profile Send private message
AZ Matt



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

PostPosted: Thu Sep 14, 2006 5:02 pm    Post subject: Hmmm... Reply with quote

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
View user's profile Send private message
David Bryant



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

PostPosted: Thu Sep 14, 2006 10:20 pm    Post subject: It's not a secret Reply with quote

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 bi-valued 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'ed-out 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 bi-valued 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
View user's profile Send private message Send e-mail Visit poster's website
AZ Matt



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

PostPosted: Fri Sep 15, 2006 3:56 pm    Post subject: Cool... Reply with quote

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. Idea 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
View user's profile Send private message
CT Yankee



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

PostPosted: Sun Sep 17, 2006 2:36 am    Post subject: Reply with quote

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 thought-out 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 proof-of-concept. 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 phase-change 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 2-cell 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 logic-proof grid. There is just no way you can call this kind of thing trial and error.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles All times are GMT
Page 1 of 1

 
Jump to:  
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