Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2407.10323 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911955217809408 |
|---|---|
| author | MIT Hardness Group Anchaleenukoon, Nithid Dang, Alex Demaine, Erik D. Ji, Kaylee Saengrungkongka, Pitchayut |
| author_facet | MIT Hardness Group Anchaleenukoon, Nithid Dang, Alex Demaine, Erik D. Ji, Kaylee Saengrungkongka, Pitchayut |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_10323 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Complexity of 2D Snake Cube Puzzles MIT Hardness Group Anchaleenukoon, Nithid Dang, Alex Demaine, Erik D. Ji, Kaylee Saengrungkongka, Pitchayut Computational Complexity Computational Geometry 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. |
| title | Complexity of 2D Snake Cube Puzzles |
| topic | Computational Complexity Computational Geometry |
| url | https://arxiv.org/abs/2407.10323 |