| View previous topic :: View next topic |
| Author |
Message |
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
 Posted: Tue Feb 07, 2006 4:26 pm Post subject: Nightmare puzzle, 7 Feb, 2006 |
 |
|
Here's a tough puzzle that illustrates the "non-unique rectangle" concept.
| Code: | 6 . . . . 1 . . 5
. . 5 9 . 7 8 . .
. 4 . . . . . 3 .
. 9 . 5 . . . . 7
. . . . 4 . . . .
4 . . . . 6 . 9 .
. 3 . . . . . 1 .
. . 4 8 . 5 6 . .
7 . . 1 . . . . 8
|
I've worked quite a few puzzles that contain "non-unique rectangles," and I've noticed something: there always seems to be a fairly simple way to solve the puzzle without assuming the existence of a unique solution if one considers the "conjugate" positions of the special digit. This puzzle is a nice illustration of that principle.
After completing 19 cells and making a few eliminations with the "coloring" technique I arrived at this position.
| Code: | 6 78 3 4 28 1 9 27 5
12 12 5 9 3 7 8 6 4
89 4 79 6 5 28 127 3 12
238 9 6 5 12 28 1234 48 7
238 57 127 237 4 9 1235 58 6
4 578 12 237 1278 6 1235 9 12
5 3 8 27 6 4 27 1 9
129 12 4 8 279 5 6 27 3
7 6 29 1 29 3 45 45 8 |
Now the "non-unique rectangle" is visible at r2c1, r2c2, r8c1, & r8c2. And assuming that the solution is unique allows us to set r8c1 = 9 -- the rest of the puzzle can be solved in short order.
The conjugate solution proceeds as follows. Assume that r1c8 <> 9. Then we must have r9c3 = 9, because there's no other spot for a "9" in the lower left 3x3 box. Now we have a nice double-implication chain:
A. r9c3 = 9 ==> r3c1 = 9
B. r9c3 = 9 ==> r9c5 = 2 ==> r1c5 = 8 ==> r3c1 = 8
We can't have both "8" and "9" in r3c1, so r9c3 <> 9, and we must have r8c1 = 9.
Notice that we can follow the same chain in reverse if we choose the other "9" that's conjugate to r8c1:
r3c1 = 9 ==> r1c2 = 8 ==> r1c5 = 2 ==> r9c5 = 9
and now it's impossible to fit a "9" in the bottom left 3x3 box. dcb
Last edited by David Bryant on Wed Feb 08, 2006 9:31 pm; edited 1 time in total |
|
| Back to top |
|
 |
