  We prove the computational intractability of rotating and placing $n$ square
tiles into a $1 \times 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.9999999851. (On the other hand, there is an easy $1 \over
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 \times n$ jigsaw and
edge-matching puzzles.
