The reviewed record of science sign in
Pith

arxiv: 2407.10323 · v1 · pith:YFND47RH · submitted 2024-07-14 · cs.CC · cs.CG

Complexity of 2D Snake Cube Puzzles

Reviewed by Pithpith:YFND47RHopen to challenge →

classification cs.CC cs.CG
keywords cubestimesallowingcircstraightcubeturnturning
0
0 comments X
read the original abstract

Given a chain of $HW$ cubes where each cube is marked "turn $90^\circ$" or "go straight", when can it fold into a $1 \times H \times 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 \times H \times 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^\circ$, or turning $120^\circ$; and (5) allowing the cubes to be encoded implicitly to compress exponentially large repetitions.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.