TAOCP 7.2.2.1 Exercise 3
The system is interpreted exactly as written: x_2 + x_3 = x_3 + x_5 + x_6 = x_2 + x_5 = x_3 + x_4 = x_1 + x_4 = x_2 + x_3 + x_4 + x_6 = x_1 + x_6 = 1, with each $x_k \in {0,1}$ for $1 \le k \le 6$.
Section 7.2.2.1: Dancing Links
Exercise 3. [20] [20] An $m \times n$ matrix that's supposed to be exactly covered can be regarded as a set of $n$ simultaneous equations in $m$ unknowns. For example, (5) is equivalent to
$$x_2 + x_3 = x_3 + x_5 + x_6 = x_2 + x_5 = x_3 + x_4 = x_1 + x_4 = x_2 + x_3 + x_4 + x_6 = x_1 + x_6 = 1,$$
where each $x_k = [\text{choose row } k]$ is either 0 or 1.
a) What is the number of solutions to those seven equations?
b) Why is this approach to exact cover problems almost never useful in practice?
Verified: no
Solve time: 1m16s
Solution
The system is interpreted exactly as written:
$$ x_2 + x_3 = x_3 + x_5 + x_6 = x_2 + x_5 = x_3 + x_4 = x_1 + x_4 = x_2 + x_3 + x_4 + x_6 = x_1 + x_6 = 1, $$
with each $x_k \in {0,1}$ for $1 \le k \le 6$. Hence every displayed expression equals $1$, giving the system
$$ \begin{aligned} (1);& x_2 + x_3 = 1,\ (2);& x_3 + x_5 + x_6 = 1,\ (3);& x_2 + x_5 = 1,\ (4);& x_3 + x_4 = 1,\ (5);& x_1 + x_4 = 1,\ (6);& x_2 + x_3 + x_4 + x_6 = 1,\ (7);& x_1 + x_6 = 1. \end{aligned} $$
From (4) and (5),
$$ x_4 = 1 - x_3, \qquad x_1 = 1 - x_4 = x_3. $$
From (7),
$$ x_1 + x_6 = 1 ;\Rightarrow; x_3 + x_6 = 1 ;\Rightarrow; x_6 = 1 - x_3. $$
From (1),
$$ x_2 = 1 - x_3. $$
From (3),
$$ x_2 + x_5 = 1 ;\Rightarrow; (1 - x_3) + x_5 = 1 ;\Rightarrow; x_5 = x_3. $$
Thus all variables are determined by $x_3$:
$$ x_1 = x_3,\quad x_5 = x_3,\quad x_2 = x_4 = x_6 = 1 - x_3. $$
Substitution into (2) yields
$$ x_3 + x_5 + x_6 = x_3 + x_3 + (1 - x_3) = x_3 + 1. $$
Since this must equal $1$,
$$ x_3 + 1 = 1 ;\Rightarrow; x_3 = 0. $$
Hence
$$ x_1 = x_3 = 0,\quad x_5 = 0,\quad x_2 = x_4 = x_6 = 1. $$
Substitution into (6) gives
$$ x_2 + x_3 + x_4 + x_6 = 1 + 0 + 1 + 1 = 3 \ne 1, $$
so no assignment satisfies all seven equations simultaneously.
Therefore the system has no solutions.
$$ \boxed{0} $$
For part (b), rewriting exact cover as simultaneous linear equations in 0–1 variables destroys the structural sparsity that makes backtracking effective. The constraints couple many variables simultaneously, so local choices propagate globally through dense arithmetic relations rather than through eliminations of options and items. Any algebraic approach forces reasoning over exponentially many integer assignments consistent with intermediate partial sums, and even standard linear-algebra reductions over $\mathbb{Z}$ or finite fields do not respect the integrality restriction $x_k \in {0,1}$. The resulting feasibility problem is equivalent to 0–1 integer programming, which admits no efficient general elimination procedure analogous to Gaussian elimination, and thus loses the pruning mechanism that exact cover algorithms exploit through item and option removal. ∎