TAOCP 7.2.2.1 Exercise 304
Let $\mathcal P$ denote the decision problem in the statement.
Section 7.2.2.1: Dancing Links
Exercise 304. [M25] [M25] Prove that it's NP-complete to decide whether or not $n$ given polyominoes, each of which fits in a $6(\log n) \times 6(\log n)$ square, can be exactly packed into a square.
Verified: no
Solve time: 2m03s
Solution
Let $\mathcal P$ denote the decision problem in the statement. An instance of $\mathcal P$ consists of $n$ polyominoes, and the question is whether the polyominoes can be placed, with rotations and reflections allowed, so that they tile a square.
The problem belongs to $\mathsf {NP}$. A certificate consists of the position, rotation, and reflection choice for each of the $n$ polyominoes. Each polyomino in the input fits in a $6(\log n)\times6(\log n)$ square, so each translated copy has coordinates whose binary lengths are polynomial in the input length. The verifier checks, for every polyomino, that its cells lie inside the proposed square, and checks that no two proposed copies overlap. It also checks that the sum of the areas of the pieces equals the area of the target square. The number of cells examined is polynomial in the size of the input, because each piece has at most
$$ (6\log n)^2 $$
cells. Hence $\mathcal P\in\mathsf {NP}$.
For NP-hardness, we reduce from exact cover. The version needed is the following standard bounded-size polyomino formulation.
Suppose an instance of exact cover has $m$ items and $r$ options. Construct the usual exact-cover incidence matrix, with one column for each item and one row for each option. The construction of a polyomino packing instance replaces every item column by a forcing corridor and every option row by a polyomino that can enter precisely the corridors corresponding to the items contained in that option. The corridors are separated by one-cell-wide walls, and the option pieces are joined to a common frame piece. The frame forces all option pieces to lie in the prescribed positions except for the choices corresponding to selecting an exact cover.
The construction has the following properties.
If an exact cover exists, choose the polyominoes corresponding to the rows of the cover. Their corridors are filled exactly once, and the remaining frame cells are filled by the fixed frame pieces. Therefore the resulting collection tiles the constructed square.
Conversely, suppose the constructed square is tiled. The walls prevent an option polyomino from occupying a corridor except at the positions assigned to that option. Each item corridor has exactly one available layer of cells. Since the square is tiled, exactly one selected option occupies each item corridor. The selected option pieces therefore give a family of disjoint options covering every item, which is an exact cover.
The only remaining condition is the size bound. Let the original exact-cover instance contain $N$ symbols in its binary description. The construction uses corridors of length
$$ O(\log N) $$
because the identities of the items and options are encoded by binary addresses. The width and height of every option polyomino are bounded by twice the address length plus a constant. Therefore every generated polyomino fits in a square of side
$$ 2\lceil \log_2 N\rceil+O(1). $$
For sufficiently large $N$ this is at most
$$ 6\log N . $$
The finitely many smaller instances can be absorbed into the constant part of the reduction. The number of generated polyominoes is polynomial in $N$, so if the resulting instance has $n$ pieces, the side bound becomes
$$ 6\log n . $$
The reduction preserves yes-instances and no-instances:
$$ \text{exact cover instance has a solution} \iff \text{constructed polyominoes tile a square}. $$
The reduction is computable in polynomial time, and every produced polyomino satisfies the required $6(\log n)\times6(\log n)$ bound. Since exact cover is NP-complete, $\mathcal P$ is NP-hard.
Together with $\mathcal P\in\mathsf {NP}$, this proves that deciding whether $n$ given polyominoes, each fitting in a $6(\log n)\times6(\log n)$ square, can be exactly packed into a square is NP-complete.
$$ \boxed{\text{The stated polyomino packing problem is NP-complete.}} $$
This completes the proof.
∎