Alternating Inference Chains (AIC)

Sudoku is fundamentally a logic puzzle. We use the Sudoku rules and the given digits on the board to deduce, through logical reasoning, what must go into the empty cells.

Propositions

In logic, a proposition is a statement that can be answered with true or false. In Sudoku, the simplest kind of proposition is “a certain digit is in a certain cell.” There are also broader propositions, such as “this digit is in one of these cells.”

For example, on the board above, “$1$ is in $R1C1$” is a proposition. We may not yet know whether it is true or false, but eventually it must be one or the other.

If we look at column $C1$, we find that digit $1$ can appear only in $R1C1$. By the Sudoku rule that each digit must appear exactly once in every house (row, column, or box), we can conclude that this proposition is true.

By contrast, “$5$ is in $R1C1$” is also a proposition, but it is false. Digit $5$ already appears in row $R1$ at $R1C9$, so $5$ cannot go in $R1C1$.

Propositions corresponding to given digits and answer digits are known to be true. For example, the $7$ in $R1C2$ is given by the puzzle, so the proposition “$7$ is in $R1C2$” is true. Earlier, we also proved that “$1$ is in $R1C1$” is true, so we can place $1$ there as an answer digit.

Each candidate also corresponds to a proposition, but its truth value is still undecided. If the proposition is proved false, we eliminate the candidate. If it is proved true, we promote the candidate to an answer digit.

Links

If two propositions can affect each other's truth value, then there is a link between them.

Using the same board, now focus only on candidate digit $4$. Consider the two propositions “$4$ is in $R1C3$” and “$4$ is in $R1C5$.” We may not know the truth value of either proposition, but Sudoku tells us that if either one is true, the other must be false, because a row can contain only one $4$.

So there is a link between the propositions “$4$ is in $R1C3$” and “$4$ is in $R1C5$.”

Weak Links

This kind of relationship, where one proposition being true forces the other to be false, is called a weak link. Put differently, in a weak link at least one of the two propositions is false, or the two propositions cannot both be true.

Weak links are everywhere in Sudoku. Because a digit can appear only once in any house, two occurrences of the same candidate digit in the same row, column, or box are weakly linked. On the board above, for example, “$4$ is in $R1C3$” and “$4$ is in $R2C3$” form a weak link, because column $3$ can contain only one $4$.

Weak links also exist between candidates in the same unfilled cell. A cell must contain exactly one digit, so any two candidates in that cell form a weak link. Here, we consider only cells with at least two candidates. A cell with no candidates indicates that the current board state is invalid, either because the puzzle itself is invalid or because an incorrect answer digit was placed earlier. If a cell has only one candidate, a single technique applies, and that candidate can be promoted to an answer digit.

In cell $R1C5$, for instance, the candidates are $1$, $4$, and $8$. Each pair is weakly linked. Consider candidates $1$ and $4$: if “$1$ is in $R1C5$” is true, then $R1C5$ cannot contain $4$, so “$4$ is in $R1C5$” must be false.

Strong Links

The weak-link reasoning above starts from proposition $A$ being true and derives that proposition $B$ is false. The reverse direction means that if $B$ is true, then $A$ is false. It does not mean that if either proposition is false, the other must be true.

But the Sudoku rule “appears exactly once” means not only “at most once,” but also “at least once.” That gives us stronger and more useful links. On the same board, in box $5$, look at “$4$ is in $R5C5$” and “$4$ is in $R5C6$.” They already form a weak link, but since candidate $4$ appears in box $5$ only in those two cells, and every box must contain one $4$, we get something more: if “$4$ is in $R5C5$” is false, then “$4$ is in $R5C6$” must be true. The same reasoning applies in the reverse direction, if “$4$ is in $R5C6$” is false, then “$4$ is in $R5C5$” must be true.

Likewise, if an unfilled cell has only two candidates, those two propositions also form a strong link. For example, if cell $R5C4$ has only $7$ and $9$, then if “$7$ is in $R5C4$” is false, “$9$ is in $R5C4$” must be true.

This kind of relationship, where one proposition being false forces the other to be true, is called a strong link. Put differently, in a strong link at least one of the two propositions is true, or the two propositions cannot both be false.

Note that every strong link is also a weak link, because it still satisfies the weak-link condition that if one proposition is true, the other is false. So whenever a solving technique requires a weak link, a strong link can be used there as well.

Link Diagrams

When discussing chain techniques, we often draw diagrams of links between propositions. In these diagrams, propositions are shown as small filled circles, also called nodes. A dashed line represents a weak link, and a solid line represents a strong link.

Eliminations with Strong and Weak Links

One important use of strong and weak links is candidate elimination.

