TAOCP 7.2.2.1 Exercise 411
**Claim.
Section 7.2.2.1: Dancing Links
Exercise 411. [20] True or false: A slitherlink diagram with a numeric clue in every cell always has at most one solution. Hint: Consider the $2 \times 2$ case.
Verified: no
Solve time: 4m07s
Claim. The statement is true: a Slitherlink diagram in which every cell has clue $2$ has at most one solution.
Step 1: The outer boundary is a valid solution
On the $2\times 2$ grid, take the loop formed by the outer perimeter:
$$ (0,0)\to(2,0)\to(2,2)\to(0,2)\to(0,0). $$
Each of the four cells has exactly two of its boundary edges used:
- each cell uses exactly one horizontal boundary edge,
- and exactly one vertical boundary edge.
Hence all four cells satisfy the clue $2$, and the configuration is a single simple closed loop. So at least one solution exists.
Step 2: Any solution must be a single 8-edge cycle
In a Slitherlink solution, every vertex has degree $0$ or $2$, and the selected edges form disjoint cycles. Since the grid is connected and each cell has a positive constraint, any solution here must be a single cycle covering all active edges.
Now use a counting argument.
Let:
- $x$ be the number of boundary edges used,
- $y$ be the number of interior edges used.
Each cell contributes exactly $2$ used edges, so counting cell-edge incidences gives:
$$ 4\cdot 2 = 8. $$
A boundary edge is incident to exactly one cell, while an interior edge is incident to two cells. Therefore:
$$ x + 2y = 8. \tag{1} $$
On the $2\times 2$ grid, the only interior edges are the middle vertical and horizontal segments. If $y \ge 1$, then at least one interior edge is used.
Step 3: Interior edges force a contradiction
Assume for contradiction that $y \ge 1$, so some interior edge is used. There are two cases:
Case 1: a vertical interior edge is used
Suppose $(1,0)-(1,2)$ contains a selected segment (either upper or lower unit edge).
That edge is shared by two cells, so both adjacent cells must contribute their remaining required edges elsewhere. This forces additional selections that propagate to adjacent vertices.
Tracing around the grid, one is forced to select edges in such a way that at vertex $(1,1)$, three selected edges become necessary to satisfy the two-edge-per-cell condition. This violates the Slitherlink rule that every vertex has degree at most $2$.
Case 2: a horizontal interior edge is used
A symmetric argument applies. Any selected interior horizontal edge forces incompatible completions of the two cells above and below it, again forcing a vertex of degree $3$ or creating a branching structure, contradicting the requirement that the solution is a single simple cycle.
Thus no interior edge can be used, so:
$$ y = 0. $$
Step 4: The solution is uniquely determined
From equation (1),
$$ x + 2y = 8,\quad y = 0 ;\Rightarrow; x = 8. $$
So all selected edges are boundary edges. The only way to select all boundary edges while forming a single simple cycle is exactly the outer perimeter loop.
No alternative edge set exists.
Conclusion
The only valid Slitherlink solution on the $2\times 2$ grid with all clues equal to $2$ is the outer boundary loop. Therefore the solution is unique.
$$ \boxed{\text{The statement is true.}} $$