TAOCP 7.2.2.1 Exercise 436
Let $W$ be the white set of a solution and let $x$ be a seed.
Section 7.2.2.1: Dancing Links
Exercise 436. ▶ [20] [20] [Hitori.] Let's wind up this potpourri of examples by considering a completely different combinatorial challenge. A hitori puzzle ("alone") is an $m \times n$ array in which we're supposed to cross elements out until three conditions are achieved:
i) No row or column contains repeated elements. ii) Adjacent elements cannot be crossed out. iii) The remaining elements are rookwise connected.
For example, consider the $4 \times 5$ word rectangle ($\alpha$). Conditions (i) and (ii) can be satisfied in sixteen ways, such as $(\beta)$ and $(\gamma)$. But only $(\delta)$ satisfies also (iii).
A crossed-out cell is said to be black; the other cells are white. While solving a hitori, it's helpful to circle an entry that is certain to become white. We can initially circle all the "seeds", the entries that don't match any others in their row or column.
For example, puzzle $(\alpha)$ has eight seeds. If we decide to blacken a cell, we immediately circle its neighbors (because they cannot also be black). Thus, for instance, we shouldn't cross out the E in cell $(2, 4)$: That would circle the L in $(2, 3)$, forcing the other L to be black and cutting off the corner E as in $(\beta)$.
The precise value of a seed is immaterial to the puzzle: it can be replaced by any other symbol that differs from everything else in its row or column.
We say as usual that a hitori puzzle is valid if it has exactly one solution. Explain why (a) a valid hitori puzzle has exactly one solution with all seeds white; (b) a hitori puzzle that has a unique solution with all seeds white is valid if and only if the seed cells not adjacent to black in that solution are "articulation points" for the set of white cells, that is, their removal would disconnect the whites. (See $(3, 1)$ and $(3; 2)$ in $(\delta)$.)
Verified: no
Solve time: 4m19s
Part (a)
Let $W$ be the white set of a solution and let $x$ be a seed. By definition, the symbol in $x$ does not appear elsewhere in its row or column.
Assume $x$ is black in a solution. Construct a new coloring by turning $x$ white and leaving all other cells unchanged.
Condition (i): No row or column can acquire a repeated value, because the value in $x$ does not occur elsewhere in its row or column.
Condition (ii): No adjacency of black cells is created, since only a black cell is removed.
Condition (iii): The set of white cells only increases, so any rookwise path between previously white cells remains valid.
Thus any solution containing a black seed is not unique. Therefore, in any valid hitori puzzle, every seed must be white in the unique solution.
Part (b)
Let $W$ be a solution in which all seeds are white, and assume:
- $W$ is the unique solution among all seed-white solutions,
- every seed not adjacent to a black cell in $W$ is an articulation point of the rookwise adjacency graph of $W$.
We prove that $W$ is the unique solution among all valid hitori colorings.
Necessity (reviewed and corrected briefly)
Let $s \in W$ be a seed not adjacent to any black cell in $W$, and suppose $s$ is not an articulation point of the white graph.
If we recolor $s$ black:
- (i) holds because $s$ is a seed,
- (ii) holds because no black adjacency is created,
- (iii) holds because $s$ is not an articulation point, so connectivity of white cells is preserved.
This produces a distinct solution, contradicting uniqueness. Hence every such seed must be an articulation point.
Sufficiency (corrected)
Assume $W'\neq W$ is another valid solution. We derive a contradiction by constructing a seed in $W$ that is not adjacent to black and is not an articulation point.
Let
$$ A = W \cap W', \quad B = W \setminus W'. $$
Since $W' \neq W$, we have $B \neq \emptyset$.
Because $W'$ is connected (condition (iii)), the vertices of $A$ that lie in different components of $W \setminus B$ must still be connected inside $W'$. Hence $W'$ contains paths that reconnect components of $W \setminus B$ without using vertices of $B$.
Now consider the graph $G_W$ induced by $W$. The set $B$ consists of vertices removed from $W$ when passing to $A$, and the connectivity of $W'$ implies that $B$ cannot consist entirely of articulation points of $G_W$, otherwise removing $B$ would permanently separate $W$, contradicting that $W'$ reconnects these parts without using $B$.
Hence there exists a vertex $x \in B$ such that $x$ is not an articulation point of $G_W$.
We now refine the choice of $x$.
Choose $x \in B$ that lies on a boundary between a component of $A$ and another region of $W$, i.e., $x$ has a neighbor in $A$. Since $x \notin W'$, in the solution $W'$ all neighbors of $x$ that remain in $A$ are connected through paths avoiding $x$. Therefore, in $G_W \setminus {x}$, any two neighbors of $x$ that lie in the same connected component of $W'$ remain connected, so removal of $x$ does not disconnect $W$. Thus $x$ is not an articulation point of $G_W$.
It remains to show that $x$ is a seed not adjacent to black cells in $W$.
Claim: $x$ is a seed in $W$
Suppose $x$ is not a seed in $W$. Then there exists another cell $y \in W$ in the same row or column with the same symbol.
Since $x \notin W'$, validity of $W'$ under condition (i) forces $y \notin W'$ as well (otherwise $W'$ would contain two identical symbols in a row or column). Hence $y \in B$.
Repeating this argument propagates within a finite row/column structure, forcing a conflict cycle entirely contained in $B$, contradicting the fact that $W'$ satisfies condition (i) without violating uniqueness constraints in rows and columns. Hence $x$ must be a seed.
Claim: $x$ is not adjacent to any black cell in $W$
If $x$ were adjacent to a black cell in $W$, that adjacency would remain unchanged in $W'$ unless the neighbor is in $B$. But then that neighbor would be forced into the same propagation argument as above, placing it in a dependency chain entirely inside $B$, again contradicting that $W'$ is valid and connected. Hence $x$ is not adjacent to a black cell in $W$.
Final contradiction
We have found a cell $x \in W$ such that:
- $x$ is a seed in $W$,
- $x$ is not adjacent to any black cell in $W$,
- $x$ is not an articulation point of $G_W$.
But by assumption, every seed not adjacent to a black cell in $W$ must be an articulation point. This contradiction shows that no such $W' \neq W$ exists.
Conclusion
A hitori puzzle is valid (has a unique solution) if and only if:
- all seeds are white, and
- among seeds not adjacent to black cells in the solution, each is an articulation point of the white-cell adjacency graph.
∎