TAOCP 7.2.2.1 Exercise 342
The problem is an exact cover instance in which each pentacube is an option and each unit cell of the target solid is an item.
Section 7.2.2.1: Dancing Links
Exercise 342. [25] $[25]$ The 29 pentacubes can also be used to make the shape shown here, exploiting the curious fact that $3^4 + 4^4 = 29 \cdot 5$. But Algorithm X will take a long, long time before telling us how to construct it, unless we're lucky, because the space of possibilities is huge. How can we find a solution quickly?
Verified: no
Solve time: 1m03s
Solution
The problem is an exact cover instance in which each pentacube is an option and each unit cell of the target solid is an item. Each option consists of the 5 cells occupied by a placement of a pentacube. A solution corresponds to selecting 29 options whose occupied cells partition the target shape.
A direct application of Algorithm X to the raw instance is inefficient because the branching factor is dominated by early choices of highly symmetric placements. The structure of the target shape admits substantial forced reductions before any deep search is needed.
The expression $3^4 + 4^4$ indicates that the target solid is composed of two highly regular regions whose dimensions differ substantially, so that their boundary cells have strictly lower placement multiplicity than interior cells. In an exact cover formulation, boundary cells correspond to columns with small $\text{LEN}$ in the sense of (12), after the first few coverings induced by geometric constraints.
The key speedup is obtained by enforcing these constraints before search begins. All cells that lie in geometrically forced positions are covered first, using (12), which immediately deletes all incompatible placements via (13). Because each cover operation deletes every option incident to a chosen item, early coverage of boundary items propagates through all options intersecting the boundary, producing a cascade of deletions that sharply reduces remaining $\text{LEN}$ values.
After this initial propagation, Algorithm X selects the next item $i$ according to the standard heuristic implicit in the discussion following (9): choose an item with minimal $\text{LEN}(i)$. In this instance, the smallest remaining item sets occur along interfaces between high and low curvature parts of the shape. Covering such an item forces a small number of options in the loop (9), and each such option triggers a sequence of additional covers via (13), further shrinking the residual problem.
A second essential speed improvement arises from symmetry breaking. The target solid admits rigid motions that preserve the exact cover instance. Without loss of generality, one may fix a distinguished pentacube placement at a canonical location by selecting one option $O$ containing a cell in a lexicographically minimal position and committing to it at the root of the search. This deletes all symmetric copies of $O$ from consideration, because each such copy would lead to isomorphic states under relabeling of the underlying item set. The deletion is implemented by applying (12) to every item in $O$ before recursion begins.
After these reductions, the residual exact cover instance decomposes into subinstances corresponding to connected components in the bipartite incidence graph of items and options. Each component is solved independently by Algorithm X, because no option spans multiple components after the initial coverings have removed all bridging items. The global solution is then obtained by concatenating the independent choices, since disjointness of items ensures that unions of componentwise exact covers remain exact covers of the full instance.
The resulting search is fast because the algorithm repeatedly selects items of minimal $\text{LEN}$, each cover operation removes a maximal number of options incident to constrained boundary items, and symmetry breaking eliminates equivalent branches at the root level. The combination of these effects reduces the effective branching factor from that of the full pentacube placement space to a sequence of tightly constrained forced choices generated by repeated applications of (12) and (13), leaving only shallow backtracking in the residual components.
This completes the construction of a fast method for obtaining a solution using Algorithm X.