| View previous topic :: View next topic |
| Author |
Message |
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
 Posted: Sat Nov 17, 2007 9:57 pm Post subject: Remote Pairs, and some variants |
 |
|
Chapter 1: The Classic Remote Pair
In Sudoku terms, a pair is two cells in the same house (row, column, or box) that have the same two candidates. No other cell in the same house can have either of these candidates.
In other words: If any two cells that are peers have the same two candidates (and only two candidates), those candidates can be eliminated in their shared peers.
Sometimes we find that more than two cells in a puzzle have the same two candidates. Moreover these cells can sometimes be linked in a chain to form a remote pair. The cells in the remote pair are not peers, but their candidate values can be eliminated in the cells that are their shared peers.
For example, the following puzzle
| Code: | Example 1
+-------+-------+-------+
| . . 7 | . . 6 | 8 . . |
| . 1 2 | . . . | 3 7 . |
| 9 . . | . . 3 | . . 6 |
+-------+-------+-------+
| 7 . . | . 5 . | . . 3 |
| . 2 . | . 6 . | . 8 . |
| . . . | . 4 . | . . . |
+-------+-------+-------+
| 3 . . | . . 5 | . . 8 |
| . 8 4 | . . . | 7 2 . |
| . . 5 | . . 7 | 6 . . |
+-------+-------+-------+ |
becomes (using only singles)
| Code: | Example 1
+-------------+-------------+-------------+
| 45B 3 7 | 1 9 6 | 8 45A 2 |
| 6 1 2 | 5 8 4 | 3 7 9 |
| 9 45 8 | 2 7 3 | 145 145 6 |
+-------------+-------------+-------------+
| 7 46 1 | 9 5 8 | 2 46 3 |
| 45C 2 9 | 3 6 1 | 45D 8 7 |
| 8 56 3 | 7 4 2 | 59 569 1 |
+-------------+-------------+-------------+
| 3 7 6 | 4 2 5 | 19 19 8 |
| 1 8 4 | 6 3 9 | 7 2 5 |
| 2 9 5 | 8 1 7 | 6 3 4 |
+-------------+-------------+-------------+ |
Note that the cells marked A and B each have the same two candidates, and are in the same row. A and B are a pair, as are B and C, and C and D. They form a chain:
A=B=C=D or
XY=XY=XY=XY
with two possible solutions:
4 5 4 5 or
5 4 5 4.
A and D are a remote pair. They are not peers, but in the solution one of them is <4>, and the other must be <5>. We can eliminate the candidates in their shared peers: <45> in R3C7, <4> in R4C8, and <5> in R6C8. This solves the puzzle.
Note that, in order to be a remote pair, the chain must have an even number of cells, and an odd number of links. If we have
XY=XY or XY=XY=XY=XY or XY=XY=XY=XY=XY=XY
we can say that one end is X and the other is Y, and we can eliminate X and Y from the shared peers of the pincer cells at the ends of the chain.
If, on the other hand, the chain has an odd number of cells, and an even number of links
XY=XY=XY or XY=XY=XY=XY=XY
we can only say that both ends of the chain are the same value. Both are X, or both are Y. Andrew Stuart (link below) calls this a complementary pair.
Above is the usual explanation of remote pairs. They are not very common, but when they do occur they are very easy to find.
But, there is much more! The rest of this thread explores the question: What can I do if two cells that are not peers have the same two candidates?
Credits
Remote pairs were apparently discovered by Andrew Stuart. His description is here:
http://www.scanraid.com/AdvanStrategies.htm#RP
Glossary
House. Row, column, or 3x3 box.
Line. Row or column.
Peers. Cells that a single cell can "see". A single cell has 20 peers: Eight in its row, eight in its column, and another four in its box (that are not in its row or column).
Shared peers. Peers that two cells have in common. Two cells have at least two, and as many as 13 shared peers.[/i]
Last edited by keith on Sat Dec 29, 2007 3:22 pm; edited 3 times in total |
|
| Back to top |
|
 |
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sat Dec 29, 2007 6:55 am Post subject: |
|
|
Chapter 2: A More General Remote Pair
It is not necessary that the remote pair be connected by a chain of cells each having the same two candidates. Only one candidate is required.
Returning to the example:
| Code: | Example 1
+-------------+-------------+-------------+
| 45B 3 7 | 1 9 6 | 8 45A 2 |
| 6 1 2 | 5 8 4 | 3 7 9 |
| 9 45C 8 | 2 7 3 | 145 145 6 |
+-------------+-------------+-------------+
| 7 46 1 | 9 5 8 | 2 46 3 |
| 45E 2 9 | 3 6 1 | 45F 8 7 |
| 8 56D 3 | 7 4 2 | 59 569 1 |
+-------------+-------------+-------------+
| 3 7 6 | 4 2 5 | 19 19 8 |
| 1 8 4 | 6 3 9 | 7 2 5 |
| 2 9 5 | 8 1 7 | 6 3 4 |
+-------------+-------------+-------------+
|
A=B=C=D=E=F is a chain of strong links in <5>. In the solution, one of A or F is <5>. The other must be <4>, since A and F have the same two candidates <45>.
A number of people seem to know this, but I have not been able to find it written down anywhere: If two cells that are not peers have the same two candidates, and can be connected by a chain of an odd number of strong links in one of the candidates, the two cells are a remote pair.
For example,
| Code: | Example 2
+-------+-------+-------+
| 8 . . | . 4 . | . 3 . |
| 9 4 . | . . . | . . . |
| . 2 . | . 1 5 | 8 4 . |
+-------+-------+-------+
| . . . | . . . | 5 . . |
| . 6 . | . . 2 | . . . |
| . . . | 6 8 . | 7 . 3 |
+-------+-------+-------+
| 7 . . | . 5 . | . . 6 |
| . 5 . | . . . | 4 . . |
| 6 . 3 | . . . | . . 7 |
+-------+-------+-------+ |
can be reduced, using only singles, to:
| Code: | Example 2
+-------------+-------------+-------------+
| 8 7 15 | 29 4 69 | 126 3 125 |
| 9 4 15 | 8 26 3 | 126 7 125 |
| 3 2 6 | 7 1 5 | 8 4 9 |
+-------------+-------------+-------------+
| 24C 3 8 | 1 79 79 | 5 6 24B |
| 14 6 7 | 5 3 2 | 19 189 148 |
| 5 19 29 | 6 8 4 | 7 12A 3 |
+-------------+-------------+-------------+
| 7 189 4 | 29 5 18 | 3 129 6 |
| 12D 5 29 | 3 67 67 | 4 -189 18 |
| 6 189 3 | 4 29 18 | 129 5 7 |
+-------------+-------------+-------------+ |
A=B=C=D is a chain of strong links on <2>, connecting two cells with the same pair of candidates, <12>. We can eliminate <12> from all their shared peers, including <1> in R8C8. A and D are a remote pair.
[Yes, I understand that, in this example, A and D can also be connected by a chain of strong links in <1>. That does not affect the logic described above.]
Last edited by keith on Sat Dec 29, 2007 9:36 pm; edited 1 time in total |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sat Dec 29, 2007 7:49 am Post subject: |
|
|
Chapter 3: The M-Wing
We now continue the discussion: If two cells that are not peers each have the same two candidates, how might this be useful?
If the cells are a remote pair, they must be connected by an odd number of strong links in one candidate. If the cells are connected by an even number of strong links, they are a complementary pair. It is It is often said that a complementary pair is not useful. This is not true!
The following puzzle:
| Code: | Example 3
+-------+-------+-------+
| . . . | 8 . . | . . . |
| . . 5 | . . 6 | 7 . . |
| 8 . 4 | 5 9 . | 3 . 2 |
+-------+-------+-------+
| 2 . . | . 1 . | . . 9 |
| . . . | 3 . 9 | . . . |
| . 4 9 | . 2 . | 8 1 . |
+-------+-------+-------+
| 7 . 3 | 2 8 . | 5 . 6 |
| . . 2 | . . 7 | 1 . . |
| . . . | 1 . . | . . . |
+-------+-------+-------+ |
can be simplified, with singles only, to
| Code: | Example 3
+-------------+-------------+-------------+
| 136 36A 1-6 | 8 7 2 | 9 45 45 |
| 9 2 5 | 4 3 6 | 7 8 1 |
| 8 7 4 | 5 9 1 | 3 6 2 |
+-------------+-------------+-------------+
| 2 35B 67D | 67 1 8 | 4 35 9 |
| 15 58 178 | 3 4 9 | 6 2 57 |
| 36C 4 9 | 67 2 5 | 8 1 37 |
+-------------+-------------+-------------+
| 7 1 3 | 2 8 4 | 5 9 6 |
| 456 568 2 | 9 56 7 | 1 34 348 |
| 456 9 68 | 1 56 3 | 2 7 48 |
+-------------+-------------+-------------+ |
A and C are a complementary pair, joined via their strong links on <3> to B. C is extended to D by a strong link on <6>. We can eliminate <6> in R1C3.
So: If two cells that are not peers have the same two candidates and can be connected by an even number of strong links in one candidate, they are a complementary pair. Those two cells will have the same value in the solution. If either end can be extended by a strong link on the other candidate, that candidate can be eliminated in the shared peers of the ends of the extended chain.
To summarize, the M-wing is
XY=X=XY=Y
and we can eliminate Y from the shared peers of the end cells.
I have called this an M-Wing, for it is the simplest case of Medusa coloring. Also, it is similar to a W-Wing, which is the next topic of discussion.
Another example: This puzzle is quite difficult!
| Code: | Example 4
+-------+-------+-------+
| 2 . 9 | . . 3 | 1 . 8 |
| . 1 3 | . 9 . | 7 5 . |
| . . . | 1 . . | . . . |
+-------+-------+-------+
| 8 . . | . . . | 4 . . |
| . 4 . | 3 . 9 | . 2 . |
| . . 7 | . . . | . . 1 |
+-------+-------+-------+
| . . . | . . 2 | . . . |
| . 8 1 | . 6 . | 2 3 . |
| 7 . 2 | 4 . . | 6 . 5 |
+-------+-------+-------+
+----------------+----------------+----------------+
| 2 567 9 | 567 457 3 | 1 46 8 |
| 46 1 3 | 268 9 468 | 7 5 26 |
| 456 567 8 | 1 2457 4567 | 39 469 2369 |
+----------------+----------------+----------------+
| 8 239 56 | 2567 1257 1567 | 4 679 3679 |
| 1 4 56 | 3 578 9 | 58 2 67 |
| 39A 239 7 | 2568 2458 4568 | 3589 68-9 1 |
+----------------+----------------+----------------+
|3569B 56 4 | 589 1358 2 | 89 1789 79 |
| 59 8 1 | 579 6 57 | 2 3 4 |
| 7 39C 2 | 4 138 18 | 6 189D 5 |
+----------------+----------------+----------------+
|
A and C <39> are a complementary pair, linked by <3> in B. ABCD is an M-wing that takes out <9> in R6C8. This reveals an XY-wing which solves the puzzle.
Last edited by keith on Sun Dec 30, 2007 3:45 am; edited 5 times in total |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sat Dec 29, 2007 8:15 am Post subject: |
|
|
Chapter 4: The W-Wing
A W-wing consists of two cells that have the same two (and only two) candidates. They are supplemented by two more cells that are a strong link on either of the candidates:
XY-X=X-XY
We can eliminate Y from the shared peers of the end cells. For example, the following puzzle
| Code: |
Example 5
+-------+-------+-------+
| . . . | . 5 . | . . . |
| 9 . . | 6 . . | . . 3 |
| . 7 . | 8 . 2 | . 4 . |
+-------+-------+-------+
| 2 . 4 | . 8 . | . . 1 |
| . . 7 | 9 . 4 | 8 . . |
| 6 . . | . 7 . | 5 . . |
+-------+-------+-------+
| . 9 . | 3 . 8 | . 2 . |
| 8 . . | . . 5 | . . 6 |
| . . . | . 2 . | . . . |
+-------+-------+-------+ |
is simplified, using only singles, to:
| Code: |
Example 5
+----------------+----------------+----------------+
| 14A 26 268 | 14 5 3 | 267 78 9 |
| 9 1245 1258 | 6 14 7 | 12 18 3 |
| 3 7 16B | 8 9 2 | 16C 4 5 |
+----------------+----------------+----------------+
| 2 3 4 | 5 8 6 | 79 79 1 |
| 15 15 7 | 9 3 4 | 8 6 2 |
| 6 8 9 | 2 7 1 | 5 3 4 |
+----------------+----------------+----------------+
|1-45 9 15 | 3 6 8 | 14D 2 7 |
| 8 124 123 | 7 14 5 | 1349 19 6 |
| 7 146 136 | 14 2 9 | 134 5 8 |
+----------------+----------------+----------------+ |
A and D have the same candidates, <14>. They are connected by the strong link BC on <1> in R3. We can eliminate <4> from the shared peers of A and D; in particular, from R7C1.
The W-wing is sometimes called a semi-remote pair. The pattern was noticed (in this forum) by George Woods, and named in his honor. Here is one of the original threads: http://www.dailysudoku.com/sudoku/forums/viewtopic.php?p=6357
Last edited by keith on Sun Oct 26, 2008 5:02 am; edited 6 times in total |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sat Dec 29, 2007 8:17 am Post subject: |
|
|
Chapter 5: The Extended XY-Wing
The XY-wing is a chain of the form
XZ-XY-YZ
and the cells are in more than one house. Z can be eliminated from the shared peers of the end cells.
A complementary pair of the form
XY=X=XY
is such that the end cells have the same value. So, we can substitute the complementary pair for the pivot (center) cell of the XY-wing, to make an extended XY-wing
XZ-XY=X=XY-YZ
which makes the same eliminations as the XY-wing.
In fact, we can substitute the complementary pair for any of the three cells in the XY-wing. For example,
XZ=X=XZ-XY-YZ
makes the same eliminations.
So, if you have identified a complementary pair, check to see if you can make an extended XY-wing.
{Example Required}.
Last edited by keith on Sat Dec 29, 2007 9:55 pm; edited 1 time in total |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sat Dec 29, 2007 8:17 am Post subject: |
|
|
Chapter 6: Pincer Coloring, and other comments
Last edited by keith on Sat Dec 29, 2007 9:31 am; edited 2 times in total |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sat Dec 29, 2007 9:29 am Post subject: |
|
|
Chapter 7: Summing It Up
A. Weak link
More than two cells in the same house have the same candidate value. Any two of these cells are weakly linked. In the solution, at least one of them is not true.
B. Strong link
Two (and no other) cells in the same house have the same candidate value. These cells are strongly linked. In the solution, one of them has the candidate value, the other does not.
C. Pair
Two cells in the same house have the same two (and only two) candidate values. These cells are strongly linked in both candidates. In the solution, one cell is the first candidate, the other is the second.
D. Classic Remote Pair
Two cells that are not peers have the same two candidate values. They can be linked by a chain of cells that:
1. All have the same pair of candidates.
2. Has an even number of cells, which is equivalent to an odd number of links.
The ends of the chain
XY=XY=XY=XY
are a remote pair. The chain is comprised of four cells and three strong links on both X and Y.
E. General Remote Pair
Two cells that are not peers have the same two candidate values. They can be linked by a chain of cells that:
1. Comprises strong links on one of the candidates.
2. Has an even number of cells, which is equivalent to an odd number of links.
The ends of the chain
XY=X=X=XY
are a remote pair. The chain is comprised of four cells and three strong links on X.
F. Classic Complementary Pair
Two cells that are not peers have the same two candidate values. They can be linked by a chain of cells that:
1. All have the same pair of candidates.
2. Has an odd number of cells, which is equivalent to an even number of links.
The ends of the chain
XY=XY=XY
are a complementary pair. The chain is comprised of three cells and two strong links on both X and Y.
G. General Complementary Pair
Two cells that are not peers have the same two candidate values. They can be linked by a chain of cells that:
1. Comprises strong links on one of the candidates.
2. Has an odd number of cells, which is equivalent to an even number of links.
The ends of the chain
XY=X=XY
are a complementary pair. The chain is comprised of three cells and two strong links on X.
H. M-Wing
I. W-Wing
J. Extended XY-Wing
K. Pincer Coloring
Glossary
= Strong link
- Weak link |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Mon Jan 28, 2008 10:02 pm Post subject: |
|
|
Appendix: ravel's half M-wing
This message is copied from another thread:
http://www.dailysudoku.com/sudoku/forums/viewtopic.php?t=2298
I decided to look for another of these, which ravel pointed out a week or two ago.
| Code: |
Puzzle: M5963221sh(15)
+-------+-------+-------+
| . . 1 | . . . | . 3 . |
| . . 8 | 5 . . | 1 9 6 |
| . . 2 | . 8 . | 5 . . |
+-------+-------+-------+
| . . . | . . 8 | . . . |
| 4 . . | 6 . . | . . . |
| . . 7 | . . . | . . 5 |
+-------+-------+-------+
| 3 . . | . 1 . | 6 . 7 |
| . . 5 | . 7 . | 8 . 3 |
| . . . | . 2 4 | . . . |
+-------+-------+-------+
|
An XYZ-wing and extreme basics get us to here:
| Code: | +----------------+----------------+----------------+
| 59 45 1 | 47 6 79 | 2 3 8 |
| 7 34 8 | 5 34 2 | 1 9 6 |
| 69 36 2 | 1 8 39 | 5 7 4 |
+----------------+----------------+----------------+
| 156 156 39 | 247 34A 8 | 347B 16 29 |
| 4 128 39 | 6 5 1-37 | 37 18 29 |
| 126 1268 7 | 24 9 13D | 34C 168 5 |
+----------------+----------------+----------------+
| 3 9 4 | 8 1 5 | 6 2 7 |
| 12 12 5 | 9 7 6 | 8 4 3 |
| 8 7 6 | 3 2 4 | 9 5 1 |
+----------------+----------------+----------------+ |
A and C have the same two candidates. They are not a remote pair, they are not a complementary pair. All you can say is: If A is <4>, C is <4>. (There is a weak link A-B, and a strong link, B=C, on <4>.)
But, there is also a strong link on <3> in C=D.
The logic for the elimination is:
Either:
1. A is <3>.
Or:
2. A is <4>, C is <4>, D is <3>.
Any cell that sees both A and D cannot be <3>. In particular, we can take out <3> from R5C6.
Which leads to an XY-wing, which solves the puzzle.
Bravo, ravel!
There are more messages in the original thread:
http://www.dailysudoku.com/sudoku/forums/viewtopic.php?t=2298 |
|
| Back to top |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Mon Mar 17, 2008 12:35 am Post subject: |
|
|
A W-Wing question:
| Code: |
+-------------+----------+------------+
| 578 3 248 | 6 458 1 | 28 57 9 |
| 1 47 248 | 3 458 9 | 268 57 26 |
| 58 6 9 | 25 258 7 | 1 3 4 |
+-------------+----------+------------+
| 2 5 3 | 1 6 4 | 7 9 8 |
| 79 47 46 | 8 59 2 | 56 1 3 |
| 89 18 168 | 59 7 3 | 4 2 56 |
+-------------+----------+------------+
| 6 9 7 | 4 12 5 | 3 8 12 |
| 3 128 158 | 29 129 6 | 25 4 7 |
| 4 12 15 | 7 3 8 | 9 6 125 |
+-------------+----------+------------+
|
Play this puzzle online at the Daily Sudoku site
This is from the March 16 VH. Note the potential W-Wing on 25 in boxes 2 and 9. There is no connecting strong link that I can see. But the 5 in r5c7 sees the pair in box 9; by coloring this with two strong links, you get to r6c4, which sees the pair in box 2. I thought this was the equivalent of a strong link connection on 5, which would makes the pincers = 2 on the two pairs. But then testing the pairs shows that they are both 2 or both 5, thus no pincer effect.
Where have I gone astray?
(The grid is apparently not in error, since I can use the 89-58-59 XY-Wing to take out the 2 from r3c4 and successfully complete the puzzle). |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Mon Mar 17, 2008 1:53 am Post subject: |
|
|
Marty,
You are one link short:
| Code: | +-------------+----------+------------+
| 578 3 248 | 6 458 1 | 28 57 9 |
| 1 47 248 | 3 458 9 | 268 57 26 |
| 58 6 9 |25a 258g 7| 1 3 4 |
+-------------+----------+------------+
| 2 5 3 | 1 6 4 | 7 9 8 |
| 79 47 46 | 8 59c 2 |56d 1 3 |
| 89 18 168 |59b 7 3 | 4 2 56 |
+-------------+----------+------------+
| 6 9 7 | 4 12 5 | 3 8 12 |
| 3 128 158 |29f 1-29 6|25e 4 7 |
| 4 12 15 | 7 3 8 | 9 6 125 |
+-------------+----------+------------+ |
The connecting chain must be one, or three, or five, ... links. Yours, bcd, is only two. This is not a W-wing.
But, it is a potential M-wing. Note the coloring chain on <5> abcde. Since a and e have the same two candidates, they are a complementary pair: In the solution, they have the same value. You can complete the M-wing by adding a strong link on 2: af (or ag). The pincers in ef or eg are on <2>; you can take out <2> in R8C5.
Keith |
|
| Back to top |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Mon Mar 17, 2008 3:53 am Post subject: |
|
|
Keith, once again you're there to rescue me. Of course, since a strong link has opposite polarity, I'd need an odd number of links. Why didn't I think of that?
I wasn't thinking M-Wing at the time, but I easily see it.
Thank you. |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sat Nov 01, 2008 8:22 pm Post subject: |
|
|
Appendix 2: Generalizing the M-wing
The idea of the M-wing is this: Suppose you have a complementary pair, XY ... XY. They are connected in some way so that you know they have the same value in the solved puzzle. If you can append a strong link in either X or Y to either cell, you have a chain with pincers X or Y.
You may then have this chain:
XY ... (X) ... XY = aY
where a is anything and = is a strong link in Y. The ... (X) ... simply means that there is some logic concerning X that leads you to conclude the XY cells have the same value.
Nataraj and / or Asellus pointed out that the chain can be
XY ... (X) ... bXY = aY
where b is anything. The logic is a little different, but the conclusion still is: One, or both, of the pincers is Y.
Here is a great example:
http://www.dailysudoku.com/sudoku/forums/viewtopic.php?t=2851
| Code: | . . 7 8 . . . . .
. 2 . . . 1 6 . .
3 . . . . . . 9 .
9 . . 5 . . . 8 .
. . . . 2 . . . .
. 1 . . . 4 . . 2
. 4 . . . . . . 1
. . 9 3 . . . . .
. . . . . 7 2 . . gsf |
After basics:
| Code: | +----------------+----------------+----------------+
| 4 9 7 | 8 6 3 | 1 2 5 |
| 58 2 58 | 4 9 1 | 6 37C 37B |
| 3 6 1 | 2 7 5 | 48 9 48 |
+----------------+----------------+----------------+
| 9 3 2 | 5 1 6 | 47 8 47 |
|-67 5 4 | 79 2 8 | 39 1 36A |
| 678 1 68F | 79 3 4 | 59 5-6 2 |
+----------------+----------------+----------------+
| 2 4 35 | 6 58 9 | 3578 357D 1 |
| 1 7 9 | 3 458 2 | 58 456 68 |
| 56 8 356E | 1 45 7 | 2 345D 9 |
+----------------+----------------+----------------+ |
As pointed out by daj95376 in the original thread:
Coloring on <3>: If A is true, C is true, E is true. B, D (grouped coloring) are false. Add the strong link EF on <6>. Then you have:
A is <6>, or:
A is <3>, F is <6>.
Making the eliminations shown, and solving the puzzle.
Keith
(By the way, this is beyond the original idea of the M-wing. But, it is a reasonable extension of the logic.) |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sun Nov 09, 2008 8:17 pm Post subject: |
|
|
Here is another example of a generalized M-wing. It is a puzzle from Menneske:
http://www.menneske.no/sudoku/eng/
| Code: | Puzzle: M5592928sh(23)
+-------+-------+-------+
| 1 . 2 | 4 5 . | 6 . 8 |
| . 7 . | . . 9 | . 1 . |
| . . 4 | . . . | 9 . . |
+-------+-------+-------+
| . 8 . | . . . | . . 4 |
| 6 . . | . 1 . | . . 2 |
| 7 . . | . . . | . 5 . |
+-------+-------+-------+
| . . 7 | . . . | 3 . . |
| . 2 . | 1 . . | . 4 . |
| 4 . 8 | . 3 7 | 2 . 6 |
+-------+-------+-------+ |
After basics:
| Code: | +----------------+----------------+----------------+
| 1 9 2 | 4 5 3 | 6 7 8 |
| 358 7 356 | 268 268 9 | 4 1 35 |
| 358 356C 4 | 678 678 1 | 9 2 35 |
+----------------+----------------+----------------+
| 2 8 1-39 | 379 79 5 | 17 6 4 |
| 6 45E 59 | 789 1 48 | 78 3 2 |
| 7 34D 1-3 | 2368 2468 2468 | 18 5 9 |
+----------------+----------------+----------------+
| 59 56B 7 | 269 2469 246 | 3 8 1 |
| 39 2 36A | 1 689 68 | 5 4 7 |
| 4 1 8 | 5 3 7 | 2 9 6 |
+----------------+----------------+----------------+ |
AB and BC are strong links on <6>. If A is <6>, so is <C>.
CD is a strong link on <3>. If A is <6>, D is <3>.
A and D are pincers on <3>, making the eliminations shown, and solving the puzzle.
(DE are a pseudo-cell <35>, forming an XY-wing with A and B, making the same eliminations. Choose your poison.)
Keith |
|
| Back to top |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Sun Nov 09, 2008 10:26 pm Post subject: |
|
|
| Keith, how do you look for these? Do you look for the remote pairs XY-bXY first or for the strong links first? |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sun Nov 09, 2008 11:16 pm Post subject: |
|
|
| Marty R. wrote: | | Keith, how do you look for these? Do you look for the remote pairs XY-bXY first or for the strong links first? |
Marty,
I look for the possible pairs first: XY and XY.
Then, I ask, how can they be connected? As W-wings, or as potential M-wings? Or as remote pairs?
Then, I look for XY and bXY. Can they be connected in X or Y? If X, can you make an M-wing with a link on Y?
This may sound pretty arcane, but (I think) if you look at this example, this generalized M-wing is easy to see. After you see it!
To be quite honest, I have, so far, only solved a couple of puzzles this way. But, this will be an essential part of my toolkit in the future!
Keith |
|
| Back to top |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Sun Nov 09, 2008 11:47 pm Post subject: |
|
|
| Thanks Keith. I don't expect to use this very often, but it may help me in detecting patterns. |
|
| Back to top |
|
|
re'born
Joined: 28 Oct 2007
Posts: 80
|
| Posted: Mon Nov 17, 2008 4:06 am Post subject: |
|
|
| keith wrote: | Appendix: ravel's half M-wing
| Code: | +----------------+----------------+----------------+
| 59 45 1 | 47 6 79 | 2 3 8 |
| 7 34 8 | 5 34 2 | 1 9 6 |
| 69 36 2 | 1 8 39 | 5 7 4 |
+----------------+----------------+----------------+
| 156 156 39 | 247 34A 8 | 347B 16 29 |
| 4 128 39 | 6 5 1-37 | 37 18 29 |
| 126 1268 7 | 24 9 13D | 34C 168 5 |
+----------------+----------------+----------------+
| 3 9 4 | 8 1 5 | 6 2 7 |
| 12 12 5 | 9 7 6 | 8 4 3 |
| 8 7 6 | 3 2 4 | 9 5 1 |
+----------------+----------------+----------------+ |
A and C have the same two candidates. They are not a remote pair, they are not a complementary pair. All you can say is: If A is <4>, C is <4>. (There is a weak link A-B, and a strong link, B=C, on <4>.)
But, there is also a strong link on <3> in C=D.
The logic for the elimination is:
Either:
1. A is <3>.
Or:
2. A is <4>, C is <4>, D is <3>.
Any cell that sees both A and D cannot be <3>. In particular, we can take out <3> from R5C6.
|
Hi Keith, sorry to join the party so late. I just found out what an M-wing is. It seems to me that (at least in this particular case) your half M-wing creates a continuous loop:
(3)r6c7 = r6c6 - (3=4)r4c5 - r4c7 = (4-3)r6c7
This not only implies that r5c6<>3, but that r4c4<>4. Is this already well-known?
By the way, the same things holds for ravel's original allowing you to also eliminate 8 from r7c157. |
|
| Back to top |
|
|
nataraj
Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria
|
| Posted: Mon Nov 17, 2008 8:12 pm Post subject: |
|
|
Love your astute observations, re'born!
(How long's it been, bout a year? since you last posted here....)
Let me see if I understood the concept by re-phrasing it:
When the ends (pincers) of an m-wing ("classic","half" or "generalized", it doesn't matter) share a house ("see" each other), the loop is completed and all weak links turn into strong links, allowing additional eliminations.
Definitely not something that was "well known" to me, and I'll be on the lookout for those situations from now on! |
|
| Back to top |
|
|
re'born
Joined: 28 Oct 2007
Posts: 80
|
| Posted: Mon Nov 17, 2008 9:18 pm Post subject: |
|
|
| nataraj wrote: | Love your astute observations, re'born!
(How long's it been, bout a year? since you last posted here....)
Let me see if I understood the concept by re-phrasing it:
When the ends (pincers) of an m-wing ("classic","half" or "generalized", it doesn't matter) share a house ("see" each other), the loop is completed and all weak links turn into strong links, allowing additional eliminations.
Definitely not something that was "well known" to me, and I'll be on the lookout for those situations from now on! |
Hey nataraj,
It's nice to be back. I've missed you guys and I'm glad the names I see around here are the same as before.
Your rephrasing is exactly what I had in mind and I appreciate your more precise statement. I should note that this idea is a direct result of http://www.sudoku.com/boards/viewtopic.php?p=64249#64249
thread (edit: Link fixed 3/29/2011 - keith.)
over on the player's forum started by Bud. In that thread he presents what he calls a double w-wing. In the end, it is simply cells {a b}, {a b} that are connected by w-wings on both digits. My observation (which I again assume is well-known) is that this gives you a continuous loop (so all weak links turn into strong links) regardless of the relative positions of the two cells (i.e., they don't have to see each other). |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Tue Nov 18, 2008 1:59 am Post subject: |
|
|
| re'born wrote: | | nataraj wrote: | Love your astute observations, re'born!
(How long's it been, bout a year? since you last posted here....)
Let me see if I understood the concept by re-phrasing it:
When the ends (pincers) of an m-wing ("classic","half" or "generalized", it doesn't matter) share a house ("see" each other), the loop is completed and all weak links turn into strong links, allowing additional eliminations.
Definitely not something that was "well known" to me, and I'll be on the lookout for those situations from now on! |
Hey nataraj,
It's nice to be back. I've missed you guys and I'm glad the names I see around here are the same as before.
Your rephrasing is exactly what I had in mind and I appreciate your more precise statement. I should note that this idea is a direct result of thread over on the player's forum started by Bud. In that thread he presents what he calls a double w-wing. In the end, it is simply cells {a b}, {a b} that are connected by w-wings on both digits. My observation (which I again assume is well-known) is that this gives you a continuous loop (so all weak links turn into strong links) regardless of the relative positions of the two cells (i.e., they don't have to see each other). |
I've been staring at this, reaching towards a statement something like that made by nataraj. I was sort of leaning towards some kind of "double M-wing reversible loop" explanation. (I have yet to read Bud's thread.)
| Quote: | | cells {a b}, {a b} that are connected by w-wings on both digits |
In that case, the cells {a b} are a remote pair. Obviously. Why this is remarkable, I do not know. The first W-wing destroys the first candidate, the second the second. Knowing both of them together does not add anything to knowing them separately.
Let me read, and think, some more. When there is a post that includes ravel, re'born, and nataraj in the same breath, I know I am way over my head!
Keith |
|
| 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
