ALS (Almost Locked Sets)
Introduction to ALSs
An ALS (almost locked set) consists of n cells in the same house (row, column, or box) with a total of n+1 distinct candidates. For example, the cells {R2C3, R2C5, R2C7} below together contain the candidates {1, 2, 4, 5}: four distinct candidates in three cells.
To keep the explanations simple, we can represent ALSs with diagrams like these:
Yes, a bivalue cell is also an ALS: one cell with two candidates.
The exact number of cells usually does not matter when discussing ALS techniques, so the diagrams use whichever size makes the explanation easier to follow.
Property of ALSs
An ALS has an important property: if one candidate is eliminated from all n cells, only n distinct candidates remain in those n cells. For example, another technique might show that none of the cells can contain x. The ALS then becomes a locked set, which can be used directly for eliminations as a naked subset: a naked pair, triple, quadruple, and so on. With just one cell, it becomes a single.
In the example below, the four cells {R1C1, R1C3, R2C1, R2C3} form an ALS with the candidates {2, 3, 6, 7, 9}. If we establish or assume that another cell in column 3 contains 9, neither R1C3 nor R2C3 can contain 9. The four cells are left with four candidates, forming a locked set, or naked quadruple. We can then eliminate {2, 3, 6, 7} from the other cells in box 1.
An ALS on its own does not do much, but combining several ALSs gives us many ways to eliminate candidates.
RCC (Restricted Common Candidate)
Suppose two ALSs share a candidate x, and every cell containing candidate x in one ALS sees every cell containing candidate x in the other. We call x an RCC (restricted common candidate) of those two ALSs.
An RCC may have several candidate occurrences in each ALS. Every occurrence in one ALS must see every occurrence of the same digit in the other.
For example, the grid on the left below contains two ALSs: ALS1: {R7C2, R7C8, R7C9} and ALS2: {R9C2, R9C7, R9C8}. Both have candidate 4, and every 4 in ALS1 sees every 4 in ALS2, as the dashed lines show. Thus, 4 is an RCC of the two ALSs.
To keep the grid readable, we usually draw just one dashed line between the closest RCC occurrences, as shown on the right.
ALS1 and ALS2 also share candidate 9, but it does not meet the RCC condition. For example, R7C2:9 does not see R9C7:9. So 9 is simply a common candidate, rather than an RCC. These other common candidates matter too: we will use them for eliminations later.
Properties of RCCs
RCCs let us connect ALSs to form different techniques. If two ALSs have an RCC, then:
- If the RCC digit is placed within the two ALSs, it can appear only once and belongs to just one of them.
- The RCC digit may also be absent from both ALSs.
Every RCC occurrence in one ALS sees every occurrence of the same digit in the other, so the digit cannot be placed in both. Within a single ALS, all cells share a house, so the digit cannot be repeated there either. We also normally require the ALSs to have no cells in common. Even when overlaps are allowed, the RCC must not occur in a cell shared by the two ALSs it connects (see Overlapping ALSs). Thus, any placement of the RCC digit within the pair belongs to just one ALS.
The RCC digit can also be placed outside both ALSs, for example in another cell of the same house.
This gives us the following deductions:
- If the RCC digit is placed in one ALS, it cannot be placed in the other. The other ALS loses a candidate digit and becomes a locked set, allowing eliminations using the naked-subset principle.
- If the RCC digit is placed in neither ALS, both lose that candidate digit and become locked sets, each allowing its own eliminations.
In other words, whenever two ALSs have an RCC, at least one of them must become a locked set.
Let's revisit the example above:
If the 4 in box 9 is placed in R7C8 or R7C9, which belong to ALS1, it cannot be placed in R9C7 or R9C8, which belong to ALS2. ALS2 then becomes a naked triple: the three cells {R9C2, R9C7, R9C8} contain only {3, 8, 9}. This also creates singles, but that does not affect the reasoning here.
If 4 is placed in ALS2, at R9C7 or R9C8, ALS1 instead becomes a naked triple with {1, 8, 9} in {R7C2, R7C8, R7C9}.
The 4 in box 9 could also be placed in R8C9, outside both ALSs. In that case, neither ALS can contain 4, so both become naked triples.
ALS-XZ (One RCC)
Suppose two ALSs have an RCC x and another common candidate z. By the RCC property, at least one ALS must lose x and become a naked subset containing z. If a cell C outside both ALSs sees every z in both, we can eliminate z from C: z must be placed in whichever ALS becomes locked through losing x. There may be more than one choice of common candidate z, or more than one target cell C.
This technique is called ALS-XZ (one RCC). It is an ALS-Chain with just two nodes.
We can also reason through it as a chain, starting with z at one end:
- If
zis not placed in one ALS, that ALS becomes locked, so RCC digitxmust be placed there. The other ALS losesxand becomes locked, forcingzto be placed in that ALS. We can therefore eliminatezfrom the target cell. - If
zis placed in the first ALS, we can eliminatezfrom the target cell directly.
ALS-XY-Wing
An ALS-XY-Wing is a chain of three ALSs connected by two different RCCs, x and y. If the end ALSs share a candidate z that differs from both x and y, we can eliminate z from any cell outside the chain that sees every z in both end ALSs.
- If
zis not placed inALS1, that ALS becomes locked, soxmust be placed there.ALS2then losesxand becomes locked, forcingyto be placed inALS2. Next,ALS3losesyand becomes locked, sozmust be placed inALS3. We can therefore eliminatezfrom the target cell. - If
zis placed inALS1, we can eliminatezfrom the target cell directly.
So z must be placed in at least one of the end ALSs, ALS1 and ALS3, allowing the elimination.
The XY-Wing, classified under alternating inference chains, can also be explained as an ALS-XY-Wing. Each of its three bivalue cells is an ALS with n=1: one cell with two candidates. The digits x and y on the weak links from the pivot to the two pincers are the two RCCs.
ALS-Chain
We can extend an ALS-XY-Wing by adding more ALSs through new RCCs, as long as consecutive RCCs are different. This gives us a longer ALS-Chain. If the end ALSs share a candidate z that differs from the RCCs linking them into the chain, we can eliminate z from any cell outside the chain that sees every z in both end ALSs.
If the shared RCC digit is placed in the preceding ALS, the current ALS loses that candidate digit and becomes locked. Since the incoming and outgoing RCCs are different, the outgoing RCC digit must then be placed in the current ALS, which in turn locks the next ALS. The same reasoning continues through the rest of the chain.
Thus, if z is not placed in the first ALS, that ALS becomes locked, and the effect passes along the entire chain. The ALS at the other end, ALSn, becomes locked too, so z must be placed there.
Likewise, an XY-Chain, another type of alternating inference chain, can be explained as an ALS-Chain made entirely of ALSs with n=1. The common candidate linking two neighboring bivalue cells is their RCC.
ALS-XZ (Two RCCs)
Let's return to a pair of ALSs. Things get interesting when they have two RCCs: both RCC digits must be placed within the two ALSs, one in each.
- If neither RCC digit is placed in either ALS, both ALSs lose two candidate digits. Each goes from
ncells withn+1candidates toncells with onlyn-1candidates. There are not enough distinct digits to fill the cells without repetition, violating Sudoku rules. - If both RCC digits are placed in the same ALS, the other loses two candidate digits and likewise cannot be filled legally.
- If RCC digit
xis placed inALS1,ALS2losesxand becomes locked. Its remaining candidates include the other RCC,z, sozmust be placed inALS2. Likewise, ifzis placed inALS1,xmust be placed inALS2.
So both RCC digits must be placed within the pair, one in each ALS. Both ALSs also become locked because each loses the RCC digit placed in the other.
This gives us two kinds of eliminations:
- Both RCC digits are confined to the two ALSs. For each RCC digit
x, we can eliminatexfrom any cell outside the pair that sees every occurrence ofxin both ALSs. - Both ALSs become locked by losing one RCC. We do not yet know which RCC each loses, but every other candidate digit must be placed within its own ALS. For each non-RCC candidate in an ALS, we can eliminate that digit from any cell outside that ALS that sees all its candidate positions within the ALS.
This technique is ALS-XZ (two RCCs). It arises when the common candidate z in ALS-XZ also meets the visibility condition and becomes a second RCC, allowing a different set of eliminations.
Death Blossom
The techniques above connect several ALSs through RCCs. Another possibility is to connect several ALSs to a single cell.
If every candidate in an unfilled cell forms an RCC with some ALS, the result looks like a flower. The central cell is called the stem cell, and each ALS connected to it is a petal. If all petal ALSs share a candidate z that differs from every RCC linking a petal to the stem, we can eliminate z from any cell outside the flower that sees every z in every petal.
Whatever digit is placed in the stem cell, the corresponding petal ALS loses that candidate and becomes a naked subset. z must then be placed in that petal, so the target cell cannot contain z.
This flower-shaped elimination technique is called a Death Blossom.
Overlapping ALSs
The ALS techniques above normally require the ALSs to be disjoint: no two ALSs share a cell. However, overlaps can also be allowed. The reasoning still works as long as the RCC connecting two ALSs is not confined entirely to the cells shared by those two ALSs.
For example, the grid below contains four ALSs:
ALS1:{R1C2, R1C3, R2C1}, with candidates{2, 3, 4, 7}.ALS2:{R1C2, R2C2, R8C2}, with candidates{2, 4, 6, 7}.ALS3:{R1C7, R1C9, R2C8}, with candidates{1, 3, 4, 6}.ALS4:{R8C5}, with candidates{3, 6}.
ALS1 and ALS2 overlap at cell R1C2.
ALS1 and ALS2 can be connected through RCC 7, because 7 does not occur in their shared cell R1C2.
ALS1 and ALS3 can be connected through RCC 4. Although one 4 is in R1C2, shared by ALS1 and ALS2, not all occurrences of 4 in ALS2 lie in that shared cell: there is another 4 at R2C2. Every 4 in ALS3 sees every 4 in ALS1, but not every 4 in ALS2. So 4 is an RCC of ALS1 and ALS3, but not of ALS2 and ALS3.
ALS2 and ALS4 can be connected through RCC 6. The 6 in ALS2 is not in the shared cell.
Allowing overlaps gives us Overlapping ALS-Chains and Overlapping Death Blossoms, corresponding to ALS-Chains and Death Blossoms respectively.