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 Pair exclusions

 
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: Sun Aug 26, 2007 3:03 pm    Post subject: Remote Pair exclusions Reply with quote

Maybe everyone else knows this, but it was mildly surprising to me.

To make a Remote Pair exclusion, all the cells in the chain do NOT have to have the same candiates.

A remote pair is:

(a)XY==YX==XY==YX(A)

and any cell that "sees" both ends a and A cannot be X or Y. Necessarily, the chain is composed of strong links in both candidates. It must be comprised of an even number of cells (in this case, four) connected by an odd number of links (three).

But, what if the strong links are only for one candidate?

(a)XY==WX==XZ==YX(A)

W and Z are anything - they do not have to represent a single candidate.

One of a and A must be X. AND, one must be Y! The eliminations for both chains are the same.

So, suppose you have two cells that have the same two candidates but are not a naked pair. If you can connect them by simple coloring on either of the candidates, and if the coloring chain has an uneven number of links (even number of cells), you can make the Remote Pair exclusions.

It seems to me this is a possibly useful rule when solving by hand. So far as programming is concerned, it is likely a special case of a number of chain types.

Here is an example:



The cells whose candidates are <36> can be linked by coloring on <3>. They are a remote pair. (There are no exclusions to make in this case.)

Another way to find a chain.

Keith
Back to top
View user's profile Send private message
Marty R.



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

PostPosted: Sun Aug 26, 2007 4:03 pm    Post subject: Reply with quote

Quote:
Maybe everyone else knows this, but it was mildly surprising to me.


Hardly a surprise that I didn't know it. It'll be interesting to see if this situation comes up in actual puzzles. The last new technique I learned was the W-Wing and that comes up often enough to make it a valuable part of the arsenal. I hope this turns out similarly.

P.S. I just realized that this is also a W-Wing, but more powerful, since the rules of the Wing would exclude just the 6 and the Remote Pairs excludes the 36. Now I'm wondering if every one of these Remote Pairs things is also a W-Wing. If so, does that mean that the W-Wing disappears since we have this more powerful tool to replace it?
Back to top
View user's profile Send private message
keith



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

PostPosted: Sun Aug 26, 2007 5:05 pm    Post subject: Reply with quote

Quote:
If so, does that mean that the W-Wing disappears since we have this more powerful tool to replace it?


Marty,

I don't think so. It's one more thing to note while looking for W-wings. If you have two cells with the same pair of candidates, see if you can link them by coloring strong links on either of the candidates. If you can join them, be sure that there is an odd number of links before making any eliminations!

Remember early on, there was some confusion over whether a W-wing allowed you to make eliminations for both candidates? Maybe we were looking at cases like this.

Every one of these is also a W-wing. To see that, simply delete the first and last links of the chain.

Keith
Back to top
View user's profile Send private message
Marty R.



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

PostPosted: Sun Aug 26, 2007 5:21 pm    Post subject: Reply with quote

I just thought of a case where the W-Wing wouldn't fit the Remote Pairs. I can't find the original post, but it involved the pairs connected not by a strong link, but by a de facto strong link for the W-Wing purpose. It was something like:

Code:

+--------+-------+---------+
| .  . . | . . . | . .  .  |
| 36 . . | . . . | . .  37 |
| .  . . | . . . | . .  .  |
+--------+-------+---------+
| .  . . | . . . | . .  .  |
| .  . . | . . . | . .  .  |
| .  . . | . . . | . .  .  |
+--------+-------+---------+
| .  . . | . . . | . .  38 |
| .  . . | . . . | . .  39 |
| .  . . | . . . | . 36 .  |
+--------+-------+---------+

Play this puzzle online at the Daily Sudoku site

The 3s are the link to the 36 pairs but the connection in column 9 isn't a strong link so it wouldn't allow the Remote Pairs chain, but serves for the Wing because two of the 3s are in the same box.
Back to top
View user's profile Send private message
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Sun Aug 26, 2007 7:26 pm    Post subject: Reply with quote

Marty,

I believe that your example does, in fact, qualify as a remote pair with both exclusions allowable. The link in C9 is, in fact, strong: R78C9 share a polarity with respect to R2C9 and R9C8.

However, if there were a <3> candidate somewhere in C9 of Box 6, then the link would be weak and we would have the usual W-Wing with only <6> exclusions possible.

The key is whether or not the two links from the remote bivalue cells to the external strong link are themselves strong. If so, then it is a remote pair. If one or both are weak, then it is the more limited W-Wing.
Back to top
View user's profile Send private message Visit poster's website
Mogulmeister



Joined: 03 May 2007
Posts: 695

PostPosted: Sun Aug 26, 2007 8:04 pm    Post subject: Reply with quote

Very interesting on remote pairs is our old friend Andrew Stuart.
Back to top
View user's profile Send private message
keith



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

PostPosted: Sun Aug 26, 2007 9:00 pm    Post subject: Reply with quote

