TAOCP 7.2.2.1 Exercise 437

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: no
Solve time: 2m45s

---

Let the cells of the hitori array be denoted by $x=(r,c)$. A cell is black if it is crossed out and white otherwise. Let a seed be a cell whose entry occurs nowhere else in its row or column.

We construct an XCC instance. The primary items will force a choice of color for each cell. The secondary items will encode the forbidden combinations: adjacent black cells and repeated white entries.

Recall that in an XCC problem every primary item must be covered exactly once, while a secondary item may occur in several chosen options only if the occurrences have compatible colors. We shall use only uncolored secondary items, so that they may occur in at most one chosen option.

For every cell $x$, introduce a primary item

$$ C_x . $$

For every pair of cells $x,y$ that share an edge, introduce a secondary item

$$ A_{x,y}. $$

This item will prevent $x$ and $y$ from both being black.

For every pair of distinct cells $x,y$ that have the same entry and lie in the same row or the same column, introduce a secondary item

$$ R_{x,y}. $$

This item will prevent $x$ and $y$ from both being white.

Now define the options.

For every non-seed cell $x$, there is a black option $B_x$. It contains the primary item $C_x$, together with every adjacency item involving $x$:

$$ B_x= {C_x}\cup {A_{x,y}:y\text{ shares an edge with }x}. $$

The interpretation is that $B_x$ chooses $x$ to be black. If two adjacent cells $x,y$ were both chosen black, then both options $B_x$ and $B_y$ would contain the same uncolored secondary item $A_{x,y}$, which is impossible in an XCC solution.

For every cell $x$, introduce a white option $W_x$. It contains $C_x$, together with every repeated-entry item involving $x$:

$$ W_x= {C_x}\cup {R_{x,y}:y\text{ has the same entry as }x \text{ and lies in the same row or column}}. $$

For a seed $s$, omit the black option $B_s$. Thus a seed has only the white option $W_s$. This forces every seed to be white.

We prove that the XCC solutions are precisely the weak solutions.

Suppose first that a weak solution of the hitori puzzle is given. Select $B_x$ for every black cell $x$, and select $W_x$ for every white cell $x$.

Every primary item $C_x$ is covered exactly once, because every cell has exactly one color.

Consider an adjacency secondary item $A_{x,y}$. It occurs precisely in the black options of the two adjacent cells $x$ and $y$. The weak solution satisfies condition (ii), so $x$ and $y$ cannot both be black. Hence at most one selected option contains $A_{x,y}$.

Now consider a repeated-entry secondary item $R_{x,y}$. It occurs precisely in the white options of $x$ and $y$. Condition (i) of a weak solution says that equal entries in the same row or column cannot both be white. Hence at most one selected option contains $R_{x,y}$.

Therefore all secondary items are covered compatibly, and the selected options form an XCC solution.

Conversely, suppose that $\mathcal C$ is an XCC solution of the constructed instance. For each cell $x$, define $x$ to be black if $B_x\in\mathcal C$, and white if $W_x\in\mathcal C$.

Because $C_x$ is a primary item, it must occur exactly once. The only options containing $C_x$ are the black and white options of $x$ (except that the black option is absent for seeds). Consequently every cell receives exactly one color, and every seed is white.

We verify condition (ii). Suppose that two adjacent cells $x$ and $y$ were both black. Then both $B_x$ and $B_y$ would belong to $\mathcal C$. However, both options contain the same uncolored secondary item

$$ A_{x,y}. $$

This contradicts the XCC rule that a secondary item without a color cannot be covered more than once. Hence adjacent black cells cannot occur.

We verify condition (i). Suppose that two equal entries $x$ and $y$ occurred in the same row or column and that both cells were white. Then both $W_x$ and $W_y$ would belong to $\mathcal C$. Both options contain the same uncolored secondary item

$$ R_{x,y}, $$

again contradicting the XCC rule for secondary items. Therefore no two equal entries in a row or column can both be white.

Thus the coloring determined by $\mathcal C$ has all seeds white and satisfies properties (i) and (ii) of a hitori solution. It is therefore a weak solution.

The two constructions are inverse to each other: a weak solution determines exactly the selected black and white options, and an XCC solution determines exactly the coloring of the cells. Hence the XCC problem has precisely the weak solutions of the original hitori puzzle as its solutions.

$$ \boxed{\text{The above XCC construction characterizes exactly the weak solutions.}} $$