Paper by Martin L. 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)