| View previous topic :: View next topic |
| Author |
Message |
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
 Posted: Sun Jul 23, 2006 3:50 pm Post subject: Nightmare, July 11 |
 |
|
This has been an interesting puzzle, with rectangles, X-Wing, XY-Wing and a Finned Wing. At this point it's easily solvable with a chain, perhaps multiple chains. I started with r4c6 and a "2" there solves the puzzle.
However, I am trying to cut back on my chain habit and I'm wondering if there are other techniques that are available to complete it.
| Code: | ----------------------------------------
|7 13 136 |9 46 8 |456 356 2 |
|5 23 369 |1 246 7 |49 369 8 |
|29 4 8 |3 5 26 |69 7 1 |
----------------------------------------
|8 7 35 |4 236 26 |1 56 9 |
|29 235 359 |7 36 1 |568 568 4 |
|1 6 4 |5 8 9 |7 2 3 |
----------------------------------------
|6 9 7 |8 1 3 |2 4 5 |
|3 15 15 |2 7 4 |89 89 6 |
|4 8 2 |6 9 5 |3 1 7 |
----------------------------------------
|
|
|
| Back to top |
|
 |
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sun Jul 23, 2006 7:47 pm Post subject: |
|
|
Marty,
I could make no progress without chains. Sudoku Susser says it needs a chain, and finds many of them.
I took a look for the possibility of a UR on <56> in the top right section, but I did not find anything.
Keith |
|
| Back to top |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Mon Jul 24, 2006 1:31 am Post subject: |
|
|
| Quote: | | I could make no progress without chains. Sudoku Susser says it needs a chain, and finds many of them. |
Thanks Keith. In the time I've been on this forum, there have been numerous discussions about trial-and-error and how certain chains fall into that category, at least in the opinion of some. I've argued against those opinions, yet deep down, I apparently agree partially.
Thus, I've tried to further explore other techniques before doing the chains, and have often felt that when I solved with chains that maybe I was missing something. Perhaps chains arent so bad after all; if they're good enough for the Susser, they should be good enough for me too.  |
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Mon Jul 24, 2006 11:09 pm Post subject: This puzzle features an "APE" |
|
|
I had to use double-implication chains to complete this puzzle, Marty. I think that some kind of chain is unavoidable.
Out of curiosity I ran Ruud's "SudoCue" solver on this puzzle, to see how it would mount an attack. The program produced one very interesting new style of move, called an "Aligned Pair Exclusion," or APE. Here's the position.
| Code: | 7 13 136 9 46 8 456 356 2
5 23 369 1 2467 267 469 369 8
29 4 8 3 5 26 69 7 1
8 7 345 456 236 256* 1 56 9
29 235 359 7 36 1 568 568 4
1 6 45 45 8 9 7 2 3
6 9 7 8 1 3 2 4 5
3 15 15 2 67 4 89 89 67
4 8 2 56 9 567 3 1 67 |
We can exclude the digit "5" from r4c6 by the following logic.
r4c6 = 5 ==> r4c8 = 6
r4c6 = 5 ==> r6c4 = 4
But now there are no candidates left at r4c4, so r4c6 = 5 is seen to be impossible. Notice that this particular "APE" is the same thing as the "four-star constellation" that someone_somewhere introduced on this board last October. So the logic isn't new ... but I've never seen the name "Aligned Pair Exclusion" before.
There's a pretty good description of two kinds of "APE"s on the ScanRaid web site.
Interestingly enough, Ruud's program resorts to a forcing chain after following up with a few obvious moves that follow the "APE".
| Code: | 7 13 136 9 46 8 456 356 2
5 23 369 1 246 7 469 369 8
29 4 8 3 5 26 69 7 1
8 7 345 45 236 26 1 56 9
29 235 359 7 36 1 568 568 4
1 6 45 45 8 9 7 2 3
6 9 7 8 1 3 2 4 5
3 15 15 2 67 4 89 89 6
4 8 2 6 9 5 3 1 7 |
From here we can see that r1c5 = 4 is impossible via a double-implication chain:
A. r1c5 = 6 ==> {1, 3} pair in r1c2&3.
B. r1c5 = 6 ==> r4c6 = 6 ==> r4c8 = 5 ==> r1c8 = 3
and we can't avoid placing two "3"s in row 1. Once we set r1c5 = 4 a couple of XY-Wings are enough to finish it off. dcb |
|
| Back to top |
|
|
Myth Jellies
Joined: 27 Jun 2006
Posts: 64
|
| Posted: Tue Jul 25, 2006 9:57 am Post subject: |
|
|
| Code: | *-----------*
|...|9.8|...|
|5..|...|..8|
|.4.|.5.|.7.|
|---+---+---|
|8..|...|..9|
|...|7.1|...|
|16.|.8.|.23|
|---+---+---|
|6.7|...|2.5|
|...|2.4|...|
|.8.|...|.1.|
*-----------*
*-------------------------------------------------------------*
| 7 13 136 | 9 46 8 | 456 356 2 |
| 5 23 369 | 1 2467 267 | 469 369 8 |
| 29 4 8 | 3 5 26 | 69 7 1 |
|-------------------+---------------------+-------------------|
| 8 7 *345 | b*456 236 #256 | 1 c56 9 |
| 29 235 359 | 7 36 1 | 568 568 4 |
| 1 6 *45 | a*45 8 9 | 7 2 3 |
|-------------------+---------------------+-------------------|
| 6 9 7 | 8 1 3 | 2 4 5 |
| 3 15 15 | 2 67 4 | 89 89 67 |
| 4 8 2 | 56 9 567 | 3 1 67 |
*-------------------------------------------------------------*
|
The type 4 UR using 45 in r46c34 kills the 5's in r4c34. Then the 54-46-65 xy-wing in abc kills the 5 in r4c6 and leaves row 4's only 5 in c [r4c8]. Basic reductions will get you to a BUG+1 grid from there. Of course, you can use APE, the ALS xz-rule, subset counting, or an xyz-wing prior to the UR to eliminate the 5 in r4c8 if you prefer. |
|
| Back to top |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Tue Jul 25, 2006 8:07 pm Post subject: |
|
|
| Quote: | | There's a pretty good description of two kinds of "APE"s on the ScanRaid web site. |
"The Aligned Pair Exclusion can be succinctly stated: Any two cells aligned on a row or column within the same box CANNOT duplicate the contents of any two-candidate cell they both see."
This may be succinct, but it's not clear to me. What does it mean that the two cells can't duplicate the contents of any two-candidate cell? Are we talking the two cells together, or either one of the cells can't be a duplicate? Can that be restated, perhaps with less succinctness, if necessary, and more clarity?
Consider this simple example.
| Code: | | |679 269 27 |4 1 3 |8 5 26 | |
The 679 and 269 cells both see the 27 and 26 cells. So what does that tell me about what can be done with the two three-candidate cells? |
|
| Back to top |
|
|
Myth Jellies
Joined: 27 Jun 2006
Posts: 64
|
| Posted: Tue Jul 25, 2006 10:52 pm Post subject: |
|
|
| Marty R. wrote: | Consider this simple example.
| Code: | | |679 269 27 |4 1 3 |8 5 26 | |
The 679 and 269 cells both see the 27 and 26 cells. So what does that tell me about what can be done with the two three-candidate cells? |
It tells you that if the 269 cell equals 2 then the 679 cell must be 9 (26 and 27 are prohibited by the bivalue cells). If you had a 29 cell in the same box as the two three-candidate cells, then you could eliminate the 2 from the 269 cell using APE; or the ALS xz-rule, or AICs, or Subset Counting, etc. |
|
| Back to top |
|
|
ravel
Joined: 21 Apr 2006
Posts: 536
|
| Posted: Wed Jul 26, 2006 11:37 am Post subject: |
|
|
| Myth Jellies wrote: | | The type 4 UR using 45 in r46c34 kills the 5's in r4c34. |
This is a sample, how a UR reduction can be "destroyed". From Marty's grid one could not know, if the 5 or one of the 2 4's were givens. In this case it would not have been allowed to eliminate 5 from r4c3. |
|
| Back to top |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Wed Jul 26, 2006 5:18 pm Post subject: |
|
|
| Myth Jellies wrote: | | Marty R. wrote: | Consider this simple example.
| Code: | | |679 269 27 |4 1 3 |8 5 26 | |
The 679 and 269 cells both see the 27 and 26 cells. So what does that tell me about what can be done with the two three-candidate cells? |
It tells you that if the 269 cell equals 2 then the 679 cell must be 9 (26 and 27 are prohibited by the bivalue cells). If you had a 29 cell in the same box as the two three-candidate cells, then you could eliminate the 2 from the 269 cell using APE; or the ALS xz-rule, or AICs, or Subset Counting, etc. |
Thank you Mr. Jellies, but don't underestimate my thickheadedness. It seems to me that if the 269 cell were a 2, then the 679 cell would be a 9 because it's now a single, not because of one of the alphabetical rules.
And I'm sorry to say that I still don't understand the "rule" as stated on the other site, that I quoted in my earlier post. About all I can see thus far is that situation with both cells seeing a two-candidate cell might be a good place to start a forcing chain. |
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Wed Jul 26, 2006 5:48 pm Post subject: What's in a name? |
|
|
| Marty R wrote: | | And I'm sorry to say that I still don't understand the "rule" as stated on the other site, that I quoted in my earlier post. About all I can see thus far is that situation with both cells seeing a two-candidate cell might be a good place to start a forcing chain. |
Since I brought this up, I feel as if I ought to jump in again.
I think the "rules" are getting so specialized -- and the names are getting so exotic -- that it's hard to keep track of all of them.
I think the "APE" is just a special case of the "four-star constellation" we've already kicked around pretty thoroughly. The only reason I brought it up at all is because it's a new name for a (short) variety of forcing chain, it appears to be gaining wide acceptance among sudoku programmers, and others might be interested.
I'm pretty sure you're exactly right, Marty -- the "APE" can always be visualized as a variety of forcing chain. If you want to use the new name for it, fine. If not, that's fine as well. The underlying logic is what matters. dcb |
|
| Back to top |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Wed Jul 26, 2006 11:20 pm Post subject: |
|
|
| Quote: | | I'm pretty sure you're exactly right, Marty -- the "APE" can always be visualized as a variety of forcing chain. If you want to use the new name for it, fine. If not, that's fine as well. The underlying logic is what matters. dcb |
Thanks David. I have no trouble with the name or other terminology, albeit it can be confusing at times. And I will always welcome a new technique or pattern that suggests a certain spot may be a potential for a productive chain.
What bothers me is my inability to understand the definition of the "APE" rule, as originally stated on the other site, and the attempted clarification here:
"The Aligned Pair Exclusion can be succinctly stated: Any two cells aligned on a row or column within the same box CANNOT duplicate the contents of any two-candidate cell they both see."
I do not know what "CANNOT duplicate the contents" means, whether it applies to either cell individually, or the two cells in combination. That's all I'm asking for, a restatement of the rule that I can understand. |
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Thu Jul 27, 2006 12:21 am Post subject: Restating the "succinct" rule |
|
|
| Marty R wrote: | | I do not know what "CANNOT duplicate the contents" means, whether it applies to either cell individually, or the two cells in combination. That's all I'm asking for, a restatement of the rule that I can understand. |
Well, I'm not real hot with definitions, but I'll try to clarify this one, by being a little more verbose.
Suppose there are two cells (A, B) that can both "see" one or more other cells, each of which has just two possible candidates. Then in the final solution, you will not find those two cells (A, B) containing, between them, any of the pairs of candidates both A and B could "see".
I think the thing about being aligned in a row or column, and within the same box, is just a red herring. It may make the particular combination a little bit easier to look for. But the principle is simple: combinations of values that eliminate all candidates from one or more cells are simply impossible. In other words, I see nothing earth-shaking about the "APE" -- it's just a catchy new name for a form of proof by contradiction. dcb |
|
| Back to top |
|
|
ravel
Joined: 21 Apr 2006
Posts: 536
|
| Posted: Thu Jul 27, 2006 9:27 am Post subject: |
|
|
Marty,
you can find four nice puzzles, that can be solved with APE there. I suppose you would solve the first 2 without seeing it, but in the 3rd and maybe the 4th you might stumble at it.
For me APE is a subset of ALS, which one can spot rather easily, where all the other ALS's i had, i found "accidentally" when looking for chains using tuples.
PS: another APE puzzle:
| Code: | +-------+-------+-------+
| . . . | 6 5 3 | . . . |
| . 2 . | . . 4 | 3 . . |
| 4 . . | . 2 . | . 1 . |
+-------+-------+-------+
| . . . | . 3 . | . 2 . |
| . 6 5 | . . 7 | 4 . . |
| 8 . . | 4 . . | . . . |
+-------+-------+-------+
| 3 . . | 1 . . | . 9 . |
| . 4 2 | . . . | 1 . . |
| . . 8 | 2 7 . | . . . |
+-------+-------+-------+
|
|
|
| Back to top |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Thu Jul 27, 2006 5:34 pm Post subject: |
|
|
Thanks guys. I think it's best that I just let this drop. If I don't get it by now, I'm not gonna get it.
The only ALS I've ever heard of is the disease that nobody wants.
Ravel, I tried that puzzle and it took a little work. There was a finned wing, strong link, type 4 rectangle and x-wing. Then I was stuck, so I tried a chain which lead to a contradiction. Then another chain solved the whole thing.
Perhaps I used the APE rule without knowing I used it. |
|
| Back to top |
|
|
ravel
Joined: 21 Apr 2006
Posts: 536
|
| Posted: Fri Jul 28, 2006 7:22 am Post subject: |
|
|
I really think you dont need it :)
So just to finish the topic: The 3 pairs kill all candidates in r9c1, when they cannot be 7.
| Code: | #17 178 9 | 6 5 3 | 2 78 4
567 2 67 | 789 1 4 | 3 578 579
4 578 3 | 789 2 89 | 679 1 5679
-----------------------------------------------------
#79 79 4 | 5 3 1 | 68 2 68
2 6 5 | 89 89 7 | 4 3 1
8 3 1 | 4 6 2 | 79 57 579
-----------------------------------------------------
3 57 #67 | 1 4 568 | 78 9 2
5-79 4 2 | 3 89 589 | 1 6 78
#169 19 8 | 2 7 69 | 5 4 3
|
|
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Fri Jul 28, 2006 3:04 pm Post subject: This "APE" has a sort of "mirror-image" |
|
|
Ravel, when I reached that point in this puzzle I saw a double-implication chain which amounts to the same thing, more or less.
| Code: | 17 178 9 | 6 5 3 | 2 78 4
567 2 67 | 789 1 4 | 3 578 579
4 578b 3 | 789 2 89 | 679 1 5679b
-----------------------------------------------------
79 79 4 | 5 3 1 | 68b 2 68
2 6 5 | 89 89 7 | 4 3 1
8 3 1 | 4 6 2 | 79 57 579
-----------------------------------------------------
3 57a 67 | 1 4 568 | 78b 9 2
579 4 2 | 3 89 589 | 1 6 78
169 19 8 | 2 7 69 | 5 4 3 |
A. r7c3 = 7 ==> r7c2 = 5
B. r7c3 = 7 ==> r7c7 = 8 ==> r4c7 6 ==> r3c9 = 6 ==> r3c2 = 5
Here's why this DIC looks like a "mirror-image" of the APE you pointed out.
-- Your contradiction left no candidates at r4c1. We can also think of this as meaning (somewhat illogically) that both "7" and "9" have to fit into r4c2.
-- Think about column 2, with both "7" and "9" occupying r4c2. Then r9c2 = 1, and r1c2 = 8, leaving only "5" to occupy both r3c2 and r6c2. In other words, the contradiction you derived implies (broadly speaking) the contradiction I arrived at.
I can't exactly prove this idea -- I'm not even sure I can express it clearly. But it's as if the double-implication chain I used is a sort of dual, or mirror-image, of the "APE" chain you explained. dcb
PS This setup has other possibilities. For instance, consider what happens if r1c2 = 1 ...
A. r1c2 = 1 ==> r1c1 = 7 ==> r4c1 = 9 ==> r8c1 = 5
B. r1c2 = 1 ==> r9c2 = 9 ==> r4c2 = 7 ==> r7c2 = 5
This also leads pretty directly to your conclusion that r8c1 <> 7, because of r1c1 = 1, r9c2 = 1, r4c2 = 9, and r4c1 = 7. My point is that there are quite a few chains of inference involving the same basic structure, any one of which is enough to crack this puzzle wide open. For a human solver, any of these are equally useful ... the challenge is just to spot any one of them. |
|
| Back to top |
|
|
ravel
Joined: 21 Apr 2006
Posts: 536
|
| Posted: Fri Jul 28, 2006 9:48 pm Post subject: |
|
|
Very interesting, David.
I like your idea of "dual" chains (we have this for hidden/naked sets and the "dual" fish patterns with k and 9-k rows/columns involved).
Unfortunateley in the moment i am too busy to think more about that. |
|
| 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
