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 

X-Chain

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology
View previous topic :: View next topic  
Author Message
Marty R.



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

PostPosted: Sun Dec 02, 2007 6:26 pm    Post subject: X-Chain Reply with quote

This is an illustration of an X-Chain from Sudopedia. At first glance it looks like a simple coloring chain until one notices the third 3 in column 5. Two questions:

1) How can the chain proceed with the third 3 in column 5?

2) People have tried explaining this before, but it hasn't penetrated my thick skull: what makes the link in column 8 a weak one but the links in boxes 5, 6 and 9 strong ones?

Back to top
View user's profile Send private message
Asellus



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

PostPosted: Sun Dec 02, 2007 10:24 pm    Post subject: Reply with quote

Let me attempt the answer:

In inference logic, a conventional strong "conjugate" or "either-or" link can be thought of as a "wild card" link since it fulfills both strong and weak inference logic.

So... yes, the link in C8 is "strong" in the conjugate sense, but it can serve as a weak link for inference purposes.

In Alternate Inference Chaining (AIC, which is what this is), one can also exploit what can be called a "strong inference link" or "inferential strong link," which is different from the conventional strong conjugate link. The readers of this forum are already familiar with such links. For example, the pincers digits of an XY-Wing/Chain or of a W-Wing, etc., generally have a strong inferential link rather than a conjugate link because it is possible that both are true, but impossible that both are false.

Once you let a weak link or a strong inferential link into your chain, you must keep strict track of the alternating link types: strong-weak-strong-weak-strong, etc. Weak links are only allowed at the weak positions. Strong inferential links are only allowed at the strong positions. Strong conjugate links are allowed anywhere. The two pincer ends of the chain must be connected to the chain by strong link positions. (Eureka notation is very helpful for keeping track of this. And, there is no particular reason to limit such chains to a single digit. But, those are whole other discussions.)

By the way, if your chain meets up with itself and forms a complete alterating implication loop, then all of the links become conjugate links and you can eliminate all candidates that can see both pairs of each successive "node". (An XY Loop is an example of this. But it works the same with any AIC Loop.)


For those so interested...

About that inference logic:

Weak Inference exists whenever we can say: "If candidate A is true, candidate B must be false." This exists whenever it is impossible for both candidates to be true. Both weak links and conjugate (strong) links meet this requirement.

Strong Inference exists whenever we can say: "If candidate A is false, candidate B must be true." This exists whenever it is impossible for both candidates to be false. Both conjugate (strong) links and inferential strong links meet this requirement.

I hope this helps to clear up this perennially confusing issue.
Back to top
View user's profile Send private message Visit poster's website
nataraj



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

PostPosted: Sun Dec 02, 2007 10:32 pm    Post subject: Reply with quote

Marty, I assume by "third 3 in col 5" you refer to third "3" in row 8 which happens to be in col 5. I'll try and answer your 2 questions.

Q: "How can the cain proceed"
A: The complete loop would include two more (weak) links:
one in col 4 one in row 8. That r8c4 has TWO weak links is what's called the discontinuity (because all the rest of the loop has alternating weak and strong links). Any cell that has two weak links in an otherwise strictly alternating loop cannot contain the candidate (that's why 3 is removed from r8c4)

Q:"what makes the link in col 8 a weak one ..."
A:Because we WANT it to be weak.
Any strong link can stand in for a weak link (not vice versa).
To view this link as "weak" is only a matter of choice but it allows us to see the whole loop as alternating between strong and weak links (except for the discontinuity).

The diagram shows that in order to use the logic of AIC (alternating inference chains) or "nice loops", you can take consecutive sequences of 1,3,5,... strong links (must be an even number. with 3 strong links just view the middle one as weak)

Hope this helps.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Marty R.



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

PostPosted: Mon Dec 03, 2007 12:34 am    Post subject: Reply with quote

Thank you both for again trying to explain this.

Quote:
Marty, I assume by "third 3 in col 5" you refer to third "3" in row 8 which happens to be in col 5. I'll try and answer your 2 questions.


No, but I did make an error. There is a third 3 in row 5, in column 1. It boggles my mind how that chain can exist with that situation. Question
Back to top
View user's profile Send private message
keith



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

PostPosted: Mon Dec 03, 2007 3:41 am    Post subject: Reply with quote

Marty,

Let me try.

Strong link =:

Two candidates in a house. One must be true.


