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]