Strong and Weak Links
In Sudoku, a link describes a logical constraint between possible placements: whether a digit can go in one cell may affect what can go in another.
For example, a row cannot contain the same digit x twice. If we establish that cell C must contain x, we can eliminate candidate x from the other cells in that row. This constraint, where one placement being true makes another false, is an example of a weak link.
Likewise, a row must contain digit x. If x has only two possible positions in the row and one is ruled out, the other must contain x. This constraint, where one placement being false makes another true, is an example of a strong link.
Nodes
The objects connected by links are called nodes. The simplest node means “cell C contains digit x,” written as [C:x]. A node involving just one cell and one candidate is called a simple node, in contrast to the grouped nodes introduced below.
For example, on the board below, [R1C2:3] means “cell R1C2, in row 1 and column 2, contains digit 3.”
A node represents a proposition: a statement that is either true or false. For a simple node [C:x]:
- True means that the digit in
Cisx. Proving this lets us placexinC. - False means that the digit in
Cis notx. Proving this lets us eliminate candidatexfromC.
The presence of candidate x in C only means that this possibility has not yet been ruled out; it does not mean that [C:x] is already true. We can also temporarily assume a node is true or false, then follow its links to deduce the consequences.
Grouped Nodes
Sometimes we need to consider several possible placements together. For example, “at least one of C1, C2, and C3 contains x” is a grouped node, written as [C1:x, C2:x, C3:x]. It means that at least one of [C1:x], [C2:x], and [C3:x] is true: the logical “or” of these simple nodes.
On the board below, [R4C6:8, R5C6:8, R6C6:8] means “at least one of R4C6, R5C6, and R6C6 contains 8.”
The truth value of [C1:x, C2:x, C3:x] is determined as follows:
- The grouped node is true if at least one of
C1,C2, andC3containsx. - The grouped node is false if none of these cells contains
x.
Proving a grouped node true does not necessarily identify the cell in which to place the digit. Proving it false lets us eliminate candidate x from every cell in the group.
Weak Links
A weak link means that two nodes cannot both be true: at least one must be false. If we establish (or assume) that one node is true, the other must be false.
Both nodes in a weak link may be false. A weak link alone does not determine the other node's truth value when one node is false.
We use ┉ (Unicode U+2509) to represent a weak link between two nodes: A┉B. In a diagram, it looks like this:
Weak links are everywhere in Sudoku.
Each digit must appear exactly once in every house, so duplicates are not allowed. This constraint gives us weak links. For example, if two different cells RnCa and RnCb in row n both contain candidate x, then they form the weak link [RnCa:x]┉[RnCb:x]. At most one of these nodes can be true, and both may be false. The same applies in columns and boxes.
Each cell can contain only one digit. Therefore, any two different candidates x and y in an unfilled cell RaCb form the weak link [RaCb:x]┉[RaCb:y]. They cannot both be true; if the cell ultimately contains a different digit, both are false.
On the left board below, [R4C2:8]┉[R4C8:8] represents a weak link between “R4C2 contains 8” and “R4C8 contains 8” in row 4. On the right, [R5C5:1]┉[R5C5:9] represents a weak link between candidates 1 and 9 in cell R5C5.
“Seeing” and “Peers”
When describing a weak link, we often say “node A sees node B,” meaning that they cannot both be true.
For the two examples above, we can say “the 8 in R4C2 sees the 8 in R4C8” and “the 1 in R5C5 sees the 9 in R5C5.”
When the candidate digit is clear from context, we can simply say that two cells “see each other.” This usually means they share a house. For example, “because R4C2 sees R4C8, at most one of these cells can contain 8.”
A cell's peers are the other cells that share a house with it. We can therefore also describe a weak link by saying “cells x and y are peers.” For example, “R4C2 is a peer of R4C8, so if R4C8 contains 8, R4C2 cannot contain 8.”
“Seeing Both” and “Common Peers”
If a node forms a weak link with each of several other nodes, we say it “sees all” of them, or “sees both” when there are two. The common peers of a set of cells are the cells that are peers of every cell in that set: the intersection of their individual peer sets.
For example, on the board below, “R4C6 sees both R4C7 and R5C4, so if either of them contains 2, R4C6 cannot contain 2” describes the two weak links [R4C6:2]┉[R4C7:2] and [R4C6:2]┉[R5C4:2]. We can also say “R4C6 is a common peer of R4C7 and R5C4, so…”
When using an AIC (alternating inference chain) whose end nodes refer to the same digit, the elimination is often described as “remove that candidate from cells that see both end nodes of the chain.”
When a weak link involves a grouped node, “simple node A sees grouped node B” means that A sees every simple node in B. For the same candidate digit, we can also say that the cell containing A is a common peer of all the cells in B.
On the board below, simple node [R6C7:7] sees grouped node [R6C1:7, R6C3:7], because R6C7 shares a row with both cells in the group. Simple node [R8C3:7] sees only [R6C3:7], so it does not see the entire grouped node.
“Grouped node A sees grouped node B” means that every simple node in A sees every simple node in B. For the same candidate digit, this means that every cell in A is a common peer of all the cells in B.
On the board below, grouped node [R1C1:4, R2C1:4] sees grouped node [R3C2:4, R3C3:4], because all the cells in both groups share a box. It does not see grouped node [R2C8:4, R2C9:4], because R1C1 sees neither cell in that group.
Strong Links
A strong link means that two nodes cannot both be false: at least one must be true. If we establish (or assume) that one node is false, the other must be true. A strong link alone, however, does not determine the other node's truth value when one node is true.
We use ━ (Unicode U+2501) to represent a strong link between two nodes: A━B. In a diagram, it looks like this:
For example, [R1C1:1]━[R1C8:1] represents a strong link between “R1C1 contains 1” and “R1C8 contains 1.”
For simple nodes, strong links derived directly from the Sudoku rules mainly come from two structures: bivalue cells and conjugate pairs.
Bivalue Cells
An unfilled cell C with exactly two remaining candidates x and y is called a bivalue cell. Since every cell must contain a digit, C must contain either x or y. At least one of [C:x] and [C:y] must therefore be true, giving the strong link [C:x]━[C:y].
On the board below, every unfilled cell except R3C9 is bivalue. For example, [R1C1:2]━[R1C1:7] is a strong link within a bivalue cell.
Conjugate Pairs
If digit x has not yet been placed in a house and has only two possible positions left, the nodes for those positions form a conjugate pair. For example, suppose x can go only in RnCa or RnCb in row n. Since the row must contain an x, at least one of [RnCa:x] and [RnCb:x] must be true, giving the strong link [RnCa:x]━[RnCb:x]. The same applies in columns and boxes.
In row 1 of the board below, candidate 1 appears only in R1C1 and R1C8, so [R1C1:1]━[R1C8:1] is a strong link between a conjugate pair.
Strong Links between Grouped Nodes
If all possible positions for a digit in a house are divided into two groups, the corresponding grouped nodes form a strong link: if none of the cells in one group contains that digit, a cell in the other group must contain it.
On the left board, candidate 7 appears in box 1 only in R1C2, R2C2, R3C1, and R3C3, giving [R1C2:7, R2C2:7]━[R3C1:7, R3C3:7]. On the right, candidate 6 appears in row 2 only in R2C2, R2C3, R2C7, R2C8, and R2C9, giving [R2C2:6, R2C3:6]━[R2C7:6, R2C8:6, R2C9:6]. These structures occur in the intersecting row and column of an Empty Rectangle and the pivot of Chute Remote Pairs, respectively.
Strong Links Derived through Logic
Strong links can also be established through logical reasoning:
An AIC proves that at least one end node is true. Its end nodes therefore have a logical strong link.
In coloring techniques, the two colors within a group represent complementary truth values. Any node of one color therefore forms a strong link with any node of the other color.
Strong Links That Can Be Used as Weak Links
Bivalue cells, conjugate pairs, and strong links between grouped nodes within a house all satisfy both “at least one true” and “at most one true”: exactly one node is true. These nodes have both a strong link and a weak link. In other words, a strong link between nodes that see each other is also a weak link. Such a link can be used wherever a chain requires a weak link.
The logical definition of a strong link, however, guarantees only that at least one node is true. A strong link derived through reasoning does not necessarily also satisfy the weak-link condition, so it cannot always be used as a weak link.
In practice, whenever a weak link is needed, simply look for nodes that see each other. There is no need to check whether they also form a strong link.
Eliminations with Strong and Weak Links
One important use of strong and weak links is to eliminate candidates and simplify the board.
If nodes A and B form a strong link, and node X sees both of them (forms a weak link with each), then X must be false.
As shown above, the strong link guarantees that at least one of A and B is true. Either one being true makes X false through its weak link. We can therefore establish that X is false without knowing which node is true.
If X is a simple node [C:x], we can eliminate candidate x from cell C.
Sudoku Techniques Based on Links
- AICs: techniques that reason through a chain of alternating strong and weak links.
- Coloring: techniques that assign colors to nodes based on strong links, then use these colors and weak links to draw conclusions.