Finding a Hamiltonian Path in a Cube with Specified Turns is Hard
We prove the NP-completeness of finding a Hamiltonian path in an N × N × N cube graph with turns exactly at specified lengths along the path. This result establishes NP-completeness of Snake Cube puzzles: folding a chain of N3 unit cubes, joined at face centers (usually by a cord passing through all...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Information Processing Society of Japan
2014
|
| Online Access: | http://hdl.handle.net/1721.1/86227 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-4295-1117 https://orcid.org/0000-0002-3182-1675 https://orcid.org/0000-0003-0198-3283 |
| _version_ | 1826217537661042688 |
|---|---|
| author | Abel, Zachary Ryan Demaine, Erik D. Demaine, Martin L. Eisenstat, Sarah Charmian Lynch, Jayson R. Schardl, Tao Benjamin |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Abel, Zachary Ryan Demaine, Erik D. Demaine, Martin L. Eisenstat, Sarah Charmian Lynch, Jayson R. Schardl, Tao Benjamin |
| author_sort | Abel, Zachary Ryan |
| collection | MIT |
| description | We prove the NP-completeness of finding a Hamiltonian path in an N × N × N cube graph with turns exactly at specified lengths along the path. This result establishes NP-completeness of Snake Cube puzzles: folding a chain of N3 unit cubes, joined at face centers (usually by a cord passing through all the cubes), into an N × N × N cube. Along the way, we prove a universality result that zig-zag chains (which must turn every unit) can fold into any polycube after 4 × 4 × 4 refinement, or into any Hamiltonian polycube after 2 × 2 × 2 refinement. |
| first_indexed | 2024-09-23T17:05:15Z |
| format | Article |
| id | mit-1721.1/86227 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T17:05:15Z |
| publishDate | 2014 |
| publisher | Information Processing Society of Japan |
| record_format | dspace |
| spelling | mit-1721.1/862272022-09-29T23:34:39Z Finding a Hamiltonian Path in a Cube with Specified Turns is Hard Abel, Zachary Ryan Demaine, Erik D. Demaine, Martin L. Eisenstat, Sarah Charmian Lynch, Jayson R. Schardl, Tao Benjamin Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics Abel, Zachary Ryan Demaine, Erik D. Demaine, Martin L. Eisenstat, Sarah Charmian Lynch, Jayson R. Schardl, Tao Benjamin We prove the NP-completeness of finding a Hamiltonian path in an N × N × N cube graph with turns exactly at specified lengths along the path. This result establishes NP-completeness of Snake Cube puzzles: folding a chain of N3 unit cubes, joined at face centers (usually by a cord passing through all the cubes), into an N × N × N cube. Along the way, we prove a universality result that zig-zag chains (which must turn every unit) can fold into any polycube after 4 × 4 × 4 refinement, or into any Hamiltonian polycube after 2 × 2 × 2 refinement. 2014-04-23T20:49:10Z 2014-04-23T20:49:10Z 2013-07 2012-08 Article http://purl.org/eprint/type/JournalArticle 1882-6652 http://hdl.handle.net/1721.1/86227 Abel, Zachary, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B. Schardl. “Finding a Hamiltonian Path in a Cube with Specified Turns Is Hard.” Journal of Information Processing 21, no. 3 (2013): 368–377. https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-4295-1117 https://orcid.org/0000-0002-3182-1675 https://orcid.org/0000-0003-0198-3283 en_US http://dx.doi.org/10.2197/ipsjjip.21.368 Journal of Information Processing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Information Processing Society of Japan MIT web domain |
| spellingShingle | Abel, Zachary Ryan Demaine, Erik D. Demaine, Martin L. Eisenstat, Sarah Charmian Lynch, Jayson R. Schardl, Tao Benjamin Finding a Hamiltonian Path in a Cube with Specified Turns is Hard |
| title | Finding a Hamiltonian Path in a Cube with Specified Turns is Hard |
| title_full | Finding a Hamiltonian Path in a Cube with Specified Turns is Hard |
| title_fullStr | Finding a Hamiltonian Path in a Cube with Specified Turns is Hard |
| title_full_unstemmed | Finding a Hamiltonian Path in a Cube with Specified Turns is Hard |
| title_short | Finding a Hamiltonian Path in a Cube with Specified Turns is Hard |
| title_sort | finding a hamiltonian path in a cube with specified turns is hard |
| url | http://hdl.handle.net/1721.1/86227 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-4295-1117 https://orcid.org/0000-0002-3182-1675 https://orcid.org/0000-0003-0198-3283 |
| work_keys_str_mv | AT abelzacharyryan findingahamiltonianpathinacubewithspecifiedturnsishard AT demaineerikd findingahamiltonianpathinacubewithspecifiedturnsishard AT demainemartinl findingahamiltonianpathinacubewithspecifiedturnsishard AT eisenstatsarahcharmian findingahamiltonianpathinacubewithspecifiedturnsishard AT lynchjaysonr findingahamiltonianpathinacubewithspecifiedturnsishard AT schardltaobenjamin findingahamiltonianpathinacubewithspecifiedturnsishard |