Paper by Erik D. Demaine

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.

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.

This paper is also available from SpringerLink.

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.

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 September 26, 2015 by Erik Demaine.