**Reference**:- Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Pasin Manurangsi, and Anak Yodpinyanee, “Even 1 ×
*n*Edge Matching and Jigsaw Puzzles are Really Hard”,*Journal of Information Processing*, to appear. Special issue of papers from the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games **Abstract**:-
We prove the computational intractability of rotating and placing
*n*square tiles into a 1 ×*n*array such that adjacent tiles are compatible—either equal edge colors, as in edge-matching puzzles, or matching tab/pocket shapes, as in jigsaw puzzles. Beyond basic NP-hardness, we prove that it is NP-hard even to approximately maximize the number of placed tiles (allowing blanks), while satisfying the compatibility constraint between nonblank tiles, within a factor of 0.9999999702. (On the other hand, there is an easy (1/2)-approximation.) This is the first (correct) proof of inapproximability for edge-matching and jigsaw puzzles. Along the way, we prove NP-hardness of distinguishing, for a directed graph on*n*nodes, between having a Hamiltonian path (length*n*− 1) and having at most 0.999999284 (*n*− 1) edges that form a vertex-disjoint union of paths. We use this gap hardness and gap-preserving reductions to establish similar gap hardness for 1 ×*n*jigsaw and edge-matching puzzles. **Length**:- The paper is 11 pages.
**Availability**:- The paper is available in PDF (769k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- Jigsaw1xn_JCDCGGG2016 (Even 1 ×
*n*Edge Matching and Jigsaw Puzzles are Really Hard)

See also other papers by Erik Demaine.

Last updated July 25, 2017 by Erik Demaine.