TAOCP 7.2.2.1 Exercise 34
\textbf{Construction.
Section 7.2.2.1: Dancing Links
Exercise 34. [M25] $[M25]$ Given an exact cover problem $A$ as in exercise 33, construct an exact cover problem $A'$ such that (i) $A'$ has at most three 1s in every column; (ii) $A'$ and $A$ have exactly the same number of solutions.
Verified: no
Solve time: 6m27s
$$ \textbf{Construction.} $$
Let $A$ be the given exact cover instance. We regard $A$ as a $0$-$1$ matrix. For each column $c$ of $A$, let
$$ r_1,r_2,\ldots ,r_k $$
be the rows having a $1$ in column $c$. If $k\leq 3$, we leave this column unchanged. We only describe the replacement when $k>3$.
The replacement is done independently for each such column. The idea is to replace the single column $c$, which forces exactly one of the rows $r_i$ to be chosen, by a bounded-degree selection gadget having the same property.
Choose a binary tree $T$ with $k$ leaves. Label the leaves
$$ \ell_1,\ell_2,\ldots,\ell_k $$
and associate leaf $\ell_i$ with the occurrence of $c$ in row $r_i$.
For every node $v$ of $T$, introduce a new column $C_v$. The old occurrence of $c$ in row $r_i$ is replaced by a $1$ in column $C_{\ell_i}$.
For every internal node $v$, with children $u$ and $w$, introduce the two auxiliary rows
$$ R_{v,u}={C_v,C_u}, $$
and
$$ R_{v,w}={C_v,C_w}. $$
Finally introduce one additional column $C_\rho$, where $\rho$ is the root, and replace the original column $c$ by the requirement that $C_\rho$ be covered. Equivalently, $C_\rho$ is made a compulsory column of the new exact cover instance.
The only remaining point is to remove the excessive occurrence of the root column. We do this by adding one dummy row
$$ D={C_\rho}. $$
The dummy row is not allowed to be chosen simultaneously with any original row occurrence; this is enforced by replacing every leaf column $C_{\ell_i}$ by the column pair construction below.
For each leaf column $C_{\ell_i}$, introduce a new column $L_i$, replace the occurrence of $C_{\ell_i}$ in the original row $r_i$ by $L_i$, and add the auxiliary row
$$ {C_{\ell_i},L_i}. $$
Now every leaf choice propagates upward through the tree. The resulting gadget has the following invariant.
$$ \boxed{\text{Exactly one leaf column is covered by an original row.}} $$
To see this, consider the tree from the root downward. Every internal column $C_v$ must be covered exactly once. It can only be covered by one of the two rows
$$ {C_v,C_u},\qquad {C_v,C_w}. $$
Hence choosing a row at $v$ covers exactly one child column and leaves the other child column to be handled inside the corresponding subtree. Therefore, at each branching point, exactly one child subtree remains active. Continuing recursively, precisely one root-to-leaf path is selected. At the leaf, the only way to terminate the path is to use the corresponding original row $r_i$. All other leaves are covered by the auxiliary rows attached to their parents. Hence the gadget has exactly one possible original occurrence selected.
Conversely, if a particular occurrence $r_i$ of the original column $c$ is selected, the unique path from the root to $\ell_i$ is forced. At each internal node on this path, choose the row leading to the next node. All remaining child subtrees are then uniquely completed by the complementary auxiliary rows. Thus every original choice of one occurrence of $c$ gives exactly one completion of the gadget.
Therefore the gadget establishes a bijection:
$$ {\text{ways to cover the old column }c} \longleftrightarrow {\text{ways to cover the replacement gadget}}. $$
Applying the replacement independently to every column of $A$ having more than three occurrences gives the required instance $A'$.
It remains to check the column degrees. A leaf column occurs in its original row and in at most two auxiliary rows. An internal column occurs only in the two rows belonging to its children and in the row belonging to its parent, so it has at most three $1$'s. The root column has only its two child rows (and the harmless dummy occurrence before simplification). Thus every column of $A'$ contains at most three $1$'s.
The correspondence above is independent for each replaced column, so choosing rows in $A$ and choosing the corresponding rows in $A'$ are in one-to-one correspondence. Consequently,
$$ #\operatorname{Sol}(A')=#\operatorname{Sol}(A). $$
Hence $A'$ satisfies both required conditions:
$$ \boxed{\text{every column of }A'\text{ has at most three }1\text{'s}} $$
and
$$ \boxed{#\operatorname{Sol}(A')=#\operatorname{Sol}(A)} . $$