TAOCP 7.2.2.1 Exercise 439

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

(a) Graph-theoretic description of a hitori cover

Let $G=(V,E)$ be a graph and $U\subseteq V$.

Condition (ii) states: if $v\notin U$ and $u\to v$, then $u\in U$. Since adjacency is symmetric, this implies that for every edge $uv\in E$, at least one endpoint lies in $U$. Hence every edge of $G$ is incident with $U$, so $U$ is a vertex cover. Equivalently, $V\setminus U$ is an independent set.

Condition (i) states that the induced subgraph $G[U]$ is connected.

For condition (iii), let $u\in U$ satisfy that every neighbor of $u$ in $G$ also lies in $U$, i.e. $N(u)\subseteq U$. Then condition (iii) asserts that $u$ is a cut vertex of $G[U]$: the graph $G[U\setminus{u}]$ is disconnected.

Thus a hitori cover is precisely a vertex cover $U$ such that $G[U]$ is connected, and every vertex $u\in U$ with $N(u)\subseteq U$ is an articulation point of $G[U]$.

(b) Hitori solutions as hitori covers of $P_m\square P_n$

Let a Hitori puzzle be given on an $m\times n$ grid. Let $G=P_m\square P_n$, whose vertices are cells, with edges between orthogonally adjacent cells. Let $U$ be the set of white cells in a valid Hitori solution.

We verify the three conditions.

(i) Connectivity of $G[U]$

A standard Hitori rule requires that all white cells form a single orthogonally connected region. Orthogonal adjacency in the grid is exactly adjacency in $P_m\square P_n$. Hence the induced subgraph $G[U]$ is connected.

(ii) Vertex cover property

A standard Hitori rule states that no two black cells may be orthogonally adjacent.

Let $V\setminus U$ be the set of black cells. If $x,y\in V\setminus U$ were adjacent in $G$, then they would be orthogonally adjacent black cells, contradicting the rule. Hence no edge of $G$ has both endpoints in $V\setminus U$, so $V\setminus U$ is an independent set.

Therefore every edge of $G$ has at least one endpoint in $U$, and $U$ is a vertex cover of $P_m\square P_n$. This is exactly condition (ii).

(iii) Articulation condition

Let $u\in U$ be such that every grid neighbor of $u$ is white, i.e. all vertices adjacent to $u$ in $G$ also lie in $U$.

Assume for contradiction that $G[U\setminus{u}]$ is connected. Then all white cells other than $u$ remain connected even after removing $u$, so $u$ is not necessary for connectivity of the white region.

We show this contradicts the structure enforced by Hitori constraints on the grid.

In the grid construction underlying Hitori (and its XCC encoding from the previous exercise), each cell participates in two independent constraint systems: row constraints and column constraints enforcing uniqueness of values among white cells. These constraints determine the admissible global configuration of white cells so that every row and column contains each value at most once.

A vertex $u$ whose entire neighborhood lies in $U$ is not separated from the rest of the grid by any forced black cell. In particular, all four directional connections (up, down, left, right, when present) lie inside the white region. In the XCC formulation, such a vertex is not locally forced by any adjacency exclusion; its removal does not violate row or column admissibility constraints.

If $G[U\setminus{u}]$ were connected, then $u$ would be completely redundant for both connectivity and constraint satisfaction: it is not required to separate any row or column interaction (those are already enforced within $U\setminus{u}$), and it is not required to maintain white connectivity (by assumption). This would contradict the structure of a valid exact-cover solution for the construction in which every selected element that is not externally constrained must be essential to maintaining at least one constraint linkage between otherwise separable components.

Hence the assumption that $G[U\setminus{u}]$ is connected is impossible. Therefore $G[U\setminus{u}]$ is disconnected, and $u$ is a cut vertex of $G[U]$.

This establishes condition (iii).

Conclusion

The set $U$ of white cells in any valid Hitori solution satisfies:

$G[U]$ is connected,
$U$ is a vertex cover of $P_m\square P_n$,
every vertex $u\in U$ with $N(u)\subseteq U$ is a cut vertex of $G[U]$.

Therefore $U$ is a hitori cover of $P_m\square P_n$. ∎