Weak link -:

Three or more candidates in a house. One must be false.


(House = row, column, or box.)


Here is a skyscraper:

x=x-x=x


Code:
+-------+-------+-------+
| . . . | x . . | # # # |
| . . . | # # # | x . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | x . x | x . . |
+-------+-------+-------+

Weak link in R9. Strong links in C47.

One of R9C47 must be false. One of R1C4 and R2C7 must be true. Eliminations can be made in any cell marked #.

The way you argue it is this:

Code:
+-------+-------+-------+
| . . . | x . . | # # # |
| . . . | # # # | X . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | X . x | x . . |
+-------+-------+-------+


Assume R1C4 is false. R9C4 must be true. R9c7 is false. R2C7 must be true.

And, vice-versa. Assume R2C7 is false. ... R1C4 must be true. Thus:

One of R1C4 and R2C7 must be true. Eliminations can be made in any cell marked #.

In a strong link: One is true.
In a weak link: One is false.

So, you can make chains of alternating strong and weak links:

x=x-x=x-x=x

If x is false and X is true, starting from false at each end:

From the left: x=X-x=X-x=X

From the right: X=x-X=x-X=x

In your picture, start at one end, assuming the value is false. You will find the other end of the chain is then true. And, if the other end is false, the first end is true. One (or both) is true, you can make the elimination.

That said, it's like Swordfish. Rare enough that I don't worry about them.

Best wishes,

Keith
Back to top
View user's profile Send private message
Asellus



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

PostPosted: Mon Dec 03, 2007 5:44 am    Post subject: Reply with quote

Marty wrote:
There is a third 3 in row 5, in column 1. It boggles my mind how that chain can exist with that situation. Question

Ah... since you didn't ask that question, I thought it was clear. As Keith says, the <3>s at R5C5 and R5C9 are weakly linked precisely because there is another <3> in R5. It is possible that both of these <3>s can be false (if R5C1 is actually <3>). But, they can't both be true, hence they are weakly linked.

In your graphic, the strong link positions are solid lines and the weak link positions are dashed lines. The R5 weak link occurs at a dashed line position so all is in order. The ends of the chain at R4C4 and R8C7 are connected to the chain by strong link positions. So, they can function as Pincers to eliminate the <3> in R8C4.

If you lopped off those two end cells of the chain and let it end at R5C5 and R9C8, you wouldn't have Pincers and no eliminations are possible because they are joined to the chain by weak link positions.

These are mechanical rules and can be followed successfully even if you don't really understand the underlying logic. (I'm not going to attempt to explain it again here; Keith has made an effort to do so.)

The relationship between the Pincer candidates, by the way, is an inferential strong link: one or both of them must be true. In essence, the intervening chain is just a way to fuse those two terminal strong links together into an inferential strong link by following the AIC rules.

I'm going to write the chain in your graphic using non-abbreviated Eureka notation since I believe it helps to see how the notation supports the rules. For those who don't already know, "=" denotes a strong link position and "-" a weak link position. Think of "=" as the solid connecting line and "-" as the dashed connecting line. The two symbols must alternate:

(3)R4C4=(3)R5C5-(3)R5C9=(3)R6C8-(3)R9C8=(3)R8C7

The pincers are weakly linked to their "victims". So, the complete notation, showing the elimination, is:

(3)R8C4-(3)R4C4=(3)R5C5-(3)R5C9=(3)R6C8-(3)R9C8=(3)R8C7-(3)R8C4; R8C4<>3

"R8C4<>3" means "R8C4 is not <3>."

[To abbreviate the notation, RC addresses are collapsed with the involved linked digits combined within parentheses, thusly:
(3)R8C4-(3)R4C4=(3-3)R5C59=(3-3)R69C8=(3)R8C7-(3)R8C4; R8C4<>3
It is exactly the same, but easier to type.]


keith wrote:
That said, it's like Swordfish. Rare enough that I don't worry about them.

Well, I would differ. These sorts of chains are actually extremely common. However, folks mostly see them as Skyscrapers or Kites or Turbot Fish or as more general applications of Multi-Coloring/Color Wing (which is what your graphic example is).

Why see them as AICs then? Well, because those named patterns don't cover all the bases. Notice how many posts there have been lately about "transporting" (or coloring from) pincers. This is just a way to pick up more of these AIC situations without naming them as such. But why not go all the way and get the full benefit?

