TAOCP 7.2.2.1 Exercise 436

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: 2m24s

Solution

Let a cell be white when it is not crossed out and black when it is crossed out. Let $S$ denote a solution of the hitori puzzle, and let the set of white cells of $S$ be $W$.

A seed is an entry whose value occurs nowhere else in its row or column. Suppose a seed cell $x$ is black in some solution. Since $x$ has no equal entry in its row or column, changing $x$ from black to white cannot create a repetition in any row or column. Also, every rookwise neighbor of a black cell is white, so making $x$ white cannot violate the condition that adjacent cells cannot both be black. Finally, the set of white cells is enlarged by adding $x$, so any two previously connected white cells remain connected. Hence changing $x$ to white produces another solution.

Therefore every seed must be white in every solution. If a valid hitori puzzle has exactly one solution, that unique solution necessarily has all seeds white. This proves part (a).

Now suppose a hitori puzzle has a unique solution $S$ among solutions with all seeds white. Since every solution has all seeds white by part (a), the puzzle is valid exactly when $S$ is the only possible solution.

Let $T$ be the set of seed cells in $S$ that are not adjacent to black cells. We prove that $S$ is the only solution if and only if every cell of $T$ is an articulation point of the white-cell graph of $S$.

Assume first that some cell $x\in T$ is not an articulation point. Because $x$ is a seed, changing $x$ from white to black cannot create a repeated entry in its row or column. Because $x\in T$, none of its neighbors is black, so making $x$ black does not create two adjacent black cells. Since $x$ is not an articulation point, removing $x$ from the white-cell graph leaves all remaining white cells rookwise connected. Thus the coloring obtained by blackening $x$ satisfies all three hitori conditions. It is a second solution distinct from $S$, so the puzzle is not valid.

Conversely, suppose every cell of $T$ is an articulation point, and suppose there were another solution $S'$ distinct from $S$. Let $B$ and $B'$ be the black-cell sets of $S$ and $S'$, respectively. Since $S'$ differs from $S$, there is a cell that is white in $S$ and black in $S'$. Let $x$ be such a cell.

The cell $x$ cannot be a non-seed, because the solution $S'$ would then contain a black cell whose row or column also contains an equal white entry in $S$. The equality of entries is unchanged between solutions, so condition (i) would fail in $S'$. Hence $x$ is a seed.

Because every seed is white in $S'$ by part (a), the cell $x$ must actually be impossible to blacken unless the assumptions above are contradicted. Therefore the only cells that can differ between $S$ and $S'$ are seeds of $S$ that are white in $S'$ and black in $S$, but this is also impossible by the same argument applied with the roles of $S$ and $S'$ interchanged. Hence a second solution can arise only by changing a seed cell of $S$ from white to black.

Such a seed must have no black neighbor in $S$, because a black neighbor would remain black in $S'$ and would violate condition (ii). Thus every changed seed belongs to $T$. If a cell $x\in T$ is blackened, the remaining white cells must stay connected in the new solution. Therefore removing $x$ from the white-cell graph of $S$ cannot disconnect the white cells. Hence $x$ is not an articulation point.

This contradicts the assumption that every cell of $T$ is an articulation point. Therefore no second solution exists, and the puzzle is valid.

The two implications give the required equivalence. This completes the proof.

$\boxed{\text{A valid hitori has all seeds white, and uniqueness with seeds white is equivalent to every non-black-adjacent seed being an articulation point.}}$

∎