Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Thomas D. Morgan, and Ryuhei Uehara, “Variations on Instant Insanity”, in Space-Efficient Data Structures, Streams, and Algorithms: Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday (Ianfest-66), edited by Andrej Brodnik, Alejandro López-Ortiz, Venkatesh Raman, and Alfredo Viola, Lecture Notes in Computer Science, volume 8066, August 15–16, 2013, pages 33–47.

BibTeX

@InCollection{InstantInsanity_Ianfest2013,
  AUTHOR        = {Erik D. Demaine and Martin L. Demaine and Sarah Eisenstat and Thomas D. Morgan and Ryuhei Uehara},
  TITLE         = {Variations on Instant Insanity},
  BOOKTITLE     = {Space-Efficient Data Structures, Streams, and Algorithms:
                   Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday (Ianfest-66)},
  bookurl       = {http://www.fields.utoronto.ca/programs/scientific/13-14/efficient/},
  VOLUME        = 8066,
  SERIES        = {Lecture Notes in Computer Science},
  seriesurl     = {http://www.springer.de/comp/lncs/},
  EDITOR        = {Andrej Brodnik and Alejandro L\'opez-Ortiz and Venkatesh Raman and Alfredo Viola},
  MONTH         = {August 15--16},
  YEAR          = 2013,
  PAGES         = {33--47},

  length        = {15 pages},
  withstudent   = 1,
  doi           = {https://dx.doi.org/10.1007/978-3-642-40273-9_4},
  dblp          = {https://dblp.org/rec/conf/birthday/DemaineDEMU13},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1007/978-3-642-40273-9_4">SpringerLink</A>.},
}

Abstract:

In one of the first papers about the complexity of puzzles, Robertson and Munro [14] proved that a generalized form of the then-popular Instant Insanity puzzle is NP-complete. Here we study several variations of this puzzle, exploring how the complexity depends on the piece shapes and the allowable orientations of those shapes.

Comments:

This paper is also available from SpringerLink.

Length:

The paper is 15 pages.

Availability:

The paper is available in PDF (1406k).

See information on file formats.

[Google Scholar search]