The New Sudoku Players' Forum

[ClarinetMan]

I'm new to "advanced techniques" and cannot understand a point that I've seen quoted several places; namely
"In a continuous nice loop, the weak links can be turned into strong links" Is there a clear explanation of this somewhere?

[Lunatic]

I thought it was the opposite, strong links kan be used as weak links, because strong links mostly derived from weak links. Just think of all removed candidates in a house with a strong link. If one or more of those removed candidates were still present, the strong link would still have been weak. The fact that the removeable candidates are indeed removed, made that link strong, but it may still be considered weak as well.

[daj95376]

[Withdrawn: the topic outgrew my reply.]

[Lunatic]

That's just an Alternating Inference Chain, like this:

aic_0001.gif (13.19 KiB) Viewed 1412 times

Strong links are blue, weak links are orange.
The strong link on candidate 3 from r8c9 to r3c9 is used as weak link.

Am I missing something?

[David P Bird]

Lunatic you have coloured one of your links incorrectly so they don't alternate which invalidates the AIC. Whether this was accidental or not, it illustrates general points about AICs and closed loops.

This is how it should be:
(4=9)r1c9 - (9=3)r8c9 *-* (3=1)r3c9 - (1=4)r2c7 - Loop

f=>t ------> f=>t --------> f=>t -------> f=>t

t<=f <------ f<=t <-------- t<=f <------- t<=f

Two strongly linked arguments can't both be false
Two weakly linked arguments can't both be true
First assume the first argument is false and follow the links left to right to show the last one must be true.
Likewise in reverse if the last argument is false the first one must be true.
So any (4)in sight of (4)r1c9,r3c7 must be false - general AIC proof.
As the loop closes, one of the and arguments must be false and so one or other of these two outcomes must hold.

If the link between (3)r8c9 & (3)r3c9 is shown as strong then by AIC rules they both could be true and the chain won't carry an inference from the argument at one end to the other. We are not using the fact that these are the only two instances in c9 (strong) but rather the fact that c9 can only hold one instance of (3) however many there are (weak).

Now either all the odd arguments are true or all the even ones are, and every link becomes conjugate (exactly one argument is true) and so can be used either as a weak or strong link. Therefore (9)r7c9 can also be eliminated. (For loops that don't close there is nothing to stop both end arguments being true and this doesn't work.)

Further, any candidate that sees an odd and even instance of itself in the loop must be false. This allows eliminations to be made for (x) that sees loop (x)odd_argument and loop (x)even_argument in a larger loop - 'across the loop'.
The arguments don't have to be counted as all those on the right of a weak link are odd and all those on the left of one are even.

As DAJ has shown, all the eliminations in a continuous AIC loop can be demonstrated by breaking the loop in different places or just using a segment of it so there's nothing particularly clever about them which is your point I believe. It's just a lot more convenient to make multiple eliminations from a single chain when it closes on itself with a weak link between the two end arguments.

David

[blue]

I see that David has posted while I've been writing this.

"HI David" ... I'll post this anyway, and then have a look at your post.
Sorry for stepping on it so soon.

P.S.: I see we covered similar ground, but not the same way.

--

Strong links are blue, weak links are orange.
The strong link on candidate 3 from r8c9 to r3c9 is used as weak link.

The terminology has evolved over time ...

In the modern terminology, (2 or) 3 kinds of links are possible between a pair of candidates:

a strong link - at least one must be true
a weak link - no more than one can be true ... or ... at least one must be false.
a conjugate link - both of the above ... or ... exactly one must be true (and the other false)

Long ago, congugate links were just called "strong links".
At some point the importance of "strong links" in the weaker sense mentioned above, was realized.
At that point, people started used "strong link" to mean that (weaker) type of link, and "strong congugate link", or just "conguate link", when the need arose ... to refer to a "link" that can be used in either/both way(s).

This isn't relevant, but I don't think congugate links have much use, nowadays.
The only use I can think of, is in "simple coloring" (and its extensions).

In your illustration, the links that you're calling "strong links", are "(strong) congugate links" in the modern terminology.
As for the link between r8c9 and r3c9, while it is a congugate link, only its "weak" aspect is needed to form the loop.
Note: The existence of the loop here, is not required, for the link to be considered "weak" -- it's a "natural" weak link.

To expand on that last statement (about the loop being "required" or not), and also on Danny's post ...

Code: Select all

 Individual Chains:

 (1=4)r2c8 - (4=9)r1c9 - (9=3)r8c9 - (3=1)r3c9                                      =>  -1 r3c8

             (4=9)r1c9 - (9=3)r8c9 - (3=1)r3c9 - (1=4)r2c8                          =>  -4 r1c8

 (...)

The 2nd chain uses a "natural" weak link bewteen 1r3c9 and 1r2c8.
The 1st chain, is an AIC that starts and ends with a strong link, and as such, it represents an argument that the endpoints are "strongly linked" in the weaker sense -- i.e. that if one is false (e.g. 1r2c8 on the left), then the other must be true (1r3c9 on the right).
If you like, you can say that the existence of the loop, has promoted a the natural weak link, to a strong (congugate) link.
It is weak by its nature; the 1st AIC shows its "strong aspect"; and the (natural) weak part "closes the loop", and allows for the 2nd, 3rd, etc., chains to be divined, and exploited in the manner that Danny indicated.

