Wepwawet wrote:As I understand it, please correct me if I am wrong, that the internal links in an ALS are strong, which makes sense, as it is entered and exited by weak links, so the alternating inference nature of the chain is maintained.
Yes, that is fully correct. In the ANS (almost naked subset) type of ALS the internal links are strong and the external links are weak. In an AHS (almost hidden subset) it's the other way around. ALS is usually used as a synonym for ANS, but it's a bit ambiguous, so I'll use ANS here.
Strong Links within an ANSAn ANS has n cells with n+1 digits as candidates. If
all candidates of any of those digits are removed, the other digits get locked as a naked subset (pair/triple/quad etc). So, any contained digit has a strong link with a naked subset formed of the other digits. I think that's the most intuitive way to see and use ANSs, and that's why I also prefer chains written like that: (1=234)r123c1. It means that either there's a digit 1 (and obviously two other digits, but we don't know or care which) or a naked triple 234 in those three cells. It also follows that any digit has a strong link with any other digit within the ANS, so it's technically correct to write (1=4)r123c1 as well, though I find it harder to read and compare to the grid.
Weak Links surrounding an ANSAs you said, since the ANS has an internal strong link, it must be surrounded by two weak links if used in a chain. They must obviously use different digits. In normal situations only one digit is used for either weak link, but it's also possible to use more on one or both sides for advanced linking. When the AIC is viewed as an implication chain and traversed in one direction, then one weak link enters and the other exits, as you said, but the roles obviously reverse if the chain is read the other way. Either way, what's important is that both weak links must see
all instances of the linking digit(s) in
both the ANS and the linked external nodes. That was the problem in your first example where only one of the locked 3s could see the intended linking target.
An example:
... - (5=23'1)r651c1 - (1=56'4)r1c568 - (4=89'3)r567c8 - ...
If read from left to right, the middle ANS (1456)r1c568 is entered with a weak link on 1 (the exit digit of the previous ANS; must be locked as a single in r1c1 to link to the second ANS), which locks the rest of the digits 456 as a naked triple. Any or all of them could be used for the exiting weak link, but in this case the 4 is used for linking. Again, it must be locked as a single in r1c8 to link to the third ANS in c8.
Btw, I've added the '-separator to highlight the right-linking candidates, though it's normally omitted (still the right-linking candidate(s) should be written last).
Regarding the puzzle I posted on Nov 23rd.
It looks like I am misunderstanding some aspects of ALS's. Are you saying that all instances of the exit candidate that exist in an ALS must see the next node? Deducted from
Your 3[E2|E6] doesn't have a weak link to 3[H6] because E2 doesn't see it, so the chain can't continue beyond that point
Exactly.
If so, then I have missed that point about Almost Locked Sets, I cannot recollect seeing that point stated anywhere. It could explain why I could not fathom out why some of my reasoning failed me in some puzzles. That is the common theme in both of the puzzles, I am hoping that is the answer.
Well, you do know how naked pairs/triples/quads etc work, right? That's what you should think about when considering how the "exit link" works. Once the incoming weak link "removes" one digit (completely) you have a naked subset with the rest. Look at that as a whole and think what it could eliminate in its surroundings if it were in fact a naked pair or triple or so on. Those are candidates with which you can link it. However, you should also look at where the individual digits are located within the locked set because they have different linking potentials (those that get locked as a single or a pointing pair are usually the best).
In your example with the ANS (139)r5c26, the incoming weak link removes the 9 so you're left with a naked pair 13. That far your chain was correct. However, since both digits have candidates in both cells, and they're not even in the same box, there's nowhere but the same row where either of those digits can (simply) link to. In fact, you could use the full pair to remove both 1 and 3 from r5c3 and get a 9r5c3 to continue the chain, but obviously you don't need the ANS for that (9r5c2 is directly strongly linked with 9r5c3).
Further ALS explanation required.
I have gone to the Sudopedia Mirror web page
http://sudopedia.enjoysudoku.com/ALS-XY-Chain.html and it states that ALS C and D have a restricted common of 1, yet ALS D has two 1's in it. Is this being regarded as a grouped node within the ALS (as they share the row), or is it a typo?
It's not a typo. You can have several candidates of the weak-linking digit in both ANSs as long as they all see each other. That's why such a digit is called
Restricted Common (RC) -- the restriction being that at most one of its candidates can be true in the combined cells of both ANSs (definition of a weak link). Btw, Hodoku unfortunately calls the same concept Restricted Common
Candidate (RCC), which is a very confusing misnomer, because it obviously means
digit as well:
Hodoku wrote:To combine two ALS they must share at least one candidate. "Share" means, that all instances of the candidate in ALS 1 see all instances of that candidate in ALS 2. Such a candidate is called a Restricted Common Candidate (or RCC for short).
Replace all instances of "candidate" with "digit" and that sounds about right. It's a totally different situation if two ALSs actually share candidates because it means they have overlapping cells (which can't contain RC candidates between those two ALSs, as Hodoku correctly mentions). Thus, I suggest sticking with Sudopedia (in this case) and "RC" which has no ambiguity.
Anyway, if that restricted digit is true in one ANS, it can't be true in the other, which locks the other digits in the latter. In other words, the presence of an RC between two ANSs guarantees that at least one of them gets locked with the other digits. That in turn means that the chain must propagate to at least one direction as long as both locked sets have a suitable weak link (for example through an RC with another ANS).
Here's my annotated version of the example on that page:
- Code: Select all
.----------------.--------------.-----------------------.
| . a[4]6 . | . . . | d25 d258 . |
| . . . | . . . | . . . |
| . 27-4 . | c3'1 . . | . d1'258 d1'28(4) |
:----------------+--------------+-----------------------:
| . . . | . . . | . . . |
| . . b2'6 | c6'73 . . | . . . |
| . a69'2 . | . . . | . . . |
:----------------+--------------+-----------------------:
| . a[4]69 . | . . . | . . . |
| . . . | c73 . . | . . . |
| . . . | . . . | . . . |
'----------------'--------------'-----------------------'
(4=69'2)r176c2 - (2=6)r5c3 - (6=73'1)r583c4 - (1=258'4)b3p1289 => -4 r3c2
What that AIC proves is that either we have a [4] in r17c2 (i.e. r1c2 or r7c2) or we have a (4) in r3c9 (or both). Either way there can't be a 4 in r3c2 which sees them all. The RCs are: a-
2-b, b-
6-c, c-
1-d. The RC
candidates in the last case are: 1r3c489.
We could also break the three-cell ANSs in c2 and c4 into smaller segments like this (note that the first weak link uses both digits 6 and 9):
(4=69)r17c2 - (6|9=2)r6c2 - (2=6)r5c3 - (6=7'3)r58c4 - (3=1)r3c4 - (1=258'4)b3p1289 => -4 r3c2
Now the RCs are: a-69-b, b-2-c, c-6-d, d-3-e, e-1-f.
Again, the '-separators are there just for educational purposes to highlight the RCs. Normally I only use them with loops to highlight bystander eliminations. So, my normal way to write the first chain would be:
(4=692)r176c2 - (2=6)r5c3 - (6=731)r583c4 - (1=2584)b3p1289 => -4 r3c2
...or if I wanted to highlight the eliminating digit at both ends (also correct but a bit harder to understand):
(4=692)r176c2 - (2=6)r5c3 - (6=731)r583c4 - (1258=4)b3p1289 => -4 r3c2
Note that it would also work (and the chain would be the same) if we had additional 4s in r3c8 and r6c2:
- Code: Select all
.------------------.--------------.--------------------------.
| . a[4]6 . | . . . | d25 d258 . |
| . . . | . . . | . . . |
| . 27-4 . | c3'1 . . | . d1'258(4) d1'28(4) |
:------------------+--------------+--------------------------:
| . . . | . . . | . . . |
| . . b2'6 | c6'73 . . | . . . |
| . a[4]69'2 . | . . . | . . . |
:------------------+--------------+--------------------------:
| . a[4]69 . | . . . | . . . |
| . . . | c73 . . | . . . |
| . . . | . . . | . . . |
'------------------'--------------'--------------------------'
But this wouldn't:
- Code: Select all
.----------------.--------------.-----------------------.
| . a[4]6 . | . . . | d25 d258(4) . |
| . . . | . . . | . . . |
| . 247 . | c3'1 . . | . d1'258 d1'28(4) |
:----------------+--------------+-----------------------:
| . . . | . . . | . . . |
| . . b2'6 | c6'73 . . | . . . |
| . a69'2 . | . . . | . . . |
:----------------+--------------+-----------------------:
| . a[4]69 . | . . . | . . . |
| . . . | c73 . . | . . . |
| . . . | . . . | . . . |
'----------------'--------------'-----------------------'
The same chain is still valid but now it doesn't eliminate anything because 4r1c8 doesn't see r3c2:
(4=69'2)r176c2 - (2=6)r5c3 - (6=73'1)r583c4 - (1=258'4)b3p1289 => nothing
You'd have the same problem if you tried to continue the chain because now the quad 2458 is hard to weak-link with anything. All of its digits, including the 4s, are spread into multiple rows and columns within the box. Thus there's no simple way to link them as a unit with anything outside of the box (though it's possible but rather advanced).
Here's an example of that linking problem. Note the added 1r8c4:
- Code: Select all
.----------------.--------------.-----------------------.
| . a[4]6 . | . . . | d25 d258 . |
| . . . | . . . | . . . |
| . 247 . | c3'1 . . | . d1'258 d1'28(4) |
:----------------+--------------+-----------------------:
| . . . | . . . | . . . |
| . . b2'6 | c6'73 . . | . . . |
| . a69'2 . | . . . | . . . |
:----------------+--------------+-----------------------:
| . a[4]69 . | . . . | . . . |
| . . . | c73'1 . . | . . . |
| . . . | . . . | . . . |
'----------------'--------------'-----------------------'
Now the chain can't advance past this point:
(4=69'2)r176c2 - (2=6)r5c3 - (6=73'1)r583c4 // can't continue
...because 1r8c4 doesn't see the 1s in r3c89. There's no RC and thus no weak link between c and d.
Or even worse if we add 2r1c2:
- Code: Select all
.----------------.--------------.-----------------------.
| . a[4]6'2 . | . . . | d25 d258 . |
| . . . | . . . | . . . |
| . 247 . | c3'1 . . | . d1'258 d1'28(4) |
:----------------+--------------+-----------------------:
| . . . | . . . | . . . |
| . . b2'6 | c6'73 . . | . . . |
| . a69'2 . | . . . | . . . |
:----------------+--------------+-----------------------:
| . a[4]69 . | . . . | . . . |
| . . . | c73'1 . . | . . . |
| . . . | . . . | . . . |
'----------------'--------------'-----------------------'
Now the first ANS can't propagate anywhere, because there's no RC between a and b, so there's no chain at all beyond the internal strong link:
(4=69'2)r176c2 // can't continue