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 

Stuck

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



Joined: 12 Feb 2006
Posts: 5157
Location: Rochester, NY, USA

PostPosted: Mon Mar 13, 2006 1:28 am    Post subject: Stuck Reply with quote

This is one I think I should have solved, based on previous puzzles with the same rating from the same source. The first time I solved all but four cells, but they formed a rectangle and all four contained the same pair. I figured the odds were much greater that I had made an error rather than this being a non-unique puzzle. The second time I reached an impasse much earlier. A unique rectangle and X-Wing were of minimal help.

Code:
-------------------------------------------------
|3    2    6    |7    19   4    |89   5    189  |
|149  1459 8    |3    1569 569  |7    16   2    |
|159  7    19   |569  8    2    |4    136  1369 |
-------------------------------------------------
|8    69   3    |2    569  569  |1    7    4    |
|149  1469 5    |8    469  7    |3    2    69   |
|2    469  7    |469  3    1    |569  8    569  |
-------------------------------------------------
|7    35   4    |1    2    56   |568  9    3568 |
|6    1359 2    |459  7    8    |59   134  135  |
|159  8    19   |4569 4569 3    |2    146  7    |
-------------------------------------------------
Back to top
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3164
Location: near Detroit, Michigan, USA

PostPosted: Mon Mar 13, 2006 2:15 am    Post subject: Reply with quote

Marty,

From the position you posted, R8C7 must be <5>. Look at B9.

Then, another <5> is pinned, and then there is an X-wing on <5>.

Keith
Back to top
View user's profile Send private message
Steve R



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

PostPosted: Mon Mar 13, 2006 4:30 am    Post subject: Stuck Reply with quote

Interesting puzzle, Marty.

Is it possible to post the starting grid?

Steve
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5157
Location: Rochester, NY, USA

PostPosted: Mon Mar 13, 2006 5:57 pm    Post subject: Reply with quote

Keith, I'm looking at B9 and can't reason out why r8c7 needs to be a "5".

Steve, the original:

Code:
3-67---5-
---3----2
-7--824--
---2--1-4
--5---3--
2-7--1---
--412--9-
6----8---
-8---32-7
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Thu Mar 16, 2006 2:28 am    Post subject: This one is pretty tough Reply with quote

Hi, Marty!

From the position as you posted it, the reason why r8c7 = 5 should be pretty clear -- you have the possibilities listed as {5, 9}, and there's a "9" at r7c8. Unfortunately, that's not enough to make much of a dent in this very tough puzzle.

Code:
---------------------------------------------------
|3    2    6    |7     19    4    |89   5    189  |
|149  1459 8    |3     1569  569  |7    16   2    |
|159  7    19   |569*  8     2    |4    136  1369 |
---------------------------------------------------
|8    69   3    |2     569   569  |1    7    4    |
|149  1469 5    |8     469   7    |3    2    69   |
|2    469  7    |469*  3     1    |69   8    569  |
---------------------------------------------------
|7    35   4    |1     2     56   |68   9    368  |
|6    139  2    |49    7     8    |5    134  13   |
|159  8    19   |4569* 4569  3    |2    146  7    |
---------------------------------------------------


You can reason to the conclusion that r7c6 = 5 as follows.

-- There are only three places to put a "6" in column 4.
-- If r3c4 = 6 then r2c8 = 6, the "6" in box 9 must lie in row 7, and r7c6 <> 6.
-- If r6c4 = 6 then r5c9 = 6, the "6" in box 3 must lie in column 8, r7c7 = 6, and r7c6 <> 6.
-- If r9c4 = 6 then r7c6 <> 6.

So r7c6 = 5, and that should be enough to get you rolling. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
keith



Joined: 19 Sep 2005
Posts: 3164
Location: near Detroit, Michigan, USA

PostPosted: Thu Mar 16, 2006 4:00 am    Post subject: Explanation Reply with quote

Marty,

R8C7 must be <5> because R7C8 is <9>.

And, R6C9 is the only possible <5> in R6 and / or C9.

And, there is an X-wing in C1 and C4 that says R9C5 is not 5.


This clarifies the position you posted, but by no means solves the puzzle. See David's message for a hint on further progress.

Keith
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5157
Location: Rochester, NY, USA

PostPosted: Thu Mar 16, 2006 6:28 pm    Post subject: Reply with quote

As always, thanks to both of you. I don't know how I could stare at that puzzle and not see the "9" in r7c8.

Quote:
And, there is an X-wing in C1 and C4 that says R9C5 is not 5.

I can't for the life of me find that X-Wing.

Quote:
You can reason to the conclusion that r7c6 = 5 as follows.

