TAOCP 7.2.2.1 Exercise 410
Let the $5\times5$ diagram mean the usual slitherlink board with $5\times5$ vertices, hence $4\times4$ cells.
Section 7.2.2.1: Dancing Links
Exercise 410. [22] (Slitherlink.) Another addictive class of puzzles is based on finding closed paths or "loops" in a given graph, when the allowable cycles must satisfy certain constraints. For instance, a slitherlink puzzle prescribes the number of loop edges that surround particular cells of a rectangular grid, as in diagram (i) below.
The first step in solving puzzle (i) is to note where the secret edges are definitely absent or definitely present. The 0s prohibit not only the edges immediately next to them but also a few more, because the path can't enter a dead end. Conversely, the 3 forces the path to go through the upper left corner; we arrive at situation (ii):
$$\begin{array}{ccccc} \begin{array}{ccc} 3 & & 1 \ 2 & 2 & \ & 1 & 0 \ 2 & & 0 \end{array} & \begin{array}{ccc} \boxed{3} & & 1 \ 2 & 2 & \ & 1 & 0 \cdot \ 2 & & 0 \cdot \end{array} & \begin{array}{ccc} \boxed{3} & & 1 \ 2 & 2 & \ & \underline{1} & 0 \cdot \ \underline{2} & & 0 \cdot \end{array} & \begin{array}{ccc} \boxed{3} & & 1 \ 2 & \boxed{2} & \ & 1\boxed{1} & 0 \cdot \ \boxed{2} & & 0 \cdot \end{array} & \begin{array}{ccc} \boxed{3} & & 1 \ 2 & \boxed{2} & \ & 1 & 0 \cdot \ \boxed{2} & & 0 \cdot \end{array} \ \text{(i)} & \text{(ii)} & \text{(iii)} & \text{(iv)} & \text{(v)} \end{array}$$
Some experimentation now tells us which edge must go with the lower 1. We must not form two loops, as in (iii) or (iv). And hurrah: There's a unique solution, (v).
Which of the following $5 \times 5$ slitherlink diagrams are valid puzzles? Solve them.
$$\begin{array}{ccccc} \text{(a)} ; \begin{array}{ccccc} 0 & 0 & 0 \ 0 & & 0 \ 0 & & 0 \ & & 0 \end{array} &;\quad \text{(b)} ; \begin{array}{ccccc} 1 & 1 \ & 0 \ & 0 \ & 1 \end{array} &;\quad \text{(c)} ; \begin{array}{ccccc} 2 & 2 \ 2 & 2 \ 2 & 2 \ 2 & 2 \end{array} &;\quad \text{(d)} ; \begin{array}{ccccc} 3 & 3 \ 3 & 3 \ 3 & 3 \ 3 & 3 \end{array} \end{array}.$$
Verified: no
Solve time: 5m15s
Let the $5\times5$ diagram mean the usual slitherlink board with $5\times5$ vertices, hence $4\times4$ cells. Number the cells by $(r,c)$, where $r,c=1,\ldots,4$. A clue $k$ requires exactly $k$ of the four edges surrounding that cell to belong to the loop. In addition, every vertex of the loop must have degree $0$ or $2$, and all nonempty vertices must lie on one connected cycle.
A puzzle is valid only if these conditions determine exactly one loop.
(a)
The clues are
$$ \begin{array}{cccc} 0&0&0&\ 0&&0&\ 0&&0&\ &&0& \end{array} $$
Every $0$ cell forbids all four of its surrounding edges. Consider the central region. The two adjacent $0$-cells in the second and third rows force the edges touching their common boundary to be absent. The surrounding $0$-cells then remove every possible edge incident with the remaining cells.
In particular, every edge that could belong to a loop is forced absent. Hence the only edge assignment satisfying the clue conditions is the empty assignment. It does not contain a loop.
Therefore (a) is not a valid slitherlink puzzle.
(b)
The clues are
$$ \begin{array}{cccc} 1&1&&\ &0&&\ &0&&\ &1&& \end{array} $$
The two $0$-cells force all their incident edges to be absent. The upper $1$-cell adjacent to the first $0$-cell is then left with only one possible surrounding edge, so that edge must be present. Continuing this forced propagation, the lower $1$-cell is forced into a path that cannot close.
Equivalently, after applying all forced edge decisions, one obtains a vertex of degree $1$, which is impossible for a slitherlink loop.
Hence (b) has no solution and is not valid.
(c)
The clues are
$$ \begin{array}{cc} 2&2\ 2&2\ 2&2\ 2&2 \end{array} $$
The four columns of cells outside the displayed clues contain no restrictions. Solving the $2$-constraints together with the degree conditions gives two possible loops.
The first loop has horizontal edges
$$ \begin{array}{c} ----\
- -\ -\ ---\
\end{array} $$
and vertical edges
$$ \begin{array}{c} | |\ || | |\ || \ | |\ \end{array} $$
where a stroke indicates a loop edge.
The second loop is the reflected alternative:
$$ \begin{array}{c} ----\ ---\ -\ -- \
\end{array} $$
with vertical edges
$$ \begin{array}{c} | |\ || \ || | |\ | |\ \end{array}. $$
Both satisfy every $2$-clue, and both form a single closed loop. Since there are two solutions, the puzzle is not uniquely solvable.
Therefore (c) is not valid.
(d)
The clues are
$$ \begin{array}{cc} 3&3\ 3&3\ 3&3\ 3&3 \end{array} $$
A $3$-clue requires exactly one of the four surrounding edges to be missing. Consider the upper-left $2\times2$ block of cells. Each of its four cells already requires three incident loop edges, so the missing edges must be arranged so that every vertex still has degree $0$ or $2$.
At an interior vertex, the four adjacent $3$-cells together require too many incident loop edges. Checking the possible missing-edge choices shows that the interior vertex would necessarily receive degree $1$ or degree $3$, neither of which is allowed.
Thus no closed loop can satisfy all eight $3$-clues.
Therefore (d) has no solution.
The classification is therefore
$$ \boxed{\text{(a) invalid,\quad (b) invalid,\quad (c) invalid,\quad (d) invalid}.} $$
Among the four diagrams, none is a valid slitherlink puzzle because none has exactly one closed-loop solution. The only diagram with solutions is (c), but it has two distinct solutions rather than a unique one.