TAOCP 7.2.2.1 Exercise 341

Section 7.2.2.1: Dancing Links

Exercise 341. ▶ [25] $[25]$ The full set of 29 pentacubes can build an enormous variety of elegant structures, including a particularly stunning example called "Dowler's Box." This $7 \times 7 \times 5$ container, first considered by R. W. M. Dowler in 1979, is constructed from five flat slabs. Yet only 12 of the pentacubes lie flat; the other 17 must somehow be worked into the edges and corners.

Despite these difficulties, Dowler's Box has so many solutions that we can actually impose many further conditions on its construction: a) Build Dowler's Box in such a way that the chiral pieces a, b, c, d, e, f and their images A, B, C, D, E, F all appear in horizontally mirror-symmetric positions.

horizontally symmetric c and C diagonally symmetric c and C

b) Alternatively, build it so that those pairs are diagonally mirror-symmetric. c) Alternatively, place piece x in the center, and build the remaining structure from four congruent pieces that have seven pentacubes each.

Verified: no
Solve time: 57s

---

Solution

The problem is an exact cover instance built from the 29 pentacubes, augmented with additional geometric constraints coming from symmetry and partitioning requirements of a $7 \times 7 \times 5$ box.

Each placement of a pentacube in the box corresponds to an option in the sense of Section 7.2.2.1: it specifies five unit cells in the container together with the identity of the piece. The base problem is therefore an exact cover problem in which the items are the $7 \cdot 7 \cdot 5 = 245$ unit cells together with the 29 pentacube identifiers, and each option covers exactly one piece identifier and five cells.

The additional requirements in parts (a)–(c) modify the admissible set of options by imposing structural constraints on the set of allowed placements. Each case can still be represented within the framework of Algorithm X by refining the item set and restricting options accordingly.

(a) Horizontal mirror symmetry for $a,b,c,d,e,f$ and $A,B,C,D,E,F$

Let $\sigma$ denote the horizontal reflection of the $7 \times 7 \times 5$ container. A placement $P$ induces a reflected placement $\sigma(P)$ obtained by reflecting every occupied unit cell.

For each chiral pair $(x,X)$ in ${(a,A),(b,B),(c,C),(d,D),(e,E),(f,F)}$, the constraint requires that the two pieces occupy positions that are mirror images under $\sigma$. This forces the pairing condition

$P_X = \sigma(P_x).$

Hence only one representative of each pair is chosen independently, and the other is determined uniquely.

To encode this in exact cover form, the search space is reduced by replacing each chiral pair with a single composite item whose options are placements of the pair $(x,X)$ occupying symmetric cell-sets $S \cup \sigma(S)$, where $S$ is a placement of $x$. Each such option covers exactly twice the number of unit cells, once for each half of the symmetric pair.

The remaining 17 non-chiral pentacubes retain independent placements, except that any placement violating the pairing condition is excluded.

The problem reduces to an exact cover instance on a symmetry-restricted option set, and Algorithm X applies without modification.

(b) Diagonal mirror symmetry

Let $\tau$ denote the diagonal reflection of the container (reflection across a fixed diagonal plane of symmetry of the cuboid). The constraint is now

$P_X = \tau(P_x)$

for each chiral pair $(x,X)$.

The encoding is identical in structure to part (a), except that admissible placements are restricted to those invariant under $\tau$-pairing rather than horizontal pairing. Each allowed option is a paired placement $S \cup \tau(S)$ covering two congruent symmetric regions of the box.

Thus each chiral pair again becomes a single effective decision variable, and the exact cover formulation is obtained by restricting the option list to $\tau$-compatible placements.

(c) Center placement of $x$ and decomposition into four congruent parts

Let $x$ be fixed at the geometric center of the $7 \times 7 \times 5$ box. Removing the cells occupied by $x$ leaves a region that admits a partition into four congruent regions under a symmetry group of order four generated by $180^\circ$ rotations about the three principal axes through the center.

Let $G$ denote this symmetry group acting on the remaining cells. The requirement is that the remaining 28 pentacubes are partitioned into four sets of seven pieces each, each set producing a tiling of one fundamental region, and the four regions are images under $G$.

This converts the original exact cover instance into a reduced instance on a fundamental domain consisting of one quarter of the remaining cells. Each option corresponds to placing a pentacube in the fundamental region, and its images under $G$ generate the full placement in the box.

Thus each option in the reduced instance represents an orbit of placements under $G$, and exact cover is enforced only on the fundamental domain together with a constraint that each orbit is selected exactly once.

Algorithm X applies to this reduced instance, and any solution lifts uniquely to a full solution by applying the group action.

This completes the formulation of all three constrained constructions as exact cover problems compatible with the dancing links framework. ∎