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 on another one

 
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: 5164
Location: Rochester, NY, USA

PostPosted: Thu Apr 27, 2006 5:39 pm    Post subject: Stuck on another one Reply with quote

This is my classic problem puzzle, too many cells with too many candidates. I've only solved two cells, r5c7 and r6c6.

Based on something I read, I made little notations outside the grid to denote rows/columns that contain strong links. How can those notations be used as a solving aid?

Code:
-------------------------------------------------------------------
|7      689    1268   |3      168    12569  |268    4568   2456   |
|2369   3689   4      |256789 68     2569   |23678  1      2567   |
|1236   368    5      |12678  4      126    |9      3678   267    |
-------------------------------------------------------------------
|13469  34679  1367   |16     5      8      |67     2      1679   |
|8      59     16     |126    7      126    |4      59     3      |
|156    2      167    |4      9      3      |678    5678   1567   |
-------------------------------------------------------------------
|3456   78     9      |568    2      456    |1      3467   467    |
|2346   1      78     |689    368    469    |5      34679  24679  |
|23456  3456   236    |1569   136    7      |236    3469   8      |
-------------------------------------------------------------------
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Fri Apr 28, 2006 4:18 pm    Post subject: This one needs forcing chains Reply with quote

Hi, Marty!

This is a very tough puzzle. Where did you find it?
Code:
-------------------------------------------------------------------
|7      689    1268+  |3      168    12569  |268    4568   2456   |
|2369   3689   4      |256789 68     2569   |23678  1      2567   |
|1236   368    5      |12678  4      126    |9      3678   267    |
-------------------------------------------------------------------
|13469  34679  1367   |16     5      8      |67     2      1679   |
|8      59     16     |126    7      126    |4      59     3      |
|156    2      167    |4      9      3      |678    5678   1567   |
-------------------------------------------------------------------
|3456   78     9      |568    2      456    |1      3467   467    |
|2346=  1      78     |689    368    469    |5      34679  24679~ |
|23456  3456   236-   |1569   136    7      |236    3469   8      |
-------------------------------------------------------------------

-- There are only two ways to enter a "2" in row 8, and only two ways to enter a "2" in column 3, so you can eliminate "2" in r1c9.

-- Similarly, there are only two ways to enter a "3" in row 7, and in column 7, so you can eliminate "3" in r2c1.

-- A double-implication chain from r5c2 is also useful:
A. r5c2 = 9 ==> r2c1 = 9.
B. r5c2 = 5 ==> r5c8 = 9 ==> r8c9 = 9 ==> r9c4 = 9.

So we can rule out the possibility of a "9" at r2c4, because there's either a "9" at r2c1, or else there's a "9" at r9c4. So the "9" in column 6 must lie in the top center 3x3 box, and we can also rule out a "9" at r8c6, making that cell into the {4, 6} pair.

That's all I have time for right now ... I hope it's helpful. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Marty R.



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

PostPosted: Fri Apr 28, 2006 4:57 pm    Post subject: Reply with quote

Quote:
That's all I have time for right now ... I hope it's helpful.


It's definitely helpful, David. As you know, I'm looking for ways to make further progress on the puzzle, but more importantly, I'm looking to train myself on how to approach these things in general and how to spot the patterns that matter.

This puzzle is rated "Tough" (April 15) from www.sudoku.com.au

These are the hardest puzzles of the ones that I have tried on a regular basis. I don't know how the Sudoku community views the "Daily Nightmare", but I have considerably more success with the latter than with the "Tough" ones from the Australian site.
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Fri Apr 28, 2006 6:43 pm    Post subject: Some more DIC's in this puzzle Reply with quote

Thanks for the link to the Australian site, Marty. I'll have to try a few of those.

