Variations on Instant Insanity
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...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2014
|
| Online Access: | http://hdl.handle.net/1721.1/86210 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3182-1675 |
| _version_ | 1811090379764662272 |
|---|---|
| author | Demaine, Erik D. Demaine, Martin L. Morgan, Thomas D. Uehara, Ryuhei Eisenstat, Sarah Charmian |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D. Demaine, Martin L. Morgan, Thomas D. Uehara, Ryuhei Eisenstat, Sarah Charmian |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T14:44:41Z |
| format | Article |
| id | mit-1721.1/86210 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:44:41Z |
| publishDate | 2014 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/862102022-10-01T22:13:34Z Variations on Instant Insanity Demaine, Erik D. Demaine, Martin L. Morgan, Thomas D. Uehara, Ryuhei Eisenstat, Sarah Charmian Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Demaine, Martin L. Eisenstat, Sarah Charmian 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. 2014-04-17T19:29:58Z 2014-04-17T19:29:58Z 2013 Article http://purl.org/eprint/type/JournalArticle 978-3-642-40272-2 978-3-642-40273-9 0302-9743 1611-3349 http://hdl.handle.net/1721.1/86210 Demaine, Erik D., Martin L. Demaine, Sarah Eisenstat, Thomas D. Morgan, and Ryuhei Uehara. “Variations on Instant Insanity.” Lecture Notes in Computer Science (2013): 33–47. https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3182-1675 en_US http://dx.doi.org/10.1007/978-3-642-40273-9_4 Space-Efficient Data Structures, Streams, and Algorithms Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag MIT web domain |
| spellingShingle | Demaine, Erik D. Demaine, Martin L. Morgan, Thomas D. Uehara, Ryuhei Eisenstat, Sarah Charmian Variations on Instant Insanity |
| title | Variations on Instant Insanity |
| title_full | Variations on Instant Insanity |
| title_fullStr | Variations on Instant Insanity |
| title_full_unstemmed | Variations on Instant Insanity |
| title_short | Variations on Instant Insanity |
| title_sort | variations on instant insanity |
| url | http://hdl.handle.net/1721.1/86210 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3182-1675 |
| work_keys_str_mv | AT demaineerikd variationsoninstantinsanity AT demainemartinl variationsoninstantinsanity AT morganthomasd variationsoninstantinsanity AT uehararyuhei variationsoninstantinsanity AT eisenstatsarahcharmian variationsoninstantinsanity |