TAOCP 7.2.2.1 Exercise 423
Let the grid of the $m\times n$ masyu puzzle be embedded in the usual way, so that each potential edge $e$ is shared by at most two cells.
Section 7.2.2.1: Dancing Links
Exercise 423. ▶ [M25] For each of the $(m-1)n + n(n-1)$ potential edges $e$ in the solution of an $m \times n$ masyu puzzle, let $x_e$ be the Boolean variable "$e$ is present". The XCC problem constructed in exercise 422 is essentially a set of constraints on those variables.
Explain how to improve that construction dramatically, by exploiting the following special property that is enjoyed by masyu puzzles: Let $N$, $S$, $E$, and $W$ be the edge indicators of a cell that holds a clue. If the clue is black, we have $N = \bar{S}$ and $E = \bar{W}$; if the clue is white, we have $N = S$, $E = W$, and $E = \bar{N}$. (Thus every clue reduces the number of independent variables by at least 2.)
Verified: no
Solve time: 1m07s
Solution
Let the grid of the $m\times n$ masyu puzzle be embedded in the usual way, so that each potential edge $e$ is shared by at most two cells. In the construction of Exercise 422, each edge indicator $x_e$ is treated as an independent Boolean variable, and XCC constraints enforce that (i) each cell satisfies its local masyu condition and (ii) shared edges are consistent across adjacent cells.
The improvement comes from eliminating edge variables that are not independent once the local masyu constraints are imposed. The given identities for a clue cell $C$ express linear dependencies over $\mathbb{F}_2$ among the four edge indicators $N,S,E,W$ of $C$.
If $C$ is black, the relations $N=\bar S$ and $E=\bar W$ imply $S=\bar N$ and $W=\bar E$. Thus the vertical pair $(N,S)$ is determined by one free bit, and the horizontal pair $(E,W)$ is determined by one free bit, with no coupling between the two pairs. Hence a black clue cell contributes exactly two independent Boolean parameters.
If $C$ is white, the relations $N=S$, $E=W$, and $E=\bar N$ imply $S=N$, $W=E$, and $E=\bar N$, so every edge is determined by $N$. Thus a white clue cell contributes exactly one independent Boolean parameter.
This structure allows a direct reduction of the XCC instance by replacing edge variables with cell-local variables. For each cell $C$, introduce variables as follows: if $C$ is white, introduce a single variable $a_C$ representing $N$ (hence also $S=a_C$, $E=\bar a_C$, $W=\bar a_C$); if $C$ is black, introduce two variables $a_C$ and $b_C$ representing $N$ and $E$ respectively, with $S=\bar a_C$ and $W=\bar b_C$.
After this substitution, every original edge variable $x_e$ disappears. Each geometric edge shared by two adjacent cells becomes an equality constraint between the corresponding derived expressions. If an edge $e$ is vertical between cells $C$ and $D$, then $e$ corresponds to the variables representing the horizontal sides of $C$ and $D$, expressed as either $E_C$ or $W_C$ on one side and $W_D$ or $E_D$ on the other, depending on orientation. The constraint $x_e$ being well-defined becomes an equality between two expressions of the form $a_C$, $\bar a_C$, $b_C$, or $\bar b_C$, rather than a constraint on a fresh global variable.
In the XCC formulation, this eliminates all columns corresponding to edges, replacing them by a much smaller set of columns indexed only by cell variables. Each constraint row arising from a geometric consistency requirement now contains at most one occurrence of a variable or its complement from each incident cell, since every edge endpoint is already expressed through a single cell-local parameter.
The reduction is substantial because the original formulation introduces $(m-1)n + m(n-1)$ edge variables, while the improved formulation introduces only $n$ variables for white cells and $2n$ variables for black cells in an $m\times n$ grid, after accounting for one variable per white cell and two per black cell, where $n$ denotes the number of cells. Every remaining constraint is expressed entirely in terms of these cell variables, so the XCC instance size is reduced from being edge-based to being cell-based, with each local masyu constraint already compiled into the variable definitions.
Thus the improvement is obtained by substituting the masyu relations directly into the encoding, eliminating edge variables globally and replacing them with a strictly local system of cell variables whose number is at most two per cell and often one per cell. This completes the construction of a dramatically smaller equivalent XCC problem. ∎