Here's where I left this puzzle last time.
Code:
-------------------------------------------------------------------
|7      689    1268   |3      168    12569  |268    4568   456    |
|269    3689   4      |25678  68     2569   |23678  1      2567   |
|1236   368    5      |12678  4      126    |9      3678   267    |
-------------------------------------------------------------------
|13469  34679  1367   |16     5      8      |67     2      1679   |
|8      59     16     |126    7      126    |4      59     3      |
|156    2      167    |4      9      3      |678    5678   1567   |
-------------------------------------------------------------------
|3456   78     9      |568    2      456    |1      3467   467    |
|2346   1      78     |689    368    46     |5      34679  24679  |
|23456  3456   236    |1569   136    7      |236    3469   8      |
-------------------------------------------------------------------

We can make quite a bit of progress by considering the two possibilities at r5c2.

A. r5c2 = 5 ==> {1, 6} pair in r6c1/r5c3 ==> r4c2 <> 6.
B. r5c2 = 9 ==> {3, 6, 8} triplet in c2r1-3 ==> r4c2 <> 6.
C. r5c2 = 5 ==> {1, 6} pair ==> r6c3 = 7 ==> r8c3 = 8.
D. r5c2 = 9 ==> {3, 6, 8} triplet ==> r7c2 = 7 ==> r8c3 = 8.

So we can eliminate the "6" at r4c2 and set r8c3 = 8 -- this forces r7c2 = 7 and r7c4 = 8. Now the grid looks like this.
Code:
-------------------------------------------------------------------
|7      689    126    |3      168    12569  |268    4568   456    |
|269    3689   4      |2567   68     2569   |23678  1      2567   |
|1236   368    5      |1267   4      126    |9      3678   267    |
-------------------------------------------------------------------
|13469  349    1367   |16     5      8      |67     2      1679   |
|8      59     16     |126    7      126    |4      59     3      |
|156    2      167    |4      9      3      |678    5678   1567   |
-------------------------------------------------------------------
|3456   7      9      |8      2      456    |1      346    46     |
|2346   1      8      |69     36     46     |5      34679  24679  |
|23456  3456   236    |1569   136    7      |236    3469   8      |
-------------------------------------------------------------------

There's another chain from r5c2.

A. r5c2 <> 5 ==> r9c2 = 5 ==> r9c4 <> 5.
B. r5c2 = 5 ==> r5c8 = 9 ==> r8c9 = 9 ==> r8c4 = 6 ==> r8c6 = 4 ==> r7c6 = 5 ==> r9c4 <> 5.

So we can eliminate the "5" at r9c4, creating the {1, 6, 9} triplet in column 4 and allowing us to make quite a few "easy" moves. It's not enough to solve the puzzle completely, but at least it gets the ball rolling.

In general I've found the "double-implication chain starting from pairs" technique to be very helpful with puzzles like this one. The one exception I've noticed is that the technique is hard to apply if there aren't very many pairs in the starting grid. dcb

PS I managed to finish this puzzle off with a couple more double-implication chains, all of them rooted in r5c2, or in the adjacent cell, r5c3. Let me know if you still had trouble with this puzzle -- I'll be glad to explain the rest of it, but it will probably be more fun if you finish it up yourself.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Sat Apr 29, 2006 2:22 pm    Post subject: Reply with quote

Well done, David.

After your steps no chains are needed anymore. With an empty rectangle the 1 in r3c6 can be eliminated and you come here:

Code:
 7     689  *26    | 3     168  *1269  | 268   45    45   
 2369  3689  4     | 5     68    269   | 23678 1     267 
 1     368   5     | 7     4     26    | 9     368   26   
-------------------+-------------------+-------------------
 3469  3469  1367  | 16    5     8     | 67    2     1679
 8     59   *16    | 2     7    *16    | 4     59    3   
 56    2     167   | 4     9     3     | 678   5678  1567
-------------------+-------------------+-------------------
 346   7     9     | 8     2     5     | 1     346   46   
 236   1     8     | 69    36    4     | 5     3679  2679
 23456 3456  236   | 169   136   7     | 236   3469  8   

