Paper by Martin L. 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.

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.

Length:
The paper is 15 pages.

Availability:
The paper is available in PDF (1406k).
See information on file formats.
[Google Scholar search]


See also other papers by Martin Demaine.
These pages are generated automagically from a BibTeX file.
Last updated by Martin Demaine.