| View previous topic :: View next topic |
| Author |
Message |
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
 Posted: Thu Apr 27, 2006 5:39 pm Post subject: Stuck on another one |
 |
|
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 |
|
 |
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Fri Apr 28, 2006 4:18 pm Post subject: This one needs forcing chains |
|
|
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 |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Fri Apr 28, 2006 4:57 pm Post subject: |
|
|
| 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 |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Fri Apr 28, 2006 6:43 pm Post subject: Some more DIC's in this puzzle |
|
|
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 |
|
|
ravel
Joined: 21 Apr 2006
Posts: 536
|
| Posted: Sat Apr 29, 2006 2:22 pm Post subject: |
|
|
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 |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Sat Apr 29, 2006 4:09 pm Post subject: |
|
|
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 |
|
|
ravel
Joined: 21 Apr 2006
Posts: 536
|
| Posted: Sat Apr 29, 2006 7:13 pm Post subject: |
|
|
| 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 |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Sat Apr 29, 2006 10:28 pm Post subject: What's in a name? |
|
|
| 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 |
|
|
ravel
Joined: 21 Apr 2006
Posts: 536
|
| Posted: Sun Apr 30, 2006 12:24 pm Post subject: Re: What's in a name? |
|
|
| 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  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 |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Sun Apr 30, 2006 4:09 pm Post subject: |
|
|
| 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.  |
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Mon May 01, 2006 4:59 pm Post subject: I don't like extremely long chains |
|
|
| 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 |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Tue May 02, 2006 4:31 pm Post subject: |
|
|
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 |
|
|
|
|
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
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