You have a uniqueness pattern here, which allows you to eliminate 6 from r1c3, because the 1's in column 6 are strongly linked:
r1c3=6 => r5c3=1 => r5c6=6 => r1c6=1

So r1c3=2.

With basics, another ER (for a 6) and an xy-wing the puzzle can be solved then.
Back to top
View user's profile Send private message
Marty R.



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

PostPosted: Sat Apr 29, 2006 4:09 pm    Post subject: Reply with quote

David, using your suggestions, I made quite a bit of progress, or so I thought, until I backed myself into a corner with three cells in c9 containing only the pair "39." Trying to learn techniques is a challenge, but accuracy has plagued me, even though I have always been good with details. I erased and started over.

Ravel, what are "empty rectangles"? That's a term I haven't heard before.
Back to top
View user's profile Send private message
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Sat Apr 29, 2006 7:13 pm    Post subject: Reply with quote

Marty R. wrote:

Ravel, what are "empty rectangles"? That's a term I haven't heard before.

This is Havards thread about Empty Rectangles.
And this is the first situation in your puzzle, where you can apply it (for number 1):
Code:
x7    x689   126   | 3     168   1269  | 268   45    45   
x2369 x3689  4     | 5     68    269   | 23678 1     267 
 1236  368  +5     | 7     4    -126   | 9     368   26   
-------------------+-------------------+-------------------
 13469 3469  1367  | 16    5     8     | 67    2     1679
 8     59   *16 -- | 2 --- 7 -- *16    | 4     59    3   
 156   2     167   | 4     9     3     | 678   5678  1567
-------------------+-------------------+-------------------
 346   7     9     | 8     2     5     | 1     346   46   
 236   1     8     | 69    36    4     | 5     3679  2679
 23456 3456  236   | 169   136   7     | 236   3469  8   
