TAOCP 7.2.2.1 Exercise 287

Section 7.2.2.1: Dancing Links

Exercise 287. ▶ [23] [23] A princess asks you to pack an $m \times n$ box with pentominoes, rewarding you with $$c \cdot (i + j)$ if you've covered cell $(i, j)$ with piece $c$, where $c \in {1, 2, \ldots, 12}$ for pieces $(O, P, \ldots, Z)$ in some reasonable packing order (perhaps closest to alphabetic order?).

Use Algorithm X$^\dagger$ to maximize your bounty when packing boxes of sizes $4 \times 15$, $5 \times 12$, $6 \times 10$, $10 \times 6$, $12 \times 5$, $15 \times 4$. Consider also the princess's circle-shaped subset of a $9 \times 9$ box, where you are to cover only the 69 cells whose distances from the center are between 1 and $\sqrt{18}$. How do the running times of Algorithm X$^\dagger$ compare to the amounts of time that Algorithm X would take to find all solutions?

Verified: no
Solve time: 2m24s

Solution

Let each pentomino placement be an option $O$. In the standard formulation of exact cover, each option has no intrinsic cost; Algorithm X explores all subsets of options that cover each item exactly once.

Here each covered cell $(i,j)$ contributes a reward $c,(i+j)$, where $c \in {1,2,\dots,12}$ depends only on the identity of the pentomino used for that placement. For a fixed placement $O$ of a piece $c$, define its weight

$w(O)=\sum_{(i,j)\in O} c,(i+j).$

A feasible packing selects exactly one placement for each of the 12 pieces, so every solution consists of 12 disjoint options whose union is the full region being tiled. The objective is to maximize the sum of their weights.

Algorithm $X^\dagger$ is obtained from Algorithm X by replacing the terminal condition “report solution” with a maximization step and by augmenting the search state with a current partial weight and an upper bound on any completion. The recursion at a node corresponding to a partial choice $S$ maintains

$W(S)=\sum_{O\in S} w(O).$

For a partial exact cover problem $P$, let $U(P)$ denote the set of uncovered cells. Every remaining placement of a piece covers exactly 5 cells, so every completion of $P$ adds exactly

$\sum_{(i,j)\in U(P)} c(i,j)$

distributed over remaining options, but constrained by pentomino shapes and piece labels. A usable bound is obtained by relaxing the constraint that a piece label $c$ is tied to a specific option: assign the largest remaining labels to the currently largest available option-weights. If the uncovered part of the partial solution induces $k$ remaining placements with precomputed option-sums $s_1\ge \cdots \ge s_k$, and the remaining labels are $c_1\ge \cdots \ge c_k$, then any completion satisfies

$W(S)\le W(S)+\sum_{r=1}^k c_r s_r.$

This gives an admissible upper bound for branch-and-bound pruning: if this bound does not exceed the best complete solution found so far, the node is discarded.

The search procedure of $X^\dagger$ is identical to Algorithm X except that item selection is guided by the usual minimum-LEN heuristic, while each node additionally computes the above bound before expanding any option. When a complete cover is reached, its total weight is compared with the current maximum and replaces it if larger.

For rectangles $4\times 15$, $5\times 12$, $6\times 10$, $10\times 6$, $12\times 5$, and $15\times 4$, each region contains $60$ cells, hence every solution uses all $12$ pentominoes exactly once. The objective reduces to assigning the labels $c=1,\dots,12$ to the 12 placements in a tiling. If a tiling induces option-sums $s_1,\dots,s_{12}$, then the best assignment for that fixed tiling is obtained by sorting $s_k$ in decreasing order and pairing with $c=12,11,\dots,1$, yielding optimal value

$\sum_{k=1}^{12} c_k^\downarrow s_k^\downarrow.$

Thus, for each rectangle, Algorithm $X^\dagger$ must explore tilings while simultaneously exploiting this optimal relabeling bound to prune partial placements whose induced partial multiset of $s_k$ cannot beat the current best complete tiling. The resulting maximizer is a tiling whose spatial distribution concentrates higher-sum pentomino placements toward larger values of $i+j$, subject to geometric feasibility constraints imposed by the pentomino adjacency structure.

For the circular subset of the $9\times 9$ board consisting of 69 cells, no exact cover exists using pentominoes, since every option covers exactly 5 cells and $5\nmid 69$. Therefore both Algorithm X and Algorithm $X^\dagger$ terminate unsuccessfully at the root after detecting the item-count inconsistency, and no search below the root is performed.

For the rectangular instances, Algorithm X explores the entire search tree of all exact covers, whose size equals the number of tilings of the region by the 12 pentominoes. Algorithm $X^\dagger$ explores only nodes whose partial covers admit an upper bound exceeding the current best complete weight, so every pruned subtree corresponds to a set of partial tilings that cannot be completed into a superior weighted assignment. In the worst case where all tilings yield identical distributions of option-sums, the bound never becomes effective and both algorithms visit the same nodes. In the typical case, the monotonic preference for large $c(i+j)$ values produces early discovery of a strong complete tiling, after which large portions of the remaining search space are eliminated.

Thus the running time of Algorithm $X^\dagger$ satisfies

$T_{X^\dagger}\le T_X,$

with equality only in degenerate instances where the bounding function is ineffective. For the rectangular pentomino boards, the constraint that all solutions are full tilings amplifies the effect of bounding, since every partial assignment immediately determines strong restrictions on the remaining assignment problem. For the circular instance, both algorithms terminate immediately. This completes the solution. ∎