[Leren]

daj95376 wrote : ..... (1=4)r2c8 - (4=9)r1c9 - (9=3)r8c9 - (3=1)r3c9 - loop => -1r3c8,-4r1c8,-9r7c9

Lunatic wrote : That's just an Alternating Inference Chain, like this: ..... Am I missing something?

I assume that you are having trouble understanding the loop eliminations and why statements like "In a continuous nice loop, the weak links can be turned into strong links" are often made.

Let's see if I can help. You are right in both cases - Yes, it's an Alternating Inference Chain and Yes, you are missing something.

What you are missing is that, in order to prove the eliminations, the continuous loop is really traversed twice - in opposite directions with different starting points.

Let's rewrite the above loop as if it was being traversed from left to right (as it is written). You'll notice that I''m replacing the brackets by the assumed and inferred parity (True or False) of each node in the loop.

We start by assuming that r2c8 is not 1 (ie it's 4, because there is a Strong link in r2c8).

-1=4 r2c8 - 4=9 r1c9 - 9=3 r8c9 - 3=1 r3c9 - loop

Now here's the trick ; go to the other end of the Strong link in r2c8 and assume that r2c8 is not 4 (ie it's 1) and, because you are at the other end of the Strong link in r2c8, you have to traverse the loop in the opposite direction.

You would write the loop as : -4=1 r2c8 -1=3 r3c9 -3=9 r8c9 -9=4 r1c9 - loop.

Notice that when the loop is traversed in the other direction the parity of each node in the loop is the opposite of what it is in the original direction.

Now for the killer observation : r2c8 can only be 1 or 4 (remember, we're using a Strong link for the starting points), so one of the loop traversals is ultimately False and the other is ultimately True.

However, any common outcomes of both loop traversals must apply irrespective of which traversal is True and which is False, because we have covered 100% of cases for cell r2c8.

For the first loop traversal, r3c9 is 1, so r3c8 is not 1. For the second loop traversal, r2c8 is 1, so r3c8 is not 1. That's a common outcome ! - 1 r3c8 is proven !! How cool is that !!!

You'll find similar situations that prove - 4 r1c8 and - 9 r7c9.

In the general case you'll find that for continuous loops, in each Weak link, one of two instances of a candidate in a row, column, box or cell is True for one traversal direction and one is True for the other traversal direction, so all but those two instances of the candidate may be eliminated from cells that both of these nodes can see.

The way daj95376 wrote the loop is correct and notationally efficient but it can be confusing for the inexperienced reader. The brackets indicate that the assumed parity of each node is indeterminate. What you have to do is make an assumption of the parity of the first node you come to, and the operators ( = and - ) will determine the parity of all subsequent nodes. For continuous loops you usually start with a Strong link, so assume the first node is False if reading from left to right and you should find that the last node is True. If reading from right to left assume the last node is False and you should find that the first node is True. Also for continuous loops you can use any one of the Strong links for the starting points and you'll come to the same conclusions.

Hope this helps, Leren

[Lunatic]

Lunatic you have coloured one of your links incorrectly so they don't alternate which invalidates the AIC. Whether this was accidental or not, it illustrates general points about AICs and closed loops.

It was accidental. I noticed it myself after posting, but didn't mind that much because it is indeed a strong link, but used as weak link, so it had to be orange.

Nevertheless, it's almost two years since I visited the forum, and apparently some things changed since. My question that if I missed something, was because I took the reaction from daj95376 serious, and just wanted some explanation about wat has changed over the last two years that I was absent.

Anyway, I see some other posts as well, so they will direct me in the new, right, way, I presume.

[Lunatic]

Ok, let's see if I'm getting it....

On behalf of being able to proof that a candidate can be eliminated, we don't speak about AIC's no more. We proof the elimination of a candidate in a closed loop of strong and weak links, by going trough the loop in both directions starting from a strong link where we take one candidate as true for the first loop, and the other candidate as true for the reverse loop, alternating true/false through both loops. Once the elimination of a candidate (or a multitude of candidates) is proven, by the fact that it (or they) see both instances (False and True) of itself (themself), we can see a weak link becoming a strong link.

[JasonLion]

Not everything is a loop, chains where the two ends don't connect are still used frequently enough.

Just about everything is an AIC, or includes an AIC, however using "AIC" in the description is no longer very common. Most things are now named with more specific names that tell you what specific kind of AIC you have. It is also more common to include other things as links in an AIC, for example using an ALS as a link in a chain seems to be fairly common.

[David P Bird]

Ok, let's see if I'm getting it....

Lunatic, yes you are getting there. The great majority of the patterns you list in your solver can be written as simple AIC chains where the eliminations are made by just the first and last terms. It is only when these terms can't be true together that a loop is formed when the other links in the chain can also produce eliminations.

Closed loops only work when the links in the loop alternate properly between weak and strong so that the logic can be followed in both the forward and reverse directions.

David