You have a strong link for 1 in r5c3-r5c6, the empty rectangle is in r12c12 of box 1 (in this case there are 2 ER's for 1 in box 1).
You can see, that either
r5c6=1 => r3c6<>1 or
r4c3=1 => r1c(12)3<>1 => r3c1(2)=1 => r3c6<>1
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Sat Apr 29, 2006 10:28 pm    Post subject: What's in a name? Reply with quote

ravel wrote:
Well done, David.

Thank you, ravel.
ravel wrote:
You have a uniqueness pattern here, which allows you to eliminate 6 from r1c3, ...

Not to put too fine a point on it, ravel, but I don't understand how "uniquity" applies in this situation -- the corners of the rectangle lie in four different houses. So you can't permute the values 1 & 6 around the corners, because that will produce an invalid grid (two ones in box 1 and box 5; two sixes in box 2 and box 4).

Interestingly, I did notice that setting r5c3 to "1" will lead to a contradiction when I first started working on this puzzle. The problem is, the path to the contradiction was so long and involved (at least, the one I found was) that it looked too much like "trial and error" to be any fun.
ravel wrote:
... the empty rectangle is in r12c12 of box 1 (in this case there are 2 ER's for 1 in box 1).

I read Havard's post about "empty rectangles", and I have to admit it didn't really grab my imagination. For me, at least, most of these "ERs" are more easily understood as double-implication chains.
Code:
 7     689   126   | 3     168   1269  | 268   45    45   
 2369  3689  4     | 5     68    269   | 23678 1     267
 1236  368   5     | 7     4     126   | 9     368   26   
-------------------+-------------------+-------------------
 13469 3469  1367  | 16    5     8     | 67    2     1679
 8     59   *16    | 2     7    *16    | 4     59    3   
 156   2     167   | 4     9     3     | 678   5678  1567
-------------------+-------------------+-------------------
 346   7     9     | 8     2     5     | 1     346   46   
 236   1     8     | 69    36    4     | 5     3679  2679
 23456 3456  236   | 169   136   7     | 236   3469  8

At this point in the puzzle (or one substantially similar to it) I followed a double-implication chain from r5c3.

A. r5c3 = 1 ==> r1c3 <> 1
B. r5c3 = 6 ==> r5c6 = 1 ==> r1c5 = 1 ==> r1c3 <> 1

This is exactly the same logic as the "empty rectangle" you described, ravel. I've got nothing against coining new terminology, but I'm not real certain what this particular idea adds. It may make it easier to spot cases where a DIC can be employed ... I don't know. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Sun Apr 30, 2006 12:24 pm    Post subject: Re: What's in a name? Reply with quote

David Bryant wrote:
... I don't understand how "uniquity" applies in this situation -- the corners of the rectangle lie in four different houses.

Darned, you are very right, i made the same mistake, that i have pointed out at least 2 times in other posts Sad Seems that i was too anxious for finding uniqueness patterns recently.
Thanks for correcting that.
Quote:

This is exactly the same logic as the "empty rectangle" you described, ravel. I've got nothing against coining new terminology, but I'm not real certain what this particular idea adds.

Your double-implication chain describes the use of the ER in box 2, which - combined with the same strong link - leads to the elimination of 1 in r1c3.
Of course you are right, that each ER elimination can be notated as such a chain (by definition), but note that the ER would also work, if you had more than 2 candidates in r5c36 and an additional 1 in r1c4, which makes the chain a bit less easy to spot and a bit more complicated.
The ER would be spotted as easy as in this case: when you have a strong link, just look up/down (or right/left), if there is an ER.
So i would compare it to an xy-wing, which also commonly is considered to be an own technique, while its nothing but a simple double-implication chain.
Back to top
View user's profile Send private message
Marty R.



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

PostPosted: Sun Apr 30, 2006 4:09 pm    Post subject: Reply with quote

Quote:
Interestingly, I did notice that setting r5c3 to "1" will lead to a contradiction when I first started working on this puzzle. The problem is, the path to the contradiction was so long and involved (at least, the one I found was) that it looked too much like "trial and error" to be any fun.

David, I've spoken about trial-and-error in at least one other thread, perhaps responding to comments by Alan. If I've interpreted the remarks correctly, it seems the label "trial-and-error" is being applied to the result, not the method.

If you start out testing each of two values in a cell and find some other cells are the same for both values in the starting cell, then you've done a nice DIC or forcing chain. But if one value leads to a contradiction, then it's viewed negatively as trial-and-error. In my unsophisticated newbie world, the negatively viewed latter forces a value in the starting cell, while the positively viewed former forces value(s) in other cells.

I'm having trouble understanding the difference in attitude between the two. Question
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Mon May 01, 2006 4:59 pm    Post subject: I don't like extremely long chains Reply with quote

MartyR wrote:
But if one value leads to a contradiction, then it's viewed negatively as trial-and-error.

It's not the contradiction I object to, Marty -- it's the length of the "forcing chain." Here, let me illustrate the point. The puzzle that started this thread can be reduced to this state by doing some coloring, etc.
Code:
-------------------------------------------------------------------
|7      689    1268   |3      168    12569  |268    4568   456    |
|269    3689   4      |25678  68     2569   |23678  1      2567   |
|1236   368    5      |12678  4      126    |9      3678   267    |
-------------------------------------------------------------------
|13469  34679  1367   |16     5      8      |67     2      1679   |
|8      59     16     |126    7      126    |4      59     3      |
|156    2      167    |4      9      3      |678    5678   1567   |
-------------------------------------------------------------------
|3456   78     9      |568    2      456    |1      3467   467    |
|2346   1      78     |689    368    46     |5      34679  24679  |
|23456  3456   236    |1569   136    7      |236    3469   8      |
-------------------------------------------------------------------


Placing a "1" at r5c3 will eventually lead to a contradiction, as follows.

r5c3 = 1 ==> r3c1 = 1
r5c3 = 1 ==> r4c4 = 1 ==> r9c5 = 1
r4c4 = 1 ==> r6c9 = 1
r3c1 = 1 & r9c5 = 1 ==> r1c6 = 1

Now all the "1"s have been placed on the grid, and it looks like this.

Code:
-------------------------------------------------------------------
|7      689    268    |3      68     1      |268    4568   456    |
|269    3689   4      |25678  68     2569   |23678  1      2567   |
|1      368    5      |2678   4      26     |9      3678   267    |
-------------------------------------------------------------------
|3469   34679  367    |1      5      8      |67     2      679    |
|8      59     1      |26     7      26     |4      59     3      |
|56     2      67     |4      9      3      |678    5678   1      |
-------------------------------------------------------------------
|3456   78     9      |568    2      456    |1      3467   467    |
|2346   1      78     |689    368    46     |5      34679  24679  |
|23456  3456   236    |569    1      7      |236    3469   8      |
-------------------------------------------------------------------


We observe the {6, 8} pair in column 5 and the {2, 6, 8} triplet in row 1, which allow us to simplify the grid to this state.

Code:
-------------------------------------------------------------------
|7      9      268    |3      68     1      |268    45     45     |
|269    3689   4      |257    68     259    |23678  1      267    |
|1      368    5      |27     4      2      |9      3678   267    |
-------------------------------------------------------------------
|3469   34679  367    |1      5      8      |67     2      679    |
|8      59     1      |26     7      26     |4      59     3      |
|56     2      67     |4      9      3      |678    5678   1      |
-------------------------------------------------------------------
|3456   78     9      |568    2      456    |1      3467   467    |
|246    1      78     |689    3      46     |5      4679   24679  |
|23456  3456   236    |569    1      7      |236    3469   8      |
-------------------------------------------------------------------


Now we have quite a few forced moves.

r3c6 = 2 ==> r3c4 = 7 ==> r2c4 = 5 ==> r2c6 = 9
r3c6 = 2 ==> r5c6 = 6 ==> r8c6 = 4 ==> r7c6 = 5
r5c6 = 6 ==> r5c4 = 2
r1c2 = 9 ==> r5c2 = 5 ==> r5c8 = 9
r5c2 = 5 ==> r6c1 = 6

Just so we won't get lost, here's what the grid looks like at this point.

Code:
-------------------------------------------------------------------
|7      9      268    |3      68     1      |268    45     45     |
|26     368    4      |5      68     9      |23678  1      267    |
|1      368    5      |7      4      2      |9      3678   267    |
-------------------------------------------------------------------
|3469   3467   367    |1      5      8      |67     2      679    |
|8      5      1      |2      7      6      |4      9      3      |
|6      2      67     |4      9      3      |678    5678   1      |
-------------------------------------------------------------------
|3456   78     9      |68     2      6      |1      3467   467    |
|26     1      78     |689    3      4      |5      4679   24679  |
|23456  3456   236    |69     1      7      |236    3469   8      |
-------------------------------------------------------------------


Clearly the grid cannot now be completed, because we have a "6" at r1c6, and the pair {2, 6} in r2c1 & r8c1. This is a contradiction, from which we conclude that r5c3 = 6.

I only had two reasons for avoiding this approach and seeking a simpler one when I worked up the previous solution (using shorter chains from r5c2).

-- This forcing chain is so long and involved that it's hard to explain.
-- Even after setting r5c3 = 6 one can't solve the puzzle very easily. Later on you'll have to find another forcing chain to finish it.

Generally I prefer shorter, more direct chains to longer, more complex ones. So I chose to seek another route to the solution to this puzzle. I don't have any objections to proofs by contradiction -- I understand that the statements "A is true" and "(not A) is false" are logically equivalent, and I always treat them that way. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Marty R.



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

PostPosted: Tue May 02, 2006 4:31 pm    Post subject: Reply with quote

I agree David, some of the chains are extrememely long and I always wonder if I made a mistake, since I continue to have a problem with accuracy. On some of those chains, one of the values occasionally solves every remaining cell.

In the meantime, I'm not sure where logic ends and trial-and-error starts.

By the way, some very nice work on this puzzle.
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