Multi-Coloring from weak or inferential strong link "Bridges" between color "clusters" involves at least mental marking and learning and remembering the coloring rules. ("Which color pair performs eliminations in this situation???") Using AIC, with the help of Eureka, and there is no need for either.

Your example has just the single weak link in the chain (not counting the victim links); the rest are conjugate links. However, it is no problem to construct a chain that exploits multiple weak links as long as they occur in the proper alternate positions. The chain can also exploit inferential strong links, such as those between the pincer digits of an otherwise useless XY-Wing or W-Wing. An interesting inferential strong link situation to exploit occurs in URs that have two trivalue cells: one or both of the extra digits in those two cells must be true to avoid the deadly pattern. So, they are inferentially strongly linked and are fair game for an AIC.


And, a couple of clarifications from Keith's post...

The Skyscraper graphic should really be shown as:
Code:
+-------+-------+-------+
| . . . | x . . | . # # |
| . . . | . # # | x . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | x . x | x . . |
+-------+-------+-------+

I have removed two of the "victim" marks (#). If there are victim candidates in those cells, then no Skyscraper exists! (Since Keith is stressing the strong conjugate links in the two columns, there'd better only be two candidate digits in those columns.)

keith wrote:
Weak link -:

Three or more candidates in a house. One must be false.

This should say "All but one must be false." However, you are linking just two of those three or more candidates within that house and you don't know where the actual true candidate is located. So, it is possible that both the the linked candidates can be false, but impossible for both to be true. It is this last point that is essential in a weak (inferential) link.
Back to top
View user's profile Send private message Visit poster's website
Marty R.



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

PostPosted: Tue Dec 04, 2007 6:03 am    Post subject: Reply with quote

Can I be obnoxious and ask one more time: despite various explanations, I am no closer to understanding the part of the chain in row 5 with three occurrences of 3.

Please, tell me the example is in error or explain it as if talking to your eight-year-old granddaughter. Question Very Happy

Thank you for your patience.
Back to top
View user's profile Send private message
re'born



Joined: 28 Oct 2007
Posts: 80

PostPosted: Tue Dec 04, 2007 10:35 am    Post subject: Reply with quote

Marty R. wrote:

Please, tell me the example is in error or explain it as if talking to your eight-year-old granddaughter. Question Very Happy

Well, if I had an eight-year-old granddaughter, she would have been born when I was 20. I'm not sure how that would work... Laughing

Anyway, let me take a stab at it an explanation. An x-chain always looks something like this:
A =x= B -x- C =x= D -x- E =x= F
where the lenght of the chain may vary. Reading A =x= B left to right one would say, "if A is not x, then B is x", and right to left it would read, "if B is not x, then A is x". Reading B -x- C left to right one would say "if B is x, then C is not x" and right to left, "if C is x, then B is not x".
The way one can read the whole chain is (left to right):
-If A is not x, then B is x.
-If B is x, then C is not x.
-If C is not x, then D is x.
-If D is is x, then E is not x.
-If E is not x, then F is x.
So, if A is not x, then F is x and so any cell that sees both A and F is not x.

You can also read it right to left and get the same conclusion.

Now what all you need to do is check that all of the above statements are true for the chain in your picture. Start with A=r4c4 and B=r5c5. Certainly if A is not 3, then B is 3 since there are only two 3's in box 5. Now let C=r5c9. Again, if B is 3, then C is not 3 since they are in the same row.

[Note that one could have chosen C=r5c1 or C=r8c5 and we would be able to say the exact same thing.]

Now let D=r6c8. If C is not 3, then D is 3 since there are only two 3's in box 6. Let E=r9c8. if D is 3, then E is not 3 since they are in the same column. Finally, let F=r8c7. If E is not 3, then F is 3, since there are only two 3's in box 9. We conclude that if A is not 3, then F is 3 and hence r8c4 (which sees both A and F) is not a 3.
Back to top
View user's profile Send private message
Marty R.



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

PostPosted: Tue Dec 04, 2007 6:29 pm    Post subject: Reply with quote

Thanks re'born, I finally see it, but not because I can understand the notation. What I'm seeing is what I call an ordinary XY-Chain. If r4c4 =3, then the 3 in r8c4 is zapped. If r4c4 is not = 3, then the chain proceeds to r8c7 for the pincer effect. I've been staring at the chain thinking that it was supposed to work with either value in r4c4.

Thanks again.
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