Paper by Erik D. Demaine
- Zachary Abel, 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, volume 21, number 3, July 2013, pages 368–377.
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.
- This paper is also available from J-STAGE.
- The paper is available in PDF (3387k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated January 18, 2021 by