Mogulmeister wrote:
Very interesting on remote pairs is our old friend Andrew Stuart.

He makes them sound pretty complicated!
http://www.scanraid.com/AdvanStrategies.htm#RP
and I don't see that he mentions what we are discussing here.

Not that this is earth-shattering. I just think, if you're going to look for W-wings, you may as well look for these remote pairs.

Keith
Back to top
View user's profile Send private message
Marty R.



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

PostPosted: Sun Aug 26, 2007 9:13 pm    Post subject: Reply with quote

Asellus,

I think it was you who pointed out a few weeks ago that a W-Wing works with the arrangement in column 9 that I illustrated. I am extremely weak as a theorist and logician, but I think I see where you're coming from when you explain that it's also Remote Pairs.

As an example of my theory skills:

"For two candidates, named A and B, the following strong inference deductions can be made:

* If A is false, B is true.
* If B is false, A is true. "

"For two candidates, named A and B, the following weak inference deductions can be made:

* If A is true, B is false.
* If B is true, A is false. "

I'll be darned if I can see a difference between strong and weak inference from reading the above.

Quote:
However, if there were a <3> candidate somewhere in C9 of Box 6, then the link would be weak and we would have the usual W-Wing with only <6> exclusions possible.


However, I don't understand how a 3 in c9 of box 6 would not destroy the W-Wing. Doesn't the very definition of the technique require a strong link to connect the pairs?
Back to top
View user's profile Send private message
keith



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

PostPosted: Sun Aug 26, 2007 9:48 pm    Post subject: Reply with quote

Marty,

The required pattern for a W-wing is

WX (weak link) X (strong link) X (weak link) WX

allows you to eliminate W in all cells that "see" the end cells. If all the links are strong, it is a remote pair: You can eliminate W and X in all the cells that see the end cells.

Let's try this.

There are two W-wings.

The first is on <36>, with a strong link on <3>, so it eliminates <6>.

The second is on <17> with a strong link on <7>, so it eliminates <1>.

Now, the first one also has strong links on <3> in R3 and R9 that connect it all together. It is also a remote pair, see the first figure in this thread.

The second does have a strong link on <7> in C4, but there is not a strong link in C5. It is not a remote pair.

So, if == is a strong link, and -- is a weak link:

WX--XY==XZ--WX is a W-wing

WX==XY==XZ==WX is a W-wing and a remote pair.

In between,

WX==XY==XZ--WX is a W-wing, no more.

(And, by the way, in the given example, neither W-wing makes any eliminations.)

Keith
Back to top
View user's profile Send private message
Marty R.



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

PostPosted: Mon Aug 27, 2007 1:33 am    Post subject: Reply with quote

Keith, thank you. I have executed numerous W-Wings, because I think I know them when I see them, even if I don't understand all the terminology and notation. And I understand (I think) what you pointed out today about how we can have a remote pair situation even when the pairs aren't the same.

Despite the talk of weak links being involved in W-Wings, all I can see are what I think are strong links. When a long time ago people were trying to pound multi-coloring into my head, I was told that the chains had to be weakly linked, which meant there were three candidates in the house from which the chains emanated.

So it looks like I will remain in a permanent state of confusion. Embarassed
Back to top
View user's profile Send private message
Asellus



Joined: 05 Jun 2007
Posts: 865
Location: Sonoma County, CA, USA

PostPosted: Mon Aug 27, 2007 5:38 am    Post subject: Reply with quote

Marty,

I erred about the <3> in Box 6 Column 9. You are correct: it would indeed destroy the W-Wing!

The part that is tricky to see is that even though there are three cells with candidate <3> in Box 9, it is still a strong link between the 36 bivalue in R9C8 and the two cells with candidate <3> in C9 of Box 9 when they are considered as part of a chain connecting the two W-Wing bivalue cells. This would be true even if there were also a <3> candidate in R9C9. However, if there were a <3> candidate anywhere else in Box 9, then the link would be weak and we would have the "lesser" W-Wing, not the "stronger" remote pairs.

The connection between any two of the three cells within Box 9 is indeed weak when considered as such. But, considered as a link between R9C8 and the (3-cell) column fragment of C9 in Box 9, the link is strong.

As for the logic of strong and weak links, I've already posted what may be more than enough about that in the "W Link" thread on this forum. I'll just note that the definition you quote is important in the context of understanding implication chains.

PS: It is true that in multi-coloring (or a "color wing") two separate strongly linked color clusters are joined by a single weak link. In that case, the weak link normally is due to there being three or more candidate cells within the same House, as you note.
Back to top
View user's profile Send private message Visit poster's website
Mogulmeister



Joined: 03 May 2007
Posts: 695

PostPosted: Mon Aug 27, 2007 10:33 am    Post subject: Reply with quote

Quote:
I don't see that he mentions what we are discussing here


No - but this is interesting when you look at remote pair elimination. He goes into a bit more detail in his book.
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
Page 1 of 1

 
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