Even 1 × n Edge-Matching and Jigsaw Puzzles are Really Hard

Even 1 × n Edge-Matching and Jigsaw Puzzles are Really Hard

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-har...

Full description

Bibliographic Details
Main Authors: Bosboom, Jeffrey William, Demaine, Erik D, Demaine, Martin L, Hesterberg, Adam Classen, Manurangsi, Pasin, Yodpinyanee, Anak
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:English
Published: Information Processing Society of Japan (Jōhō Shori Gakkai) 2019
Online Access:https://hdl.handle.net/1721.1/122826

Internet

https://hdl.handle.net/1721.1/122826

Similar Items