TAOCP 7.2.2.1 Exercise 422
Let the cells of the Masyu puzzle be the vertices of the graph $G$ whose edges join orthogonally adjacent cells.
Section 7.2.2.1: Dancing Links
Exercise 422. [21] Show that the "weak solutions" to any given masyu puzzle are the solutions to an easily constructed XCC problem, by adapting the solution of exercise 412.
Verified: no
Solve time: 2m15s
Solution
Let the cells of the Masyu puzzle be the vertices of the graph $G$ whose edges join orthogonally adjacent cells. A weak solution is a choice of edges of $G$ such that every cell has degree $0$ or $2$, and every clue condition is satisfied. The weakness is that the chosen edges are not required to form one connected loop. Thus several disjoint loops are permitted.
We construct an XCC instance whose solutions are precisely these weak solutions. The construction uses one option for each possible local state of a cell.
For each cell $s$, introduce a primary item $C_s$. The options associated with $s$ will all contain $C_s$, so an exact cover chooses exactly one local state for every cell.
The possible local states of a cell are the subsets of its incident directions that form either no path or a path entering and leaving the cell. Hence the possible nonempty states are the pairs
$$ {N,S},\quad {E,W},\quad {N,E},\quad {E,S},\quad {S,W},\quad {W,N}, $$
with the pairs containing nonexistent directions omitted on the boundary. For each allowed state $T$ of a cell $s$, create one option containing $C_s$.
The clue restrictions are incorporated by deleting forbidden options. For a black circle, only the two states that turn at that cell are retained, and the two neighboring cells in the direction of travel must be straight. Therefore any option for a neighboring cell violating this condition is deleted. For a white circle, only the straight state at the clue cell is retained, and the neighboring cells immediately before and after the clue are restricted so that at least one of them turns. The restrictions are local, so they are enforced by removing the corresponding options before constructing the XCC instance.
It remains to force adjacent cells to agree about whether a path segment exists. For every edge $e={s,t}$ of $G$, introduce a colored item $E_e$. If a local state of $s$ contains the direction from $s$ to $t$, the corresponding option contains $E_e$ with color $1$. If the same local state omits that direction, the option contains no occurrence of $E_e$. Similarly, the options of $t$ that contain the direction from $t$ to $s$ contain $E_e$ with color $1$.
The two endpoints of an edge therefore create a colored item $E_e$ in exactly the cases where they both select the edge. In an XCC solution, a colored item must either be absent or be covered by occurrences having the same color. Consequently, the following two possibilities are allowed:
$$ \text{both endpoints select }e, $$
or
$$ \text{neither endpoint selects }e. $$
The inconsistent cases in which exactly one endpoint selects $e$ are forbidden, because then the colored item $E_e$ would occur only once and would fail the XCC condition. Hence every selected segment is shared by its two incident cells.
We now prove the correspondence.
Given a weak solution of the Masyu puzzle, choose for every cell the option whose local state is exactly the set of segments of the weak solution incident with that cell. Exactly one option containing each primary item $C_s$ is chosen. Every edge selected by the weak solution appears at both endpoints, so each colored item $E_e$ is covered consistently. The clue restrictions hold because the chosen states come from a weak solution. Therefore the selected options form an XCC solution.
Conversely, suppose we have an XCC solution. Exactly one option containing $C_s$ is chosen for every cell $s$, so every cell receives one of its allowed local states. The colored items enforce that adjacent cells agree on every possible segment, so the chosen local states define a well-defined set of edges of $G$. Every cell has degree $0$ or $2$, because only those states were included. The deleted forbidden options guarantee all black-circle and white-circle conditions. Thus the resulting edge set is a weak solution of the original Masyu puzzle.
The two constructions are inverse: a weak solution determines exactly one XCC solution, and every XCC solution determines exactly one weak solution. Therefore the weak solutions of any Masyu puzzle are precisely the solutions of the constructed XCC problem. This completes the proof.
∎