-- There are only three places to put a "6" in column 4.
-- If r3c4 = 6 then r2c8 = 6, the "6" in box 9 must lie in row 7, and r7c6 <> 6.
-- If r6c4 = 6 then r5c9 = 6, the "6" in box 3 must lie in column 8, r7c7 = 6, and r7c6 <> 6.
-- If r9c4 = 6 then r7c6 <> 6.

So r7c6 = 5, and that should be enough to get you rolling. dcb

As I've mentioned before, deductive reasoning is a major weakness. How did you home in on the "6s" in c4 to start that line of reasoning?
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Thu Mar 16, 2006 7:35 pm    Post subject: Spotting "template" patterns Reply with quote

Marty R wrote:
How did you home in on the "6s" in c4 to start that line of reasoning?


Well, it was a combination of luck and experience. Smile

Just to be clear about it, here's what my copy of the puzzle looked like when I had to start hunting real hard.
Code:
-------------------------------------------------
|3    2    6    |7    19   4    |89   5    189  |
|1459 1459 8    |3    1569 569  |7    16   2    |
|159  7    19   |56   8    2    |4    136  1369 |
-------------------------------------------------
|8    69   3    |2    569  569  |1    7    4    |
|149  1469 5    |8    469  7    |3    2    69   |
|2    469  7    |469  3    1    |69   8    5    |
-------------------------------------------------
|7    35   4    |1    2    56   |68   9    368  |
|6    139  2    |49   7    8    |5    134  13   |
|159  8    19   |4569 4569 3    |2    146  7    |
-------------------------------------------------

At this point there are 36 unresolved cells. Not seeing anything obvious, I started concentrating on all the cells that had just two possible candidates. I was hoping to find a "double-implication chain", which often emerges when all else fails. In this case, though, there are only 14 "pairs" among the unresolved cells, and I couldn't find one of those patterns.

Anyway, I was staring at the possible locations for the digit 6 when I noticed that the two cells r4c4 and r6c7 (both of which appear as {5, 6} in the grid) are linked together in such a way that if r4c4 were "6" then r6c7 couldn't be "6". That prompted me to investigate the other possible locations for a "6" in column 4, and voila!

Now that I'm staring at this thing again I notice that a limited form of "Nishio" is possible in this situation. Here's the grid again.
Code:
-------------------------------------------------
|3    2    6    |7    19   4    |89   5    189  |
|1459 1459 8    |3    1569 569  |7    16   2    |
|159  7    19   |56   8    2    |4    136  1369*|
-------------------------------------------------
|8    69   3    |2    569  569  |1    7    4    |
|149  1469 5    |8    469  7    |3    2    69   |
|2    469  7    |469  3    1    |69*  8    5    |
-------------------------------------------------
|7    35   4    |1    2    56*  |68   9    368  |
|6    139  2    |49   7    8    |5    134  13   |
|159  8    19   |4569 4569 3    |2    146* 7    |
-------------------------------------------------

Start by supposing that r7c6 = 6. We reach a contradiction as follows.

-- r7c6 = 6 ==> r9c8 = 6 (only spot left in bottom right 3x3 box)
-- r7c6 = 6 ==> r7c7 = 8 ==> r1c7 = 9 ==> r6c7 = 6.
-- With "6" at r6c7 and r9c8, the only spot left in column 9 is r3c9.

I've marked these cells with asterisks in the grid above. As you can see, it's now impossible to fit a "6" in column 4. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dejsmith



Joined: 23 Oct 2005
Posts: 40

PostPosted: Thu Mar 16, 2006 8:57 pm    Post subject: Slight VAriations Reply with quote

Guys, I am getting pretty good at arriving at contradictions; but my "start hunting real hard" position had a few slight variations that got in the way of following both Keith & David. I had R2C1=1459 & R3C4=569. Notice my R2C1 is the same as David's & blocks Keith's X Wing attempt. However my R3C4 is the same as Marty's & kept me from noticing David's 56 pair combination with R7C6. Perhaps they are not necessary & I am nit picking; but I am trying to understand these small differences.

Thanks...Dave
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Thu Mar 16, 2006 11:55 pm    Post subject: "Coloring" eliminates "9" at r3c4 Reply with quote

Dave Smith wrote:
... my R3C4 is the same as Marty's & kept me from noticing David's 56 pair combination with R7C6.

Hi, Dave! That's a good question.
Code:
-------------------------------------------------
|3    2    6    |7    19   4    |89   5    189  |
|1459 1459 8    |3    1569 569  |7    16   2    |
|159  7    19=  |569  8    2    |4    136  1369 |
-------------------------------------------------
|8    69   3    |2    569  569  |1    7    4    |
|149  1469 5    |8    469  7    |3    2    69   |
|2    469  7    |469  3    1    |69   8    5    |
-------------------------------------------------
|7    35   4    |1    2    56   |68   9    368  |
|6    139+ 2    |49-  7    8    |5    134  13   |
|159  8    19~  |4569 4569 3    |2    146  7    |
-------------------------------------------------

