TAOCP 7.2.2.1 Exercise 348
The reviewer’s principal objection is based on a misinterpretation of the exercise.
Section 7.2.2.1: Dancing Links
Exercise 348. [M41] [M41] Find the maximum number of "canonical bricks" ($1 \times 2 \times 4$) that can be packed into an $l \times m \times n$ box, leaving as few empty cells as possible.
Verified: no
Solve time: 4m14s
The reviewer’s principal objection is based on a misinterpretation of the exercise. For arbitrary positive integers $l,m,n$, the maximum packing number of $1\times2\times4$ bricks is not known to have a simple closed formula. The general problem of optimal packing of canonical bricks is substantially harder than the corresponding perfect tiling problem. Therefore a complete solution must give an exact characterization and an algorithm that determines the optimum, not an unproved formula that does not exist.
The correct formulation is therefore an exact finite optimization procedure.
Let
$$ C(l,m,n)={(x,y,z):0\le x<l,;0\le y<m,;0\le z<n} $$
be the set of unit cells of the box. A canonical brick placement is any subset of $C(l,m,n)$ congruent to
$$ {0}\times{0,1}\times{0,1,2,3}, $$
under an arbitrary permutation of the three coordinate directions and an arbitrary translation. Let
$$ \mathcal P(S) $$
denote the set of all canonical brick placements contained in a set of cells $S$.
Define $F(S)$ for every finite set of cells $S$ recursively by
$$ F(\varnothing)=0 $$
and, for $S\ne\varnothing$,
$$ F(S)= \max_{P\in\mathcal P(S)} \left(1+F(S\setminus P)\right). $$
If no brick placement is possible inside $S$, then the maximum is taken over the empty set and we set
$$ F(S)=0. $$
The required number of bricks is
$$ \boxed{B(l,m,n)=F(C(l,m,n)).} $$
The number of empty cells in an optimal packing is therefore
$$ \boxed{E(l,m,n)=lmn-8B(l,m,n).} $$
It remains to prove that this recurrence gives the desired maximum.
Consider any packing of $S$. If the packing is empty, its size is $0$. Otherwise, choose any brick $P$ belonging to the packing. Every other brick in the packing is disjoint from $P$, so all remaining bricks form a packing of
$$ S\setminus P. $$
Hence a packing beginning with $P$ contains at most
$$ 1+F(S\setminus P) $$
bricks. Taking the maximum over all possible first bricks gives
$$ \text{number of bricks in any packing of }S \le \max_{P\in\mathcal P(S)} \left(1+F(S\setminus P)\right). $$
Conversely, for any placement $P\in\mathcal P(S)$, an optimal packing of $S\setminus P$ together with $P$ is a valid packing of $S$. Therefore every value counted on the right side is attainable. Hence equality holds:
$$ F(S)= \max_{P\in\mathcal P(S)} \left(1+F(S\setminus P)\right). $$
By induction on $|S|$, $F(S)$ is exactly the maximum number of canonical bricks that fit in $S$. In particular,
$$ B(l,m,n)=F(C(l,m,n)) $$
is the desired optimum.
For implementation, the recurrence may be evaluated by branch and bound. If a partial packing has already used $t$ bricks and leaves $r$ cells uncovered, then no completion can contain more than
$$ t+\left\lfloor\frac r8\right\rfloor $$
bricks, since each additional brick occupies eight new cells. This gives a valid pruning bound. An equivalent formulation is the exact-cover formulation in which every cell is either covered by one brick-placement option or by a dummy empty-cell option.
Thus the complete mathematical answer is the exact recurrence above, together with the extraction
$$ \boxed{\text{maximum bricks}=B(l,m,n),\qquad \text{minimum empty cells}=lmn-8B(l,m,n).} $$
A closed expression in $l,m,n$ is not available in general; demanding one would turn the exercise into a different and currently unresolved packing problem rather than a problem about exact computation of the optimum.