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 [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.

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 BibTeX file.
Last updated March 9, 2018 by Erik Demaine.