Paper by Erik D. Demaine
- 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.
In one of the first papers about the complexity of puzzles, Robertson and
Munro  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.
- The paper is 15 pages.
- The paper is available in PDF (1406k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated May 5, 2021 by