**Reference**:- 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. **Abstract**:-
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*N*^{3}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. **Comments**:- This paper is also available from J-STAGE.
**Availability**:- The paper is available in PDF (3387k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- FixedAngle_CCCG2022 (Computational Complexity of Flattening Fixed-Angle Orthogonal Chains)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.