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.

BibTeX

@Article{Jigsaw_GC,
  AUTHOR        = {Erik D. Demaine and Martin L. Demaine},
  TITLE         = {Jigsaw Puzzles, Edge Matching, and Polyomino Packing:
                   Connections and Complexity},
  JOURNAL       = {Graphs and Combinatorics},
  VOLUME        = {23 (Supplement)},
  MONTH         = {June},
  YEAR          = 2007,
  PAGES         = {195--208},
  EDITOR        = {D. Avis and A. Bondy and M. Kano and N. Katoh},
  NOTE          = {Special issue on Computational Geometry and Graph Theory:
                   The Akiyama-Chvatal Festschrift.},

  doi           = {https://dx.doi.org/10.1007/s00373-007-0713-4},
  dblp          = {https://dblp.org/rec/journals/gc/DemaineD07},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/s00373-007-0713-4">SpringerLink</A>.},
  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.
  },
  papers        = {Jigsaw_KyotoCGGT2007},
  replaces      = {Jigsaw_KyotoCGGT2007},
}

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)