| Main Page - Back |
|
Alternating Inference Chains From sudokuwiki.com, the puzzle solver's site 
|
| This article needs updating in light of changes to the solver in March 2010, particularly the representation of chains |
| If there is a super-theory of sudoku, or a strategy which encapsulates much of what we’ve discussed so far, it has to be Alternating Inference Chains (AICs). It’s very useful to split out chain-like strategies into X-Wings, XY-Chains, Forcing Chains, XYZ-Wings, X-Cycles, Nice Loops and so on, since they have special characteristics which make them spottable. But it turns out they are all part of a large extended family. The chief characteristic of all chains is that they start on a candidate which has a strong inference to another candidate, which then has a weak inference to the next candidate, and so on, alternating until the start point is reached. This may not have been apparent with XY-Chains, for example, which were not described in this way, but that was because of their special spottable characteristics. We’ll re-cast these previous examples as AICs later on. But AICs can often do tricks that none of the other strategies can hope to replicate, which means that we can use them to generalize and expand our solving armoury. As we saw in the previous chapter, alternation is just what X-Cycles are about. However, you’ll remember that X-Cycles are applied only to a single candidate number. AICs, on the other hand, take everything from an X-Cycle and extend the logic to as many different candidate numbers as necessary. AICs ask the question “How many ways are there to make a strong or a weak link?” If there is more than one way, we can join them up in an alternating manner and make deductions leading to eliminations. Let’s look back on the previous chain-like strategies and note the following:
There is also a third way (Almost Locked Sets, covered on another page), but for now let’s keep it simple and stick to these two dimensions – links between cells and within cells. But what about grouped nodes used in X-Cycles? They seem to be a mixture of both. To gather grouped nodes under one of the two types, we need to drop “candidate” and think of a “candidate premise”. The candidate premise for a single digit X in a cell is telling us that “X is true for this cell”. A grouped node is simply a candidate premise that “X is true in cells A, B or C”. We can form a link to or from a grouped node on the same digit (bi-location) or within one or more of the cells in the node to a different digit (bi-value). |
More complicated candidate premises are possible, such as “candidates X, Y and Z are all true in cells A, B and C” – which is just what we need for a WXYZ-Wing. Mostly, a candidate premise will refer to a single candidate, certainly in the first part of this chapter. Once we know how to construct these loops, we can start making deductions. Let’s look at the example on the right. AIC Rule 1, 1 taken off J9 - chain ends: A9 J3 AIC on 1 (Alternating Inference Chain, length 6): 1[A9]=3[A9]-3[A7]=3[J7]-3[J3]=1[J3]- |
 AIC Example: Load Example or : From the Start |
| Here we have a classic and pleasingly short Alternating Inference Chain with one discontinuity. We’re using Nice Loop Rule 3, which tells us that the candidate between two weak links can be removed, in this case the 1 in J9. How does this loop work? Let’s start in A9 on number 1. If 1 is not the value of this cell, then 3 must be (there’s a strong link from 1 to 3 in A9, which is bi-value). Next, we go from the 3 in A9 to the 3 in A7. There are more than two 3s in that row so the link must be weak (although even if there were only two, a strong link could be declared as having weak inference). We stick with 3 at this point to make a link of strong inference down to J7 (there being only two 3s in this column), then a link of weak inference to J3 (there being four 3s in row J). Finally, J3 is bi-value, so a strong link exists to the 1 there. In summary, our logic goes as follows:
A nice feature of AICs is that they are bi-directional – they work in both directions. To re-cast this chain the other way, we could argue:
|
| This next example is an interesting use of the AIC which is fairly common. It helps us decide which candidates in a Naked Pair are the solutions. The solver gives us this information: AIC Rule 2, on 7 (Alternating Inference Chain, length 6): 5[A7]=5[A3]-5[C2]=7[C2]-7[H2]=7[H7]- - Chain ends A7 cannot be 7 and H7 cannot be 5 The two ends of the chain share a unit in common - column 7. One can reason several ways, such as
|
 AIC Example 2: Load Example or : From the Start |
| So the chain is safely bi-directional and we must conclude that 7 can't be in A7 and 5 can't be in H7. |
| Some AICs are continuous - that is they form a ring or loop and one can follow the logic around from any starting point and in either direction. The solver will sometimes return an example as 'AIC Rule 3' - which I explain here. Thanks to a reader for providing the example. It's quite a long chain and I've drawn the links between the candidates - think line being strong links, double thin line being weak links. Although it starts on A5 this is only because the solver starts searching in the top row. - Node G6 can only be (9/7), removing 2/4 - Node B3 can only be (7/5), removing 2 AIC Rule 3, on 6 (Alternating Inference Chain, length 12): 6[A5]=9[A5]-9[G5]=9[G6]-7[G6]=7[G2] -7[J3]=7[B3]-5[B3]=5[B5]-5[C5]=6[C5]- |
 AIC Rule 3: From the Start |
| This AIC is full of links between cells (bi-locational) and within cells (bi-value). The interesting cells are the two where eliminations are made. The Rule here concerns weak links within the same cell where other candiates are present. The chain is acting like a very long, extended Hidden Pair. Where a Hidden Pair can be proved, the other candidates can be removed. So, the weak links in B3 and G6 are saying if NOT A then B. Taking B3, we are assured that if 5 is not the solution 7 will be and vis versa. We don't know which yet, but the 2 can go. Where you can identify a chain which is closed, any bi-value weak link can lose unused candidates |
