Paper by Erik D. Demaine

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)