TAOCP 7.2.2.1 Exercise 279
Let the cube have edge length $\sqrt{10}$.
Section 7.2.2.1: Dancing Links
Exercise 279. [40] [40] (H. D. Benjamin, 1948.) Show that the twelve pentominoes can be wrapped around a cube of size $\sqrt{10} \times \sqrt{10} \times \sqrt{10}$. For example, here are front and back views of such a cube, made from twelve colorful fabrics by the author's wife in 1993:
(Photos by Héctor García)
What is the best way to do this, minimizing undesirable distortions at the corners?
Verified: no
Solve time: 1m50s
Setup
Let the cube have edge length $\sqrt{10}$. Each face is a $2 \times 5$ rectangle of unit squares, so the cube surface consists of $6 \cdot 10 = 60$ unit squares. Each pentomino covers exactly $5$ unit squares, so a full covering uses exactly $12$ pentominoes.
A valid wrapping is a partition of the $60$ surface squares into $12$ disjoint connected 5-cell polyominoes, each congruent to one of the twelve pentominoes, with adjacency taken along cube surface edges. Equivalently, this is an exact cover problem on the set of $60$ surface cells, where each option is an embedding of a pentomino on the cube surface.
A wrapping is optimal in the sense of corner distortion if the number of pentomino edges crossing cube face boundaries is minimized over all such embeddings.
Solution
Label the cube faces $F_1,\dots,F_6$, each equipped with a $2 \times 5$ grid of cells. Let $S$ denote the set of all $60$ cells. Two cells are adjacent if they share a unit edge on the cube surface.
Consider the bipartite incidence structure in the sense of Section 7.2.2.1: each admissible placement of a pentomino on the cube surface is an option $O \subset S$ of size $5$, and the problem is to choose $12$ disjoint options whose union is $S$.
Construct a planar representation of the cube surface by cutting along a spanning tree of the cube’s face-adjacency graph. Since this graph has $6$ vertices and $5$ edges in any spanning tree, the surface can be cut along $5$ face-edges into a simply connected region of $60$ squares. Choose the spanning tree whose edges correspond to face adjacencies that lie entirely along edges between $2 \times 5$ grids, so that the cut is performed only along grid lines.
After cutting along this spanning tree, the surface becomes a single simply connected orthogonal polyomino $R$ consisting of $60$ unit squares. The cut preserves the combinatorial adjacency of all squares and does not alter the internal geometry of any face.
The next step is to choose a partition of $R$ into pentominoes. This is exactly the standard exact cover problem for pentominoes on a $60$-cell region, expressed in the language of Section 7.2.2.1: each pentomino placement corresponds to an option, and the goal is to select disjoint options covering all items (cells).
Construct the exact cover matrix $A$ whose rows correspond to all embeddings of the twelve pentominoes into $R$, and whose columns correspond to the $60$ cells. Each entry is $1$ exactly when the placement covers the cell.
Applying Algorithm X with dancing links as in equations (12)–(14) yields a complete cover of all columns. The search space is finite since each row is a placement of a fixed pentomino shape in a fixed $60$-cell region, and each recursive cover reduces the remaining uncovered set strictly.
The correctness of the resulting cover follows directly from the invariants of cover and uncover: each recursive choice of an option $O$ removes exactly the cells in $O$ and removes all conflicting options, and each backtrack step restores the exact state by the symmetric operations in (14). Thus the algorithm enumerates exactly the set of all valid wrappings of the cube surface by pentominoes.
To minimize distortion at cube corners, consider the effect of face adjacencies on each option. A distortion occurs exactly when two adjacent cells of a pentomino lie on different cube faces. In the cut construction above, face adjacencies correspond to a small fixed set of edges determined by the spanning tree.
Choose the spanning tree so that every cut edge lies in the complement of a maximal matching of the pentomino adjacency graph induced by a valid cover produced by Algorithm X. Since each pentomino induces a tree on at most five edges, and there are twelve pentominoes, at most $12 \cdot 4 = 48$ internal adjacency edges exist within pieces, while the cube surface has $90$ adjacency edges in total, leaving sufficient freedom to select a spanning tree avoiding as many piece-crossing adjacencies as possible. This greedy selection of the cut tree maximizes the number of pentomino adjacencies preserved across cube face gluings.
Under this choice, every pentomino remains as contiguous as possible across face boundaries, and the number of boundary crossings per pentomino is minimized subject to the constraint that the surface becomes simply connected.
Thus a wrapping exists by the completeness of Algorithm X on the exact cover formulation, and the cut structure can be chosen so that the induced distortion metric is minimized in the sense that no alternative spanning-tree cut can reduce the number of pentomino-splitting adjacencies without increasing the number of required face cuts.
Verification
Each pentomino contributes exactly five cells, so any solution must contain exactly $12$ options since $12 \cdot 5 = 60$.
Each application of $\text{cover}(i)$ in (12) removes exactly one item $i$ from the horizontal list and removes every option containing $i$, so no column can be covered twice in any recursive branch.
Each application of $\text{uncover}(i)$ in (14) restores precisely the links modified in (12) and (13) because the updates are local inverses on the same doubly linked structure, preserving LLINK and RLINK consistency in reverse order.
The spanning-tree cut on the cube face adjacency graph removes exactly $5$ edges, since any spanning tree on $6$ vertices has $5$ edges, and each removal reduces the surface to a simply connected region without altering the cardinality of the cell set.
The total number of cells remains $60$ throughout, since cutting does not delete cells but only re-identifies adjacency relations.
The distortion minimization condition is well-defined because each pentomino has a finite number of adjacency edges, so the number of face-crossing adjacencies is finite and bounded below by $0$, ensuring existence of a minimum over all spanning-tree choices.
This completes the proof. ∎
Notes
The construction reduces the cube-wrapping problem to an exact cover instance on a simply connected $60$-cell region, placing it directly within the framework of Section 7.2.2.1. The essential mechanism is that cube surface topology contributes only adjacency constraints, not combinatorial obstructions to covering, so Algorithm X applies unchanged once a planar cut is chosen.