TAOCP 7.2.2.1 Exercise 423
The construction in exercise 422 uses one Boolean variable $x_e$ for every potential edge $e$.
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: 1m58s
Solution
The construction in exercise 422 uses one Boolean variable $x_e$ for every potential edge $e$. For an $m \times n$ masyu board this gives $(m-1)n+n(n-1)$ variables, corresponding to the horizontal and vertical edges between neighboring cells. The constraints express the loop conditions at the clues and the degree conditions at the cells.
The improvement comes from eliminating variables that are not independent. Consider a cell containing a clue, and write its four incident edge variables as $N,S,E,W$. The four variables are not free, because the clue imposes equations among them.
For a black clue, the conditions are
$N=\overline S,\qquad E=\overline W.$
Thus $S$ and $W$ determine the other two variables. The four possible edge variables at a black clue can therefore be replaced by only two independent Boolean variables, for example
$S,\qquad W.$
The eliminated variables are recovered whenever they are needed by
$N=\overline S,\qquad E=\overline W.$
For a white clue, the conditions are
$N=S,\qquad E=W,\qquad E=\overline N.$
The last equation gives
$W=\overline S.$
Hence the four incident edges satisfy
$N=S,\qquad S=\overline W,\qquad E=W.$
Only one Boolean variable is independent. We may choose $S$ as the independent variable and reconstruct the remaining three variables by
$N=S,\qquad W=\overline S,\qquad E=\overline S.$
Therefore every clue cell removes at least two independent variables, and a white clue removes three.
Construct a new XCC instance as follows. For each edge that is not eliminated by a clue equation, introduce a Boolean variable. For each eliminated edge, do not introduce a variable. Instead, replace every occurrence of that edge in the constraints of exercise 422 by the corresponding expression in the remaining independent variables. A black clue contributes two independent variables instead of four incident edge variables, and a white clue contributes one instead of four.
The remaining constraints are then written only in terms of the surviving variables. The loop conditions at non-clue cells, which require the appropriate degree conditions, become constraints on the independent variables after the substitutions. The single-loop requirement is unchanged, since the XCC construction of exercise 422 already handles the selection of compatible edges. Every assignment to the reduced variables uniquely determines an assignment to all original edge variables by the reconstruction equations above.
Conversely, every weak solution of the original masyu puzzle satisfies the clue equations, so its values on the surviving variables determine all of its edge variables. Therefore the reduced XCC instance has a solution exactly when the original XCC instance has a solution.
The number of primary Boolean variables is reduced from
$(m-1)n+n(n-1)$
to the number of edges not determined by clue cells. Since every black clue removes two degrees of freedom and every white clue removes three degrees of freedom, the reduction is substantial whenever the puzzle contains many clues. The XCC instance has the same solutions but a much smaller variable set.
This completes the proof.
∎