Here's how you can eliminate the "9" at r3c4.

-- If r3c3 = 9 then r3c4 <> 9.
-- If r3c3 <> 9 then r9c3 = 9 (only two spots for a "9" in column 3).
-- But r9c3 = 9 ==> r8c4 = 9 ==> r3c4 <> 9.

In other words, the "connected pairs" in column 3 and in row 8 combine to rule out the possibility of a "9" at r3c4. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
keith



Joined: 19 Sep 2005
Posts: 3164
Location: near Detroit, Michigan, USA

PostPosted: Fri Mar 17, 2006 1:47 am    Post subject: Starting over ... Reply with quote

I went back to the starting position. You can get to this position with basic methods:

Code:


+----------------+----------------+----------------+
| 3    2    6    | 7    19   4    | 89   5    189  |
| 1459 1459 8    | 3    1569 569  | 7    16   2    |
| 159  7    19   | 569  8    2    | 4    136  1369 |
+----------------+----------------+----------------+
| 8    69   3    | 2    569  569  | 1    7    4    |
| 149  1469 5    | 8    469  7    | 3    2    69   |
| 2    469  7    | 469  3    1    | 69   8    5    |
+----------------+----------------+----------------+
| 7    35   4    | 1    2    56   | 68   9    368  |
| 6    139  2    | 49   7    8    | 5    134  13   |
| 159  8    19   | 4569 4569 3    | 2    146  7    |
+----------------+----------------+----------------+



There is a unique rectangle - look at the <19>'s in C3. For uniqueness, either R4C1 or R9C1 is <5>, so R3C1 is not <5>.

Now there is an X-wing on <5> in C1 and C4, so R9C5 cannot be <5>.

Keith
Back to top
View user's profile Send private message
dejsmith



Joined: 23 Oct 2005
Posts: 40

PostPosted: Fri Mar 17, 2006 4:13 am    Post subject: Great Lessons! Reply with quote

Guys, what great lessons! You both have shown me another level of awareness that I need to consider more often. Thanks for your patience.

Dave
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5157
Location: Rochester, NY, USA

PostPosted: Fri Mar 17, 2006 6:18 pm    Post subject: Re: Starting over ... Reply with quote

David, thank you for the explanation. I'm familiar with the term "Nishio", but I wonder if it's really a separate technique. If I understand it correctly, it seems to really be part of a forcing chain. Many times I've done a forcing chain and instead of forcing values in cells, one of the starting points has led to an invalid solution. I think that's what a Nishio is, even though I didn't start out thinking about one.

By the way, is your "double-implication chain" the same as what is often referred to as a "forcing chain"?

keith wrote:
I went back to the starting position. You can get to this position with basic methods:

Code:


+----------------+----------------+----------------+
| 3    2    6    | 7    19   4    | 89   5    189  |
| 1459 1459 8    | 3    1569 569  | 7    16   2    |
| 159  7    19   | 569  8    2    | 4    136  1369 |
+----------------+----------------+----------------+
| 8    69   3    | 2    569  569  | 1    7    4    |
| 149  1469 5    | 8    469  7    | 3    2    69   |
| 2    469  7    | 469  3    1    | 69   8    5    |
+----------------+----------------+----------------+
| 7    35   4    | 1    2    56   | 68   9    368  |
| 6    139  2    | 49   7    8    | 5    134  13   |
| 159  8    19   | 4569 4569 3    | 2    146  7    |
+----------------+----------------+----------------+



There is a unique rectangle - look at the <19>'s in C3. For uniqueness, either R4C1 or R9C1 is <5>, so R3C1 is not <5>.

Now there is an X-wing on <5> in C1 and C4, so R9C5 cannot be <5>.

Keith

Keith, are you off a column? Do you mean R3C1 as part of the rectangle and the "5" precluded from R2C1?

As to the X-Wing in columns 1 and 4: maybe I have a misunderstanding of what an X-Wing is, but I thought a requirement was that the rows involved have no more of the number in question. I.e., each row in the X-Wing can contain only two of the number. So I keep seeing that "5" in R9C5 and thinking that that precludes an X-Wing because of three "5s" in R9.

As usual, I'm in a state of.....CONFUSION.
Back to top
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3164
Location: near Detroit, Michigan, USA

PostPosted: Fri Mar 17, 2006 9:50 pm    Post subject: Reply with quote

Marty,

Quote:


Keith, are you off a column? Do you mean R3C1 as part of the rectangle and the "5" precluded from R2C1?



Yes. Actually, I am off a row.

As I said, the X-wing is in the columns. The possibility <5> occurs only twice in each of C1 and C4, and these possibilities line up in R3 and R9 to form a rectangle. One of the two squares in each row must be <5>, so we can exclude <5> as a possibility in any other squares in these rows.

