TAOCP 7.2.2.1 Exercise 437
Let the hitori instance consist of an $m \times n$ array indexed by cells $x = (r,c)$, each containing a symbol $\sigma(x)$ from a finite alphabet.
Section 7.2.2.1: Dancing Links
Exercise 437. ▶ [27] [27] A weak solution to a hitori puzzle is a solution for which all seeds are white, and for which properties (i) and (ii) of exercise 436 hold. Given a hitori puzzle, define an XCC problem whose solutions are precisely its weak solutions.
Verified: yes
Solve time: 1m22s
Setup
Let the hitori instance consist of an $m \times n$ array indexed by cells $x = (r,c)$, each containing a symbol $\sigma(x)$ from a finite alphabet. Two cells are adjacent if they share an edge in the grid.
A weak solution is a set $B \subseteq [m] \times [n]$ of black cells such that all seeds are not in $B$, and the following hold.
Condition (i) means that for any fixed row $r$ and symbol $a$, among all cells $x = (r,c)$ with $\sigma(x) = a$, at most one cell is not in $B$. The analogous statement holds for columns.
Condition (ii) means that if $x \in B$ and $y \in B$, then $x$ and $y$ are not adjacent.
The task is to construct an exact cover with coloring constraints (XCC) instance whose solutions correspond exactly to such sets $B$.
Solution
For each cell $x$, introduce a primary item $C_x$ representing the requirement that each cell receives exactly one color assignment.
For each row $r$ and symbol $a$, introduce a secondary item $R_{r,a}$. For each column $c$ and symbol $a$, introduce a secondary item $K_{c,a}$.
For each pair of adjacent cells $x,y$, introduce a secondary item $E_{x,y}$ with $x < y$ in some fixed ordering to avoid duplication.
A solution to the XCC instance will consist of selecting exactly one option covering each primary item $C_x$, while respecting secondary item constraints.
For each cell $x$, define two options unless $x$ is a seed.
The white option $W_x$ contains the items $C_x$, $R_{r,\sigma(x)}$, and $K_{c,\sigma(x)}$ where $x = (r,c)$.
The black option $B_x$ contains the item $C_x$, and for every cell $y$ adjacent to $x$, it contains $E_{x,y}$.
If $x$ is a seed, only the white option $W_x$ is included.
Each secondary item is required in the XCC sense to be covered at most once. Each primary item is required to be covered exactly once.
Given a weak solution $B$, construct a set of options as follows. For each cell $x$, choose $B_x$ if $x \in B$, and choose $W_x$ otherwise. Each cell contributes exactly one option covering $C_x$, hence all primary items are covered exactly once.
Condition (ii) implies that no two adjacent cells lie in $B$, hence no secondary item $E_{x,y}$ is contained in two selected black options. Condition (i) implies that for each fixed pair $(r,a)$ there is at most one white cell in row $r$ with symbol $a$, hence each $R_{r,a}$ is covered at most once; similarly for each $K_{c,a}$.
Conversely, given a valid XCC solution, define $B$ as the set of cells $x$ for which $B_x$ is chosen. Since each $C_x$ is covered exactly once, each cell is assigned exactly one of the two options. Since each $E_{x,y}$ is covered at most once, no two adjacent cells belong to $B$. Since each $R_{r,a}$ and $K_{c,a}$ is covered at most once, no row or column contains two distinct white cells with the same symbol.
Seed cells admit only white options, so they cannot belong to $B$.
Thus the correspondence between weak solutions and XCC solutions is bijective.
This completes the construction.
Verification
Each cell $x$ contributes exactly one primary item $C_x$ and exactly one selected option, so the covering condition enforces a well-defined coloring. The adjacency constraint is enforced solely through the secondary items $E_{x,y}$, since any violation would cause a single secondary item to appear in two selected black options. The row and column uniqueness constraints for whites are enforced independently by secondary items $R_{r,a}$ and $K_{c,a}$, since any repetition of a symbol in a row or column among white choices produces duplication of the corresponding secondary item.
All seeds are forced to use the white option because no black option exists for them, so seed constraints hold in every solution.
Notes
The construction separates constraints into primary items enforcing exclusivity of color choice per cell, and secondary items enforcing combinatorial restrictions that need only be satisfied in an at-most-once sense, matching the XCC framework used in dancing links implementations of constrained search problems.