Even $1\times n$ Edge-Matching and Jigsaw Puzzles are Really Hard

Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine +3

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 i…