**Reference**:- MIT Hardness Group, Nithid Anchaleenukoon, Alex Dang, Erik D. Demaine, Kaylee Ji, and Pitchayut Saengrungkongka, “Complexity of 2D Snake Cube Puzzles”, in
*Proceedings of the 36th Canadian Conference on Computational Geometry (CCCG 2024)*, July 17–19, 2024, to appear. **Abstract**:-
Given a chain of
*H**W*cubes where each cube is marked “turn 90°” or “go straight”, when can it fold into a 1 ×*H*×*W*rectangular box? We prove several variants of this (still) open problem NP-hard: (1) allowing some cubes to be wildcard (can turn or go straight); (2) allowing a larger box with empty spaces (simplifying a proof from CCCG 2022); (3) growing the box (and the number of cubes) to 2 ×*H*×*W*(improving a prior 3D result from height 8 to 2); (4) with hexagonal prisms rather than cubes, each specified as going straight, turning 60°, or turning 120°; and (5) allowing the cubes to be encoded implicitly to compress exponentially large repetitions. **Comments**:- The paper is also available as arXiv:2407.10323.
**Length**:- The paper is 8 pages.
**Availability**:- The paper is available in PDF (426k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- FixedAngle_CCCG2022 (Computational Complexity of Flattening Fixed-Angle Orthogonal Chains)
- HamPath_JIP (Finding a Hamiltonian Path in a Cube with Specified Turns is Hard)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.