Paper by Erik D. Demaine

Reference:
Erik D. Demaine and Martin L. Demaine, “Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity”, Graphs and Combinatorics, volume 23 (Supplement), June 2007, pages 195–208. Special issue on Computational Geometry and Graph Theory: The Akiyama-Chvatal Festschrift.

Abstract:
We show that jigsaw puzzles, edge-matching puzzles, and polyomino packing puzzles are all NP-complete. Furthermore, we show direct equivalences between these three types of puzzles: any puzzle of one type can be converted into an equivalent puzzle of any other type.

Comments:
This paper is also available from SpringerLink.

Updates:
The last paragraph of the introduction asks about polyomino packing puzzles where each piece has just logarithmic area. Michael Brand (2007) has proved such puzzles NP-complete by following a similar approach to this paper, but going directly from 3-partition to polyomino packing.

Availability:
The paper is available in PostScript (2670k), gzipped PostScript (1376k), and PDF (1326k).
See information on file formats.
[Google Scholar search]

Related papers:
Jigsaw_KyotoCGGT2007 (Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity)


See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated August 14, 2014 by Erik Demaine.