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 July 23, 2024 by
Erik Demaine.