Abstract
This paper establishes the computational complexity of $1 \times n$ edge-matching and jigsaw puzzles, proving they are NP-hard and inapproximable. By employing a gap-preserving reduction from Max-3SAT(29) through a novel intermediate graph problem, the authors demonstrate that even the simplest linear arrangements of square tiles are computationally intractable.
Introduction
Edge-matching puzzles involve arranging square tiles such that the colors or patterns on adjacent edges match. Jigsaw puzzles are a "signed" variant where edges have interlocking tabs and pockets. While solving these puzzles on a general $m \times n$ grid has long been known to be NP-hard, the complexity of the $1 \times n$ strip remained a subject of debate due to previous erroneous proofs. This research definitively proves that the $1 \times n$ case is not only NP-hard but also hard to approximate, meaning no efficient algorithm can consistently find a solution that is even "nearly" perfect.
Methodology: Gap-Preserving Reductions
The authors utilize a gap-preserving reduction to establish hardness. The proof sequence begins with Max-3SAT(29), a standard hard optimization problem. This is reduced to a new problem: Maximum Vertex-Disjoint Path Cover on directed graphs with a maximum degree of 2.
The core of the proof lies in translating this graph problem into a $1 \times n$ puzzle. The researchers designed "vertex tiles" and "edge tiles" such that a valid tiling of the strip corresponds to a Hamiltonian path in the graph. A critical innovation is the "bridge tile," which allows "garbage" edge tiles (those not part of the optimal path) to be sequestered at the end of the strip. This ensures the reduction holds even when a perfect solution does not exist, creating a "gap" that makes approximation difficult.
Key Insights and Results
The study provides the first rigorous proof of NP-hardness for $1 \times n$ signed edge-matching puzzles. Furthermore, it establishes an inapproximability factor of 0.9999999851. This result implies that it is NP-hard to distinguish between a puzzle that can be perfectly solved and one where at most a tiny fraction of the edges can be matched.
Beyond puzzles, these findings have implications for geometry and packing. The results imply that packing polyominoes into a rectangle is NP-hard even when the shapes are relatively small (area $\Theta(\log n)$). The paper also clarifies the relationship between signed (jigsaw) and unsigned (edge-matching) puzzles, showing that hardness in the former implies hardness in the latter.
Discussion and Future Directions
While the proof establishes a definitive "no-go" zone for approximation, the current gap is extremely small. The authors suggest that the actual threshold for hardness is likely much lower, potentially between the known $2/3$-approximation algorithm and the $0.999...$ bound established here. Future work may focus on tightening this bound or adapting these linear reduction techniques to more complex $n \times n$ grid constraints.
Summary updated