alanr555
Joined: 01 Aug 2005
Posts: 198
Location: Bideford Devon EX39
|
| Posted: Wed Feb 08, 2006 12:43 am Post subject: Re: Nightmare puzzle, 7 Feb, 2006 |
|
|
| Code: |
6 78 3 4 28 1 9 27 5
12 12 5 9 3 7 8 6 4
89 4 79 6 5 28 127 3 12
238 9 6 5 12 28 1234 48 7
238 57 127 237 4 9 1235 58 6
4 578 12 237 1278 6 1235 9 12
5 3 8 27 6 4 27 1 9
129 12 4 8 279 5 6 27 3
7 6 29 1 29 3 45 45 8
A. r9c3 = 9 ==> r3c1 = 9
B. r9c3 = 9 ==> r9c5 = 2 ==> r1c5 = 8 ==> r1c3 = 8
+++
In the second chain after setting r1c5 to 8, I would expect the
next link to be r3c6=2 and then r3c1=8. As r1c3 is already
set to 3, the logic is not self-evident.
This method of chains seems still to rely upon contradictions. My
understanding of the DICs defined by our Munchen friend is that
whatever value is selcted for a 'start' cell the value implied for a
'destination' cell is the same. This is a much more positive way
to present the logic - and avoids the hint of trial and error that is
implied in the contradiction approach.
Alan Rayner BS23 2QT
|
|
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Wed Feb 08, 2006 10:33 pm Post subject: Double-implication chains |
|
|
Hi, Alan!
It was a typo -- thanks for pointing it out. I've edited my earlier post to remove the slipup that turned r3c1 (the cell I meant to talk about) into r1c3.
I don't suppose there's any point in beating the dead horse of reductio ad absurdem. If you don't like to use it, then don't. The subject of double implication chains is much more interesting, anyway.
As I understand it, there are at least two kinds of double-implication chains.
-- A pair of chains proceeding from a single supposition in a single cell that intersect in some other cell to produce a contradiction.
-- At least one chain proceeding from each of two suppositions in a single cell that intersect in some other cell; these may either produce a contradiction that allows us to eliminate one candidate in the "target" cell, or they may establish the only value that's logically possible in the "target."
These chains are often "double-implication" in another sense. They may proceed by links that depend on the candidate lists at each step (eg, a path leading from {3, 4} through {4, 5} to {5,7}, and another path leading from {3, 4} through {3, 5} to {5, 7}), or they may proceed by positional clues (starting from {3, 4} as before, we observe that placing a "3" here forces a "4" in two other spots, because there are only two ways to place the "4" in this row/column/box). If there are more than three or four steps in any chain, it probably contains both types of links.
In my view, these chains are not "trial and error" because they intersect one another in a single cell after a relatively small number of steps. To me, it's only "trial and error" if one proceeds blindly down a single chain of inference, hoping to reach the end of the puzzle and backtracking if and when a contradiction is reached. But if one can visualize the steps in the process all the way to the intersection point, and make a solid deduction from that visualization, then it's not "trial and error" -- it's just a more complex form of logical inference.
Oh -- the simplest kind of double-implication chain is the familiar XY-Wing.
| Code: | xy . . xz
. . . .
yz . . wz |
We can trace two chains from the xy cell to the wz cell to prove that "z" is impossible in the "target" cell, wz. Equivalently, we can trace two chains from the wz cell to the xy cell to prove that "z" at the lower right position makes it impossible to enter any value in the xy cell. Either way we get the same result.
This post is rather long already, but I've got another nice example of double-implication chains from the "nightmare" puzzle for 8 Feb, 2006, and I may as well just go ahead and stick it in here. :)
("Nightmare", 8 Feb, 2006)
After solving 26 cells, with 33 still unresolved, I arrived at this position.
| Code: | 29 5 1 239 8 39 6 4 7
8 49 3 4679 569 67 1 2 59
6 24 7 1 59 24 59 3 8
3 1 29 5 7 29 8 6 4
4 6 8 29 3 1 59 7 259
29 7 5 68 4 68 3 1 29
7 29 269 689 1 5 4 89 3
5 3 469 46789 69 678 2 89 1
1 8 49 349 2 349 7 5 6 |
Here I found several double-implication chains, all apparently connected with the "non-unique rectangle" on {6, 7} that is just starting to emerge at r2c4, r2c6, r8c4, & r8c6. The shortest of these is rooted in r7c2:
A. r7c2 = 9 ==> r9c3 = 4 ==> {3, 9} pair in r9c4 & r9c6
B. r7c2 = 9 & r9c3 = 4 ==> r8c3 = 6 ==>r8c5 = 9
And now it's easily seen that the bottom center 3x3 box cannot be completed, so we must have r7c2 = 2.
Why do I say this chain is apparently connected with a non-unique rectangle? Well, it is also possible to show that r8c5 = 9, and when the puzzle is played that way the non-unique rectangle actually does poke out, revealing that the "conjugate" cells are r2c2, r3c6, r8c4, and r9c4, on digit "4". And all of these can be tied back to the shortest double-implication chain we've already identified:
C. r2c2 = 4 ==> r3c7 = 9
D. r3c6 = 4 ==> r3c2 = 2 ==> r7c2 = 9
E. (Either r8c4 = 4 or r9c4 = 4) ==> r3c6 = 4 ==> r7c2 = 9 (as in D)
Interestingly, we can also progress past this point by using a "coloring" argument.
| Code: | 29+ 5 1 239 8 39 6 4 7
8 49- 3 4679 569 67 1 2 59
6 24 7 1 59 24 59 3 8
3 1 29 5 7 29 8 6 4
4 6 8 29 3 1 59 7 259
29- 7 5 68 4 68 3 1 29+
7 29+ 269 689 1 5 4 89 3
5 3 469 46789 69 678 2 89 1
1 8 49 349 2 349 7 5 6 |
Clearly we must have r2c9 = 5, and this forces several more squares, ending here. (Note that the chain of "9"s can be extended while getting to this point.)
| Code: | 29 5 1 29 8 39 6 4 7
8 49 3 47 69 67 1 2 5
6 24 7 1 5 24 9 3 8
3 1 29 5 7 29 8 6 4
4 6 8 29 3 1 5 7 29
29 7 5 68 4 68 3 1 29
7 29 26 68 1 5 4 89 3
5 3 46 47 69 678 2 89 1
1 8 49 3 2 49 7 5 6 |
And now we have a very nice XY-Wing at r8c5, which can be used both to eliminate the "4" at r9c3 and the "8" at r7c8. And in fact the first of these XY-Wings is easily seen to be the core of the contradiction reached earlier by using the double-implication technique from r7c2. dcb |
|
| 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
