Given a chain of $HW$ 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.
No takes yet. Share an insight, caveat, or question.
Group et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: