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 

Remote Pairs, and some variants
Goto page 1, 2  Next
 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology
View previous topic :: View next topic  
Author Message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Sat Nov 17, 2007 9:57 pm    Post subject: Remote Pairs, and some variants Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Sat Dec 29, 2007 6:55 am    Post subject: Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Sat Dec 29, 2007 7:49 am    Post subject: Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Sat Dec 29, 2007 8:15 am    Post subject: Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Sat Dec 29, 2007 8:17 am    Post subject: Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Sat Dec 29, 2007 8:17 am    Post subject: Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Sat Dec 29, 2007 9:29 am    Post subject: Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Mon Jan 28, 2008 10:02 pm    Post subject: Reply with quote

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
View user's profile Send private message
Marty R.



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

PostPosted: Mon Mar 17, 2008 12:35 am    Post subject: Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Mon Mar 17, 2008 1:53 am    Post subject: Reply with quote

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
View user's profile Send private message
Marty R.



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

PostPosted: Mon Mar 17, 2008 3:53 am    Post subject: Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Sat Nov 01, 2008 8:22 pm    Post subject: Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Sun Nov 09, 2008 8:17 pm    Post subject: Reply with quote

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
View user's profile Send private message
Marty R.



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

PostPosted: Sun Nov 09, 2008 10:26 pm    Post subject: Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Sun Nov 09, 2008 11:16 pm    Post subject: Reply with quote

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
View user's profile Send private message
Marty R.



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

PostPosted: Sun Nov 09, 2008 11:47 pm    Post subject: Reply with quote

Thanks Keith. I don't expect to use this very often, but it may help me in detecting patterns.
Back to top
View user's profile Send private message
re'born



Joined: 28 Oct 2007
Posts: 80

PostPosted: Mon Nov 17, 2008 4:06 am    Post subject: Reply with quote

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
View user's profile Send private message
nataraj



Joined: 03 Aug 2007
Posts: 1029
Location: Vienna, Austria

PostPosted: Mon Nov 17, 2008 8:12 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
re'born



Joined: 28 Oct 2007
Posts: 80

PostPosted: Mon Nov 17, 2008 9:18 pm    Post subject: Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3165
Location: near Detroit, Michigan, USA

PostPosted: Tue Nov 18, 2008 1:59 am    Post subject: Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
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