Marty, the same argument is true if you interchange the words "row" and "column". Or, just rotate the puzzle ninety degrees.

Keith
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Fri Mar 17, 2006 11:57 pm    Post subject: "Nishio" is special Reply with quote

Marty R wrote:
David, thank you for the explanation. I'm familiar with the term "Nishio", but I wonder if it's really a separate technique. If I understand it correctly, it seems to really be part of a forcing chain. Many times I've done a forcing chain and instead of forcing values in cells, one of the starting points has led to an invalid solution. I think that's what a Nishio is, even though I didn't start out thinking about one.

You're welcome, Marty.

"Nishio" is a variety of forcing chain. But it's special. In particular it has a special name because it was invented in Japan, before the sudoku puzzles became wildly popular in the U.K. and in the U.S.A.

Nishio works by showing that a single digit cannot be placed in a particular cell because if that digit is placed in that cell, it will not be possible to place all 9 occurrences of that digit in the puzzle. So Nishio works by concentrating on a single digit.

Forcing chains that end in contradictions may involve more than one digit. Or the contradiction that is reached may involve forcing the same digit to appear twice in the same column, or row, or 3x3 box. These kinds of forcing chains are useful, but they're not "Nishio."
Marty R wrote:
By the way, is your "double-implication chain" the same as what is often referred to as a "forcing chain"?

Well, the term "forcing chain" is generally used to refer to any chain of reasoning that begins by supposing that a certain cell has a particular value.

A "double-implication chain" is a form of forcing chain, but it's also a little bit special. DIC's come in two flavors.

-- The first one -- my favorite flavor -- starts from a cell in which only two digits are possible. Two different chains lead away from this cell, each based on a different assumption about the contents of the starting cell. And the two chains intersect somewhere, demonstrating that a particular value cannot appear in the cell where the two chains intersect.

The simplest form of this flavor DIC is the familiar XY-Wing. Only four cells are involved, and each "chain" has two links in it. A common form of this flavor of DIC is just a little more complicated, involving a third link on one side of the chain.
Code:
.  35   .   .  37   .  57   .   .
.  56   .   .  78   .   .   .  67

This is a "5-star constellation."

-- If r1c2 = 3 then r1c5 = 7, forcing r2c5 = 8.
-- If r1c2 = 5 then r2c2 = 6, forcing r2c9 = 7 and therefore r2c5 = 8.

You can find quite a bit of discussion about this kind of a "DIC" by searching for the word "constellation" in this forum.

-- The second flavor of DIC just tests one value that might occur in the starting cell. It follows two different chains of inference leading away from this cell; those chains intersect somewhere else in the puzzle and contradict each other, thus demonstrating that the assumed starting value is incorrect.

I hope that all makes sense, Marty. Oh -- I'm curious. Where did you find the puzzle that started this whole thread? It's a very tough one! dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Steve R



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

PostPosted: Sat Mar 18, 2006 1:14 am    Post subject: Stuck Reply with quote

Yes, please tell us more. This is the best puzzle I have seen by a country mile. I should not have realised it without the help of DCBs keen eye: the grid invites all sorts of complexities but succumbs to an elementary solution.

Quality puzzle and most elegant resolution.

Steve.
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5157
Location: Rochester, NY, USA

PostPosted: Sat Mar 18, 2006 5:51 pm    Post subject: Reply with quote

keith wrote:
Marty,

Quote:


Keith, are you off a column? Do you mean R3C1 as part of the rectangle and the "5" precluded from R2C1?



Yes. Actually, I am off a row.

As I said, the X-wing is in the columns. The possibility <5> occurs only twice in each of C1 and C4, and these possibilities line up in R3 and R9 to form a rectangle. One of the two squares in each row must be <5>, so we can exclude <5> as a possibility in any other squares in these rows.

Marty, the same argument is true if you interchange the words "row" and "column". Or, just rotate the puzzle ninety degrees.

Keith

Keith, I guess I was asleep at the switch, thinking that if it was in the columns, I had to be looking vertically instead of horizontally. I see it quite clearly now.

Quote:
Oh -- I'm curious. Where did you find the puzzle that started this whole thread? It's a very tough one!


Once again, thank you David for your explanations.

I borrowed "Sudoku for Dummies" from the library. I was actually somewhat disappointed with it because I thought it would be a book of strategies; instead, it was a book of puzzles with just a few pages covering the most basic techniques. But I copied onto blank grids all the puzzles graded "diabolical" and this was one of them. Most of them aren't as difficult and interesting as this one.

I might mention that the puzzles graded "tough" from http://sudoku.com.au are troublesome for me. A number of sources that offer puzzles have four degrees of difficulty, but I have more trouble with this fourth level than others' fourth.
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