TAOCP 7.2.2.1 Exercise 439
Let $G=(V,E)$ be a graph, and let $U\subseteq V$ satisfy the three conditions in the definition of a hitori cover.
Section 7.2.2.1: Dancing Links
Exercise 439. [M30] Let $G$ be a graph on the vertices $V$. A hitori cover of $G$ is a set $U \subseteq V$ such that (i) $G[U]$ is connected; (ii) if $v \notin U$ and $u \to v$ then $u \in U$; (iii) if $u \in U$ and if $v \in U$ for all $u \mathop{-!!-} v$, then $G[U \setminus u]$ is not connected.
a) Describe a hitori cover in terms of standard graph theory terminology.
b) Show that the solution of a valid hitori puzzle is a hitori cover of $P_m \square P_n$.
Verified: no
Solve time: 2m14s
Setup
Let $G=(V,E)$ be a graph, and let $U\subseteq V$ satisfy the three conditions in the definition of a hitori cover. The induced graph on $U$ is denoted by $G[U]$. The notation $u\mathop{-!!-}v$ denotes adjacency in $G$, and $u\to v$ denotes the directed incidence relation used in condition (ii).
For a hitori puzzle, regard each cell as a vertex of the grid graph $P_m\square P_n$. Two vertices are adjacent when the corresponding cells share an edge in the rectangular grid. Let $U$ be the set of white cells in a solution. The goal is to prove that $U$ is a hitori cover of this graph.
Part (a) asks for a graph-theoretic description of the three defining conditions. Part (b) asks for the application of this description to a valid hitori puzzle.
Solution
For part (a), condition (i) states that $G[U]$ is connected. Thus the vertices in $U$ form a connected induced subgraph.
Condition (ii) says that every vertex outside $U$ has all of its neighbors in $U$. Equivalently, every vertex in $V\setminus U$ is surrounded entirely by vertices of $U$. In graph-theoretic language, $U$ contains the open neighborhood of every vertex not in $U$:
$$ v\notin U\implies N_G(v)\subseteq U . $$
Therefore $V\setminus U$ is an independent set only when two vertices outside $U$ cannot be adjacent, but the defining requirement is stronger: every boundary vertex outside $U$ has no neighbor outside $U$.
Condition (iii) concerns vertices of $U$ that have no neighbor outside $U$. If $u\in U$ and every neighbor of $u$ also belongs to $U$, then removing $u$ from $G[U]$ destroys connectivity. Such a vertex is an articulation vertex of $G[U]$, except that the condition applies only to vertices whose entire neighborhood lies inside $U$.
Hence a hitori cover is a connected induced subgraph $G[U]$ with the property that every excluded vertex has all neighbors inside the subgraph, and every vertex of the subgraph that is not adjacent to an excluded vertex is an articulation vertex of the subgraph.
This gives the standard graph-theoretic description required in part (a).
For part (b), let the cells of the hitori puzzle be the vertices of
$$ G=P_m\square P_n . $$
Let $U$ be the set of white cells in the unique solution.
The third hitori condition says that the remaining cells are rookwise connected. In the grid graph, rookwise adjacency is exactly graph adjacency in $P_m\square P_n$. Therefore
$$ G[U] $$
is connected, so condition (i) of a hitori cover is satisfied.
Consider a black cell $v\notin U$. The first hitori condition says that no row or column contains repeated white values. Thus every occurrence of a value equal to the value in $v$ must be black. The second hitori condition says that black cells cannot be adjacent. In the XCC formulation from exercise 437, every possible black choice forces all cells containing the same value in the same row or column to be black, while adjacent cells are forced white.
Therefore every neighbor of a black cell must be white. Since the neighbors of $v$ are precisely the cells with $u\to v$ in the grid graph notation, we have
$$ v\notin U\implies N_G(v)\subseteq U . $$
Thus condition (ii) of a hitori cover holds.
It remains to prove condition (iii). Let $u\in U$, and suppose that every neighbor of $u$ is also in $U$. This means that $u$ is not adjacent to any black cell. Assume for contradiction that
$$ G[U\setminus u] $$
is connected.
The cells in $U$ satisfy the first two hitori conditions by assumption. Because $u$ has no adjacent black cells, changing $u$ from white to black does not violate condition (ii). The connectivity assumption on $G[U\setminus u]$ says that the remaining white cells after removing $u$ are still rookwise connected. Hence the set
$$ U\setminus{u} $$
would give another valid hitori solution, because all three hitori conditions would remain satisfied.
This contradicts the assumption that the puzzle is valid, meaning that it has exactly one solution. Therefore
$$ G[U\setminus u] $$
cannot be connected whenever $u\in U$ and every neighbor of $u$ is also in $U$.
Hence condition (iii) holds.
Verification
The argument for condition (i) used only the rookwise connectivity requirement of a hitori solution. The argument for condition (ii) used the fact that black cells cannot touch white cells by the definition of a hitori solution. The argument for condition (iii) used uniqueness: a non-articulating interior white cell would produce a second solution by being blackened.
For part (a), the three conditions have therefore been translated into the following graph properties: $G[U]$ is connected, vertices outside $U$ have all neighbors in $U$, and every vertex of $U$ with no outside neighbor is an articulation vertex of $G[U]$.
For part (b), the white cells of the unique solution satisfy all three properties, so the solution set is a hitori cover of $P_m\square P_n$.
Notes
The description in part (a) shows that hitori solutions are a special class of connected dominating sets. The extra requirement is the articulation condition on vertices that are completely internal to the chosen set. This additional condition distinguishes hitori covers from arbitrary connected dominating sets.
This completes the proof.
∎