If there is a strong link between two propositions, and a third proposition $X$ forms weak links with both ends of that strong link, then $X$ must be false.

As shown above, propositions $A$ and $B$ form a strong link, while proposition $X$ forms weak links with both of them. Since at least one of $A$ and $B$ must be true, and either one being true forces $X$ to be false, $X$ must be false no matter which end is true. If $X$ is a candidate proposition, that candidate can be deleted.

Returning to the earlier board:

We already saw that “$4$ is in $R5C5$” and “$4$ is in $R5C6$” form a strong link. Now observe that “$4$ is in $R5C7$” forms weak links with both of them, so “$4$ is in $R5C7$” must be false, and candidate $4$ can be removed from $R5C7$.

This specific case is exactly the Locked Candidates technique. In fact, the same logic also removes the $4$ from $R5C9$. Many candidate-elimination techniques can be understood in terms of strong and weak links. They are often taught as more visual patterns because those patterns are easier to spot on the board.

Bivalue Cells and Conjugate Pairs

The elimination logic above shows that strong links are the core of the reasoning, while weak links play only a supporting role. A strong link allows us to conclude that at least one of two propositions must be true; weak links can then be used to show that another proposition must be false.

So how do we find strong links? Whenever Sudoku imposes an “exactly one” condition and exactly two propositions can satisfy it, those two propositions form a strong link.

From the perspectives of cells and houses, the two most natural kinds of strong links are bivalue cells and conjugate pairs.

A bivalue cell is an unfilled cell with exactly two candidates. For example, if $R5C5$ contains only $3$ and $4$, then “$3$ is in $R5C5$” and “$4$ is in $R5C5$” form a strong link.

A conjugate pair is a pair of positions for the same candidate digit $d$ in a single house, where that digit appears exactly twice. For example, if candidate $5$ appears only in $R7C3$ and $R7C7$ within row $7$, then “$5$ is in $R7C3$” and “$5$ is in $R7C7$” form a strong link.

Grouped Nodes

Propositions do not have to be limited to the simple form “this digit is in this cell.” They can also be grouped, as in “this digit is in one of these cells.”

For example, on the board above, candidate digit $6$ in box $5$ may at first seem to create only weak links. But if we group the positions, we can derive a strong link. The $6$s in that box are confined to row $5$ and column $5$, so we can divide them into two groups: one group is $R5C4$, $R5C5$, and $R5C6$ in the same row; the other is $R4C5$ and $R6C5$ in the same column. This gives two propositions:

• Proposition $A$: $6$ is in one of $R5C4$, $R5C5$, or $R5C6$.
• Proposition $B$: $6$ is in one of $R4C5$ or $R6C5$.

Because box $5$ must contain exactly one digit $6$, at least one of $A$ or $B$ must be true. So $A$ and $B$ form a strong link.

Each of these propositions combines several simple propositions into one. For example, proposition $A$ is a disjunction: $6$ is in $R5C4$, $R5C5$, or $R5C6$. When such a compound proposition is treated as a node in a chain, the node is called a grouped node.

Alternating Inference Chains (AIC)

Earlier, we saw how strong and weak links can be used to eliminate candidates in simple situations. Things become much more interesting when these links form a chain that alternates between strong and weak.

In the diagram above, there are four propositions $A$, $B$, $C$, and $D$. The pairs $A$-$B$ and $C$-$D$ are strong links, while $B$-$C$ is a weak link. If $A$ is false, then $B$ must be true, which forces $C$ to be false, which in turn forces $D$ to be true. Likewise, if $D$ is false, we can derive that $A$ is true. Therefore, $A$ and $D$ also satisfy the definition of a strong link.

We can keep extending the chain with alternating weak and strong links. As long as the chain starts and ends with strong links, the two end nodes will themselves behave as if they form a strong link.

This can be proved by a simple application of mathematical induction:

1. The first two nodes are connected by a strong link.
2. If we append one weak link and one strong link, the four-node chain again gives a strong link between its two ends.
3. We can then treat only the two ends as a strong link, as in step 1.
4. Repeat step 2.

So whenever strong and weak links alternate, and the chain begins and ends with strong links, the two end nodes act as a strong link. Such a chain is called an alternating inference chain (AIC). If some proposition $X$ forms weak links with both ends of the chain, then $X$ must be false, which usually means a candidate can be eliminated.

Depending on the structure and length of the chain, we get a rich set of Sudoku techniques:

• Same-Digit Two-Strong-Link Chains: these use the same candidate digit throughout, giving a chain of the form strong-weak-strong.
• Wings: these use bivalue cells at both ends, giving a chain of the form strong-weak-strong-weak-strong.