settings.outformat = ”pdf”; texpreamble(””);

# Complexity of 2D Snake Cube Puzzles

MIT Hardness Group Artificial first author to highlight that the other authors
(in alphabetical order) worked as an equal group. Please include all authors
(including this one) in your bibliography, and refer to the authors as “MIT
Hardness Group” (without “et al.”). Nithid Anchaleenukoon MIT Computer Science
and Artificial Intelligence Laboratory, 32 Vassar St., Cambridge, MA 02139,
USA<EMAIL_ADDRESS>Alex
Dang22footnotemark: 2 Erik D. Demaine22footnotemark: 2 Kaylee
Ji22footnotemark: 2 Pitchayut Saengrungkongka22footnotemark: 2

###### 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.

##  1 Introduction

Snake Cube [ADD+13] is a physical puzzle consisting of wooden unit cubes
joined in a chain by an elastic string running through the interior of each
cube. For every cube other than the first and last, the string constrains the
two neighboring cubes to be at opposite or adjacent faces of this cube, in
other words, whether the chain must continue straight or turn at a
$90^{\circ}$ angle. In the various manufactured puzzles, the objective is to
rearrange a chain of $27$ cubes into a $3\times 3\times 3$ box.

To generalize this puzzle, we ask: given a chain of $DHW$ cubes, where $D,H,W$
are positive integers, is it possible to rearrange the cubes to form a
$D\times H\times W$ rectangular box? We call this problem $D\times H\times W$
Snake Cube. Previous results on its complexity include:

  * •

Abel et al. [ADD+13] proved $8\times H\times W$ Snake Cube is NP-complete by
reduction from $3$-Partition.

  * •

Demaine et al. [DILU22] proved 2D Snake Cube Packing—deciding whether a chain
of cubes can pack (but not necessarily fill) a $1\times H\times W$ rectangular
box where all cubes are constrained to align with the box—is NP-complete by
reduction from Linked Planar 3SAT. This result also holds for a closed chain
[DILU22].

This result improves a previous result by Demaine and Eisenstat [DE11], which
proves NP-hardness of the problem that given a sequence of angles in interval
$[16.26^{\circ},180^{\circ}]$, is there a non-crossing polyline of side-length
1 and the angle sequence as given. [DILU22] does this with angles only in
$\\{90^{\circ},180^{\circ}\\}$.

Both [ADD+13] and [DILU22] pose the (still) open problem of determining the
complexity of $1\times H\times W$ Snake Cube, illustrated in Figure 1:

######  Open Problem 1.1 (2D Snake Cube).

Is $1\times H\times W$ Snake Cube NP-hard?

###  1.1 Our Results

In this paper, we prove NP-hardness of several variations of Open Problem 1.1:

  * •

In Section 5, we prove NP-completeness of 2D Snake Cube with Wildcards, where
some instructions can be the wildcard *, allowing a free choice between
straight or turn.

We also give an alternative proof that 2D Snake Cube Packing is NP-complete,
simplifying [DILU22].

  * •

In Section 6, we prove that $2\times H\times W$ Snake Cube is NP-complete.
This improves the result of Abel et al. [ADD+13] from $D=8$ to $D=2$.

  * •

In Section 7, we prove NP-completeness of Hexagonal 2D Snake Cube Packing:
deciding whether a chain of hexagonal prisms each specified as going straight,
turning $60^{\circ}$, or turning $120^{\circ}$ can be packed into a
$60^{\circ}$, $H\times W$ parallelogram. Similar to [DILU22], we extend this
result to closed chains. One can view this as an improvement to [DE11] in that
angles can be restricted to be in $\\{60^{\circ},120^{\circ}\\}$.

  * •

In Section 8, we prove _weak_ NP-hardness of 2D Snake Cube, when the input
instructions can be encoded to efficiently represent repeated sequences.

The first three results are all based on a common framework for reduction from
Numerical 3D Matching, detailed in Sections 3 and 4, while the last result is
a reduction from 2-Partition. We introduce the two base problems we reduce
from, and formally define the problems we prove hard, in Section 2.

##  2 Definitions

###  2.1 Problem Statement

First, we define the problems we analyze in more precise terms.

The input to all snake-cube problems is a “box” and a “program”; refer to
Figure 1. A box is a $D\times H\times W$ rectangular cuboid that the cubes of
the snake-cube puzzle must fit into. This box can be visualized as a cubic
grid where each cube occupies one space of the grid. A program
$\mathcal{P}=(p_{1},p_{2},\ldots,p_{k})$ is a length-$k$ string of
instructions, where each instruction $p_{i}$ is either the character S
(“straight”) or T (“turn”). The corresponding chain is the sequence
$c_{1},c_{2},\dots,c_{k}$ of pairwise distinct and consecutively adjacent
cubes that must follow the program in the sense that each instruction $p_{i}$
(where $i\in\\{2,\ldots,k-1\\}$) constrains the angle between the three cubes
$c_{i-1},c_{i},c_{i+1}$ to be $180^{\circ}$ for $p_{i}=\texttt{S}$ (i.e.,
going straight), and $90^{\circ}$ for $p_{i}=\texttt{T}$ (i.e., turning with
_absolute_ turn angle $90^{\circ}$). (Note that the first and last
instructions have no effect; we include them so that cubes and instructions
have a bijection.) A length-$k$ segment refers to a subchain of $k$
consecutive cubes that are constrained to form a straight line (e.g., the
subchain following the instructions TSSST is a length-$5$ segment).

asy/example_unfolded.asy

(a) An unfolded chain following the input program

asy/example_folded.asy

(b) A solution of the given instance.

Figure 1: An example instance of $D\times H\times W$ Snake Cube with input
$D=1$, $H=5$, $W=5$, and the program STTSSSTSSSTTSSTTSSTSTTTTT. The gray and
white cells represent cubes following instructions T and S, respectively.

######  Definition 2.1.

$D\times H\times W$ Snake Cube is the problem of deciding, given positive
integers $D$, $H$, $W$ (defining the box) and program $\mathcal{P}$ of length
$DHW$, whether there is a chain of cubes following the program $\mathcal{P}$.
2D Snake Cube refers to the special case of $D=1$.

######  Definition 2.2.

2D Snake Cube Packing is a variant of 2D Snake Cube where $\mathcal{P}$ may
have length less than $DHW$. Thus, the chain does not necessarily include all
cubes in the box, but must stay within the box.

######  Definition 2.3.

2D Snake Cube with Wildcards is a variant of 2D Snake Cube in which
$\mathcal{P}$ may contain a third character *, where $p_{i}=\texttt{*}$
constrains the angle between the three cubes $c_{i-1},c_{i},c_{i+1}$ to be
either $90^{\circ}$ or $180^{\circ}$.

We also consider Hexagonal 2D Snake Cube Packing, a version of 2D Snake Cube
on hexagonal prisms with three different characters: one constraining the
chain to go straight, one constraining the chain to turn by $\pm 60^{\circ}$,
and one constraining the chain to turn by $\pm 120^{\circ}$. We more formally
define this in Section 7.

We use the notation $(s)^{k}$ to denote the instruction sequence $s$ repeated
$k$ times. For example, $\texttt{T}(\texttt{SST})^{2}$ represents the sequence
TSSTSST. For almost all our proofs, this notation is just convenient
shorthand. The exception is our proof that 2D Snake Cube is weakly NP-hard,
which requires the input instruction to be compressed using this encoding,
i.e., encode $(s)^{k}$ using $|s|+O(\log k)$ bits.

All of these problems, with the exception of 2D Snake Cube under the special
encoding, are in NP: to verify a solution, simply check all angle constraints
(of which there are linearly many) and that the chain remains within the box.
This algorithm is linear in both time and space. Thus, showing any of these
problems is NP-hard suffices to establish NP-completeness.

###  2.2 2-Partition

Our weak NP-hardness of 2D Snake Cube (in Section 8) will reduce from
2-Partition, defined as follows:

######  Definition 2.4 (2-Partition).

Given a multiset $A=\\{a_{1},a_{2},\ldots,a_{n}\\}$ of positive integers,
2-Partition is the problem of deciding whether there exists a partition of
sets $A$ into disjoint union $A_{1}\sqcup A_{2}$ such that the sums of
elements in $A_{1}$ and in $A_{2}$ are equal.

We will need the following known result:

######  Theorem 2.5.

2-Partition is weakly NP-hard, i.e., NP-hard when the numbers $a_{i}$ are
encoded in binary (and thus could be exponential in value).

###### Proof.

This is listed as Problem SP12 in Garey and Johnson’s compilation [GJ90,
Section A3.2]. ∎

###  2.3 Numerical 3D Matching

Our other (strong) NP-hardness proofs are reductions from Numerical 3D
Matching, defined as follows:

######  Definition 2.6.

For any given target sum $t$ and sequences $(a_{i})_{i=1}^{n}$,
$(b_{i})_{i=1}^{n}$, and $(c_{i})_{i=1}^{n}$, each consisting of $n$ positive
integers, Numerical 3D Matching (Numerical 3DM) is the problem of deciding
whether there exist permutations $\sigma$ and $\pi$ of the set
$\\{1,2,\dots,n\\}$ that satisfies $a_{i}+b_{\sigma(i)}+c_{\pi(i)}=t$ for all
$i$. We refer to such a solution $(\sigma,\pi)$ as a matching.

######  Theorem 2.7.

Numerical 3DM is strongly NP-hard, i.e., NP-hard when the numbers
$a_{i},b_{i},c_{i},t$ are encoded in unary (and thus are polynomial in value).

###### Proof.

This is listed as Problem SP16 in Garey and Johnson’s compilation [GJ90,
Section A3.2]. ∎

In fact, we will consider the following slightly modified version of 3D
Matching.

######  Proposition 2.8.

Numerical 3DM is strongly NP-hard even when we assume that
$a_{i}\in(0.5t,0.6t)$, $b_{i}\in(0.25t,0.3t)$, and $c_{i}\in(0.125t,0.15t)$
for all $1\leq i\leq n$.

###### Proof.

Suppose that we have an instance of Numerical 3DM $a_{1},\dots,a_{n}$,
$b_{1},\dots,b_{n}$, $c_{1},\dots,c_{n}$ with target sum $t$. We can transform
the instance by defining a variable $X$ and setting

$a_{i}^{\prime}=a_{i}+4X,\qquad b_{i}^{\prime}=b_{i}+2X,\qquad
c_{i}^{\prime}=c_{i}+X,\qquad t^{\prime}=t+7X.$

Intuitively, when $X$ is sufficiently large, we have $t^{\prime}\approx 7X$,
so $a_{i}^{\prime}\approx\frac{4}{7}t^{\prime}$,
$b_{i}^{\prime}\approx\frac{2}{7}t^{\prime}$, and
$c_{i}^{\prime}\approx\frac{1}{7}t^{\prime}$, which makes all inequalities
hold. To be more precise, we claim that, for any $X$ larger than a bound
depending polynomially on $a_{i}$, $b_{i}$, $c_{i}$, and $n$, we have

$a_{i}^{\prime}\in(0.5t^{\prime},0.6t^{\prime}),\qquad
b_{i}^{\prime}\in(0.25t^{\prime},0.3t^{\prime}),\quad\text{ and }\quad
c_{i}^{\prime}\in(0.125t^{\prime},0.15t^{\prime}).$

To see why, note that in order for the first inequality to hold, we must have

$a_{i}+4X>0.5(t+7X)\iff X>t-2a_{i}\quad\text{ and }\quad
a_{i}+4X<0.6(t+7X)\iff X>5a_{i}-3t.$

Solving the other two inequalities, we find that we need

$X>\max\\{t-4b_{i},10b_{i}-3t,t-8c_{i},20c_{i}-3t\\}.$

Thus, we only need $X$ to be greater than the maximum of six linear
expressions in $a_{i}$, $b_{i}$, $c_{i}$, and $t$. Taking the maximum across
all $i$, we get that the working $X$ has polynomial size as claimed. ∎

##  3 Overview of Reductions from Numerical 3DM

The reductions in Sections 5, 6, and 7 all share a similar infrastructure,
which we informally outline here. In this overview, we assume $D=1$. We
explain how to adapt this framework to $D=2$ in Section 6.

We reduce from Numerical 3DM. Let $(a_{i})_{i=1}^{n}$, $(b_{i})_{i=1}^{n}$,
and $(c_{i})_{i=1}^{n}$ be the input numbers to match with target sum $t$. By
Proposition 2.8, we can assume that $a_{i}\in(0.5t,0.6t)$,
$b_{i}\in(0.25t,0.3t)$, and $c_{i}\in(0.125t,0.15t)$. We also pick the
following parameters:

$\displaystyle g$ $\displaystyle=\Theta(n)$ $\displaystyle\text{(the gap
size)},$ $\displaystyle h$ $\displaystyle=\Theta(n^{2})$
$\displaystyle\text{(the height of each block)},$ $\displaystyle m$
$\displaystyle=\Theta(n^{3})$ $\displaystyle\text{(the unit width of each
block)}.$

The structure of the reduction is as follows. The dimensions of the box are
$D\times H\times W=1\times(nh+(n+1)g)\times(mt+4g)$. The numbers
$(a_{i})_{i=1}^{n}$, $(b_{i})_{i=1}^{n}$, and $(c_{i})_{i=1}^{n}$ are
represented by block gadgets $(\langle A_{i}\rangle)_{i=1}^{n}$, $(\langle
B_{i}\rangle)_{i=1}^{n}$, and $(\langle C_{i}\rangle)_{i=1}^{n}$, instructions
corresponding to the subchains $(A_{i})_{i=1}^{n}$, $(B_{i})_{i=1}^{n}$, and
$(C_{i})_{i=1}^{n}$ that can fold into cuboids of dimensions $1\times h\times
ma_{i}$, $1\times h\times mb_{i}$, and $1\times h\times mc_{i}$, respectively.
We call these subchains blocks. Block gadgets typically consist of $h$ long
segments (of common length $mx$) interspersed by $h-1$ length-$2$ segments, as
shown in Figure 2(a), but details vary in different variants. Between every
two consecutive block gadgets, we add a wiring gadget, a sequence of
instructions that allows connecting the two blocks no matter where they are in
the box.

asy/single_block.asy

(a) Example of block $\langle A_{i}\rangle$ in 2D

asy/reduction_outline.asy

(b) Overall structure of the reduction

Figure 2: The reduction

If a matching exists (i.e., there exist two permutations $\sigma$ and $\pi$ of
$\\{1,2,\ldots,n\\}$ such that $a_{i}+b_{\sigma(i)}+c_{\pi(i)}=t$ for all
$i$), then (ignoring the wiring gadgets) the blocks can be arranged into a
perfect $1\times nh\times mt$ rectangle, by aligning each triple of blocks
$A_{i}$, $B_{\sigma(i)}$, and $C_{\pi(i)}$ together in the same row. Refer to
Figure 2(b). Because our box is slightly larger than $1\times nh\times mt$, we
can place the blocks with a gap of $g$ between neighboring blocks and between
each block and the boundary of the rectangular box. The gap $g$ is chosen so
there is sufficient space for a subchain following the wiring gadget to
connect all the blocks. Wires detour around blocks and do not cross; the
explicit algorithm for folding the subchain will be given in Lemma 4.4.
Finally, depending on the variant, there may be additional instructions at the
end of the program corresponding to the cubes needed to fill the remaining
space in the box.

In the other direction, we also need to show that the existence of a chain
satisfying the instructions forces the existence of a corresponding matching.
One might expect $\langle A_{i}\rangle$, $\langle B_{i}\rangle$, and $\langle
C_{i}\rangle$ to fold into blocks and pack into the grid equally-spaced apart,
which will immediately force the existence of a matching. However, there are
two major difficulties.

  * •

First, part of the chain corresponding to $\langle B_{i}\rangle$ and $\langle
C_{i}\rangle$ can slide between the blocks $A_{i}$s, causing various
unexpected configurations.

  * •

Even if the blocks do fold into perfect rectangles, one must rule out the case
when it is packed with unequal spacing between blocks.

To get around these issues, we will prove Lemma 4.1 that will force the
existence of matching even if blocks do not fold ideally.

##  4 Common Results

In this section, we will collect arguments that are shared across different
reductions from Numerical 3DM.

###  4.1 Segment Packing Lemma

This subsection concerns the part “Chain $\Rightarrow$ Matching” (i.e.,
proving the existence of Numerical 3DM matching). As said earlier in Section
3, we need to force the existence of a matching even when blocks do not fold
into ideal rectangles or are unevenly spaced. To do so, we will prove the
“Segment Packing Lemma” (Lemma 4.1), which will be used in Sections 5 and 7.

We first explain the motivation of this lemma. Recall a block gadget typically
consists of $h$ long segments interspersed with $h-1$ length-2 segments.
Therefore, for instance, any block $A_{i}$ must have $h$ segment of length
$ma_{i}$. The idea is to view a block as a collection $h$ horizontal segments.
Therefore, in any chain satisfying the program in the outline, we must have
$3nh$ segments, $h$ of each length $ma_{1},\dots,ma_{n}$,
$mb_{1},\dots,mb_{n}$, $mc_{1},\dots,mc_{n}$ that were packed in a grid. This
motivates the “Segment Packing Lemma”.

The setup of this lemma is as follows. Let $a_{1},\dots,a_{n}$,
$b_{1},\dots,b_{n}$, $c_{1},\dots,c_{n}$ be positive integers summing to $nt$.
Assume the condition in Proposition 2.8: for all $i$, we have

$a_{i}\in(0.5t,0.6t),\qquad b_{i}\in(0.25t,0.3t),\quad\text{ and }\quad
c_{i}\in(0.125t,0.15t).$

Let $m$ and $h$ be positive integers such that $m>H$, and consider a $H\times
W$ rectangle. Inside this rectangle, there are $3nh$ segments, each of which
is horizontal. The segments are classified into $3n$ types:

  * •

$n$ types of A-segments: types $A_{1}$, $A_{2}$, …, $A_{n}$;

  * •

$n$ types of B-segments: types $B_{1}$, $B_{2}$, …, $B_{n}$; and

  * •

$n$ types of C-segments: types $C_{1}$, $C_{2}$, …, $C_{n}$.

######  Lemma 4.1 (Segment Packing Lemma).

Suppose that along with our setup, we also have that

$W<m(t+1)\quad\text{and}\quad H<nh+\frac{h}{40}$

and all of the following are true:

  * •

There are exactly $h$ segments of each type.

  * •

For all $1\leq i\leq n$, all segments of type $A_{i}$, $B_{i}$, and $C_{i}$
have lengths $ma_{i}$, $mb_{i}$, and $mc_{i}$, respectively.

  * •

No two segments of the same type are more than $h$ rows vertically apart.

Then, there exists a matching of the instance $(a_{i})_{i=1}^{n}$,
$(b_{i})_{i=1}^{n}$, and $(c_{i})_{i=1}^{n}$ of Numerical 3DM.

The rest of the subsection is devoted to proving the lemma. Assume the lemma
setup throughout. First, we make the following observations.

######  Proposition 4.2.

We have the following.

  1. (i)

Any row must have at most one A-segment.

  2. (ii)

If a row contains one A-segment, it must contain at most one B-segment.

  3. (iii)

If a row contains one A-segment and one B-segment, then it must contain at
most one C-segment.

###### Proof.

Note that the length of an A-segment is $ma_{i}\geq 0.5m(t+1)>0.5W$, the
length of a B-segment is $mb_{i}\geq 0.25m(t+1)>0.25W$, and the length of a
C-segment is $mc_{i}\geq 0.125m(t+1)>0.125W$. With these, we now prove each
part as follows.

  1. (i)

More than one A-segment will span a width exceeding $W$, a contradiction.

  2. (ii)

If a row contains one A-segment and more than one $B$-segment, the length will
be at least $ma_{i}+2mb_{i}>0.5W+2\cdot 0.25W=W$, a contradiction.

  3. (iii)

If a row contains one A-segment, one $B$-segment, and more than one
$C$-segment, the length will be at least
$ma_{i}+mb_{i}+2mc_{i}>0.5W+0.25W+2\cdot 0.125W=W$, a contradiction. ∎

From Proposition 4.2, each row in the grid must be of one of the following
four categories.

  * •

A _good row_ , which contains exactly one A-segment, one B-segment, and one
C-segment.

  * •

An _A-bad row_ , which contains no A-segment.

  * •

A _B-bad row_ , which contains one A-segment but contains no B-segment.

  * •

A _C-bad row_ , which contains one A-segment, one B-segment, but no C-segment.

Let $n_{\text{good}}$, $n_{A}$, $n_{B}$, and $n_{C}$ denote the number of good
rows, $A$-bad rows, $B$-bad rows, and $C$-bad rows, respectively. The critical
claim is the following.

######  Claim 4.3.

$n_{A}+n_{B}+n_{C}<h$.

###### Proof.

First, we note that there are $H<nh+h/40$ rows. Of these, $nh$ must contain an
$A$-path, so

$n_{A}<\frac{h}{40}.$

Next, there are $nh$ B-segments. The good rows and C-bad rows contain at most
one B-segment. Moreover, since the length of each B-segment is strictly
greater than $0.25W$, each A-bad row contains at most $3$ B-segments. Thus,

$\displaystyle nh\leq 3n_{A}+n_{C}+n_{\text{good}}\implies n_{B}$
$\displaystyle\leq 2n_{A}+(n_{A}+n_{B}+n_{C}+n_{\text{good}})-nh$
$\displaystyle=2n_{A}+\frac{h}{40}<\frac{3h}{40}.$

Finally, there are $nh$ C-segments. The good rows contain at most one
C-segment. Moreover, the length of each C-segment is strictly greater than
$0.125W$, so each A-bad row contains at most $7$ C-segments and each B-bad row
contains at most $3$ C-segments. Thus,

$\displaystyle nh\leq 7n_{A}+3n_{B}+n_{\text{good}}\implies n_{C}$
$\displaystyle\leq 6n_{A}+2n_{B}+(n_{A}+n_{B}+n_{C}+n_{\text{good}})-nh$
$\displaystyle=6n_{A}+2n_{B}+\frac{h}{40}<\frac{13h}{40}.$

Summing these three bounds gives the claim. ∎

Finally, we are ready to prove that the solution to an instance of Numerical
3DM exists.

###### Proof of Lemma 4.1.

Color each row by its residue modulo $h$. Thus, each color has either $n$ or
$n+1$ rows. By Claim 4.3, there are less than $h$ bad rows, so there is a
color $c$ such that all rows of that color are good. Moreover, each block
gadget spans the height at most $h$, so each block covers at most one row of
color $c$. Thus, there are exactly $n$ rows of color $c$. For each row, if
that row contains a path from blocks $\langle A_{i}\rangle$, $\langle
B_{j}\rangle$, $\langle C_{k}\rangle$, then by counting the lengths of the
path, we have

$ma_{i}+mb_{j}+mc_{k}\leq W<m(t+1)\implies a_{i}+b_{j}+c_{k}\leq t.$

Summing this inequality for each row gives $nt\leq nt$, so all inequalities
must be equalities, giving that $a_{i}+b_{j}+c_{k}=t$, forming the desired
matching. ∎

###  4.2 Connecting Wires

This subsection concerns the wiring part and is the most technical part of
this paper. It guarantees that, if the gap is large enough, there exists a way
to wire blocks $A_{1},\dots,A_{n}$, $B_{1},\dots,B_{n}$ and
$C_{1},\dots,C_{n}$, no matter what positions they are placed in the packing.
This lemma was adapted from [AD11, Lemma 5]. The existence will be proved by
providing an algorithm to draw wires.

asy/wiring_setup.asy

Figure 3: Example of the setup wire packing when $n=3$. The red area
represents the available space.

The setup for this lemma is depicted in Figure 3 and goes as follows: in a
grid of squares, there are rectangles $X_{1},X_{2},\dots,X_{n}$, of height
$h^{\prime}$ squares and widths $x_{1},x_{2},\dots,x_{n}$ squares packed in a
rectangular $H^{\prime}\times w_{X}$ grid (height $H^{\prime}$). Note that
while “rectangles” and “blocks” refers to the same object, “squares” and
“cubes” are not the same; when applying this lemma to prove the construction
of the wiring gadgets, each square is filled with $2\times 2$ cubes. This will
be discussed further in Section 5. We use these terms here to avoid confusion
when referring to the length. For example, if a rectangle has height of
$h^{\prime}$ squares in this section, when applying to the actual instance of
2D snake cube, a corresponding “block” would have height $h=2h^{\prime}$
cubes.

A matching forces each row to contain at most one rectangle (i.e., rectangles
are not overlapped and cannot be placed side by side), but they are in
arbitrary order from top to bottom. Suppose the gap between two rectangles has
width $g^{\prime}$ squares. Define available space of a rectangle to be a set
of squares outside it that forms an extension to a rectangle by $g^{\prime}/2$
squares on each side. An overall available space is the union of all available
spaces across all rectangles, which is shown as the red area in Figure 3. For
each $i$, let $s_{i}$ and $f_{i}$ be the squares at the bottom left and top
left corners of $X_{i}$, respectively. We also let $f_{0}$ and $s_{n+1}$ be
the beginning and the ending point in the available space lying below every
rectangle at least $4n+4$ squares apart; they are both horizontally at least
$10n$ tiles away from the left edges of all rectangles.

For each $i\in\\{0,1,\dots,n\\}$, we want to connect from square $f_{i}$ to
square $s_{i+1}$ with a wire $W_{i}$ of length $\ell_{i}$, defined as a path
of $\ell_{i}$ squares such that any two consecutive squares share a common
side. This is guaranteed to be possible if the gap between rectangles is large
enough, as we explain below.

######  Lemma 4.4 (Wire Lemma).

Assume the setup in the above three paragraphs. Assume that
$\min_{i}x_{i}>w_{X}/2$, $H<w_{X}$ and the gaps between rectangles have width
at least $g^{\prime}\geq 100n$ squares. For each $i=0,1,\dots,n$, let
$\ell_{i}$ be an even integer in $[8nw_{A},12nw_{A}]$. Then, one can draw
$n+1$ disjoint wires $W_{0},\dots,W_{n}$ in the overall available space, where
$W_{i}$ has length exactly $\ell_{i}$ and $W_{i}$ connects $f_{i}$ to
$s_{i+1}$ for all $i\in\\{0,1,\dots,n\\}$. Furthermore, no two cells in
different wires $W_{i}$ and $W_{j}$ are adjacent.

######  Remark 4.5.

In Sections 5 and 7, we can set $\ell_{i}=8nw_{X}$. For Section 6, we need to
set $\ell_{i}=12nw_{X}$ since wires have to detour around the “shelf”, an
additional structure that will be defined there.

###### Proof.

We mark squares $m_{0}=f_{0},m_{1},\dots,m_{n},m_{n+1}=s_{n+1}$, all in the
same row, with distance at least $4$ apart from right to left. The square
$m_{i}$ will be in the middle of the wire $W_{i}$. Thus, it suffices to draw
$2n$ wires: $U_{i}$ from $m_{i-1}$ to $s_{i}$ and $V_{i}$ from $m_{i}$ to
$f_{i}$ for each $i=1,2,\dots,n$. After that, we can set $W_{i}$ to be
concatenation of $V_{i}$, a square $m_{i}$, and $U_{i+1}$ for all
$i\in\\{1,\dots,n-1\\}$. Moreover, let $W_{0}=U_{1}$ and $W_{n}=V_{n}$.
Inductively running $i$ from $1,2,\dots,n$, we will draw $U_{i},V_{i}$ after
$U_{1},V_{1},\dots,U_{i-1},V_{i-1}$ has been drawn. The following diagram
illustrates the notion described.

$\underbrace{f_{0}=m_{0}\xrightarrow{U_{1}}}_{W_{0}}\langle
X_{1}\rangle\underbrace{\xrightarrow{V_{1}}m_{1}\xrightarrow{U_{2}}}_{W_{1}}\langle
X_{2}\rangle\xrightarrow{V_{2}}m_{2}\cdots\xrightarrow{U_{i}}\langle
X_{i}\rangle\underbrace{\xrightarrow{V_{i}}m_{i}\xrightarrow{U_{i+1}}}_{W_{i}}\langle
X_{i+1}\rangle\xrightarrow{V_{i+1}}\cdots\xrightarrow{U_{n}}\langle
X_{n}\rangle\underbrace{\xrightarrow{V_{n}}}_{W_{n}}m_{n}=s_{n+1}$

The process of drawing wires is depicted in Figure 6 and consists of two
stages.

  1. (a)

For each $i$, draw $U_{i}$ and $V_{i}$ without crossing the previously-drawn
wires so that both $U_{i}$ and $V_{i}$ have length less than $\ell_{i}/2$.

  2. (b)

Adjust the length of $W_{i}$ so that its length is exactly $\ell_{i}$.

We first explain how to do (b). For each $i$, reserve the space of height
$40n$ on the top and bottom of the rectangle $X_{i}$. This space should not be
used by any wires during stage (a). Thus, we have the space of area greater
than $(40n)(w_{X}/2)=20nw_{X}$ on each side for any $i$. Then, for each
incoming wire $U_{i}$ and $V_{i}$, adjust the wire $U_{i}$ to coil around the
top of $X_{i}$ and the wire $V_{i}$ to coil around the bottom of $X_{i}$ as
shown in Figure 4. This way, we can add any even number of lengths of $U_{i}$
and $V_{i}$ not exceeding half the area, which is greater than
$\frac{20nw_{X}}{2}>6nw_{X}\geq\ell_{i}/2$. Since the parity of the length of
the wire is solely determined by the start and the ending point, one can get
the wires to have lengths exactly $\ell_{i}$.

asy/reserved_space_1

Figure 4: Packing of wires in the reserved spaces on the top and bottom of the
rectangle.

The rest of the proof is concentrated on (a). Reserve more space of width
$10n$ and height $h+80n$ on the left of each rectangle $X_{i}$ and previously
reserved space.

Consider a broken segment $L$ along the edges in the grid formed by vertical
and horizontal segments satisfying the properties that each vertical segment
of $L$ is the left edges of the reserved space of some rectangles, extended by
$g^{\prime}/2$ on each end, and horizontal segments are allowed only at the
middle of a gap between two consecutive rectangles to join the ends of two
neighboring vertical segments, as shown in Figure 6. Since $f_{0}$ and
$s_{n+1}$ are at least $10n$ squares horizontally away from the left edges of
all rectangles, $m_{i}$ is on the left side of all $X_{i}$ rectangles and $L$
for all $i$.

asy/reserved_left.asy

Figure 5: Example of wires after Adjust Crossing step when $X_{2}$ is placed
above $X_{1}$, $X_{3}$, and $X_{4}$. Since wires $U_{1}$ and $V_{1}$ are
placed before $U_{2}$ and $V_{2}$, they do not have to detour around $X_{2}$.
However, since wires $U_{3}$, $V_{3}$, $U_{4}$, and $V_{4}$ are placed after
$U_{2}$ and $V_{2}$, they have to detour around $X_{2}$ (The lengths depicted
are very not to scale.)

asy/wiring_overall.asy

Figure 6: Example of wire packing when $n=3$ without length adjustment. (The
lengths depicted are very not to scale.)

Now, we will explain how to place $U_{i}$ from $m_{i-1}$ to $s_{i}$ and
$V_{i}$ from $m_{i}$ to $f_{i}$. Call all squares in the reserved spaces and
rectangles occupied. The process is in three steps.

  1. 1.

Travel up. We draw the wires $U_{i}$ and $V_{i}$ from $m_{i-1}$ and $m_{i}$,
respectively to the topmost gap so that they are as close to $L$ as possible
but still leaving $1$ square gap from the previous wires. Since there are $2n$
wires, this ensures that all wires are at most $4n$ squares from all the
occupied space. Thus, including all the reserved space, the wire will be at
most $4n+40n<g^{\prime}/2$ away from the edges of rectangles with the
condition that this part of the wires will not overlap with the rectangles or
other wires.

  2. 2.

Drop down. We drop these wires down on the right of $L$ to the left reserve
space of $X_{i}$ with $1$ square gap from the previous wires (or from $L$ if
they are the first pair of wires). Now, we can trace $U_{i}$ to $s_{i}$ and
$V_{i}$ to $f_{i}$. During the drop, these wires may cross existing wires
$U_{j}$ and $V_{j}$ for some $j<i$. Since there are $2n$ wires, the reserved
space with the width $10n>(2n)(2)$ is enough to make sure that the wire will
not overlap the rectangle, and that the remaining space is connected.

  3. 3.

Adjust crossing. Wires $U_{i}$ and $V_{i}$ may intersect wires $U_{j}$ and
$V_{j}$, which are connected to rectangle $X_{j}$, for some $j<i$ when $U_{i}$
and $V_{i}$ attempt to go through the reserved space on the left of $X_{j}$.
If this happens, wrap $U_{i}$ and $V_{i}$ precisely around the reserve space
of $X_{j}$, which means that we will leave $1$ square gap from any rectangles
$X_{j}$ or wires $U_{k}$ and $V_{k}$ ($k<i$) that previously wrapped around
$X_{j}$. This is always possible because there are at most $2n$ wires that
will wrap each rectangle $X_{i}$. As a result, the width of the extension
$4n<10n=g^{\prime}/2-40n$ outside their reserved space is sufficient to
contain $2n$ wires stacked on each edge of $X_{i}$ with one square gap between
different wires. Note that we do not allow wire $U_{i}$ or $V_{i}$ to wrap
around rectangle $X_{j}$ for $j>i$.

Now, we calculate the length of wires for only one of $U_{i}$ or $V_{i}$
needed before adjusting the length by considering the horizontal length and
vertical length separately and then combining.

The vertical distance that each wire travels is at most $2H^{\prime}$ because
each wire $U_{i}$ travels directly up first and then travels down to the
position without going up again, and the wire travels each direction (up or
down) for at most $H^{\prime}$ in total.

For the total horizontal distance of $U_{i}$ and $V_{i}$, wires travel
horizontally at most once between each gap in each of traveling up and
dropping down processes, so wires travel horizontally for at most $n+1$ times
each process. Each time, a wire travels for the distance at most $w_{X}/2$.
For adjusting crossing, each wire goes left and right once along the edge of
those rectangles. However, there are at most $n-1$ rectangles to detour,
contributing to at most $2(n-1)w_{X}$ squares in length. Therefore, the total
distance each wire travels is at most
$2(n+1)(w_{X}/2)+2(n-1)w_{X}+2H^{\prime}<4nw_{X}$, so the total distance of
the wire $W_{i}$, which combines both $V_{i}$ and $U_{i+1}$, is at most
$8nw_{X}$. ∎

###  4.3 Filling the Space

The following lemma gives a simple condition that guarantees a Hamiltonian
cycle in a grid graph, which will be useful in densely filling the space in
Sections 5 and 6. The reference of this lemma is from [CDBG11], but we give a
full statement and proof for completeness.

######  Lemma 4.6 (Hamiltonicity of $2\times 2$ Polygrid).

Let $T$ be a connected set of squares in a square grid. Let $T^{\prime}$ be
the set $T$ when each square in $T$ is replaced by a $2\times 2$ subgrid.
Then, there is a Hamiltonian cycle visiting every square in $T^{\prime}$.

Moreover, the Hamiltonian cycle has the following property: for each $2\times
2$ subgrid obtained from a single square in $T$ and for each side on the
boundary, the two squares on that side are adjacent in a path.

To illustrate the “moreover” statement, Figure 7(a) shows the edges that are
required by the lemma statement.

asy/2x2_induct_condition.asy

(a) Edges required by the statement of Lemma 4.6.

asy/2x2_induction.asy

(b) Induction argument in Lemma 4.6.

Figure 7: The lemma for filling the space

###### Proof.

We do induction on $\lvert T\rvert$. The base case $\lvert T\rvert=1$ is
clear. For the inductive step, let $s$ be a square in $T$ such that
$T\setminus\\{s\\}$ is still connected. By induction hypothesis, take a
Hamiltonian cycle satisfying the requirement of the lemma. Then, since $s$ is
adjacent to another square $s^{\prime}\in T$ and by induction hypothesis, that
side of $s^{\prime}$ must have the required edge. Thus, one can replace that
required edge with a detour to the four squares in the subgrid of $s$ as in
Figure 7(b). This completes the proof. ∎

##  5 Snake Cube Puzzles in $\boldsymbol{1\times H\times W}$ box

In this section, we consider the 2-dimensional variants of Snake Cube. We
first consider 2D Snake Cube with Wildcards, where we allow the wildcard *
which could be used as either S or T. We will prove the following:

######  Theorem 5.1.

2D Snake Cube with Wildcards is NP-hard.

Section 5.1, 5.2, and 5.3 will prove Theorem 5.1. Then, in Section 5.4, we
will also outline an alternative proof of the following, which was first
proved in [DILU22].

######  Theorem 5.2.

2D Snake Cube Packing is NP-hard.

###  5.1 Setup

Given an instance of Numerical 3DM $a_{1},\dots,a_{n}$, $b_{1},\dots,b_{n}$,
$c_{1},\dots,c_{n}$ with target sum $t$, and assuming the condition of
Proposition 2.8 that $a_{i}\in(0.5t,0.6t)$, $b_{i}\in(0.25t,0.3t)$, and
$c_{i}\in(0.125t,0.15t)$ for all $i$, we set the following parameters to
construct the input program of 2D Snake Cube with Wildcards.

$\begin{array}[]{rclrcl}g=&\text{gap width}&=200n&H=&\text{height of the
grid}&=nh+(n+1)g\\\\[2.0pt] h=&\text{height of
blocks}&=20000n^{2}&W=&\text{width of the grid}&=mt+4g\\\\[2.0pt]
m=&\text{multiplier of widths}&=30000n^{3}&\ell_{A}=&\text{length of the
wires}&=16nW\\\\[2.0pt] \ell_{B}=&\text{length of the
wires}&=8nW&\ell_{C}=&\text{length of the wires}&=4nW\end{array}$

We will construct block gadgets $A_{i}$, $B_{i}$, and $C_{i}$ for all $1\leq
i\leq n$. These blocks will be expected to fold into rectangles of size
$h\times ma_{i}$, $h\times mb_{i}$, or $h\times mc_{i}$.

$\displaystyle\langle A_{i}\rangle$
$\displaystyle=(\texttt{S})^{ma_{i}-1}(\texttt{TT}(\texttt{S})^{ma_{i}-2})^{h-1}\texttt{S}$
$\displaystyle\langle B_{i}\rangle$
$\displaystyle=(\texttt{S})^{mb_{i}-1}(\texttt{TT}(\texttt{S})^{mb_{i}-2})^{h-1}\texttt{S}$
$\displaystyle\langle C_{i}\rangle$
$\displaystyle=(\texttt{S})^{mc_{i}-1}(\texttt{TT}(\texttt{S})^{mc_{i}-2})^{h-1}\texttt{S}$

The program we will use is the following:

$\displaystyle\mathcal{P}=$ $\displaystyle\langle
A_{1}\rangle(\texttt{*})^{\ell_{A}}\langle
A_{2}\rangle(\texttt{*})^{\ell_{A}}\dots(\texttt{*})^{\ell_{A}}\langle
A_{n}\rangle(\texttt{*})^{\ell_{A}}$ $\displaystyle\quad\langle
B_{1}\rangle(\texttt{*})^{\ell_{B}}\langle
B_{2}\rangle(\texttt{*})^{\ell_{B}}\dots(\texttt{*})^{\ell_{B}}\langle
B_{n}\rangle(\texttt{*})^{\ell_{B}}$ $\displaystyle\quad\langle
C_{1}\rangle(\texttt{*})^{\ell_{C}}\langle
C_{2}\rangle(\texttt{*})^{\ell_{C}}\dots(\texttt{*})^{\ell_{C}}\langle
C_{n}\rangle(\texttt{*})^{\ell_{C}}\langle\texttt{*}\rangle^{\ell}$

where the number of * at the end is to make the length of the whole string is
exactly $WH$.

###  5.2 Chain implies Matching

Suppose that there is a chain that satisfies the program $\mathcal{P}$ above.
Each block gadget forced cubes to form $h$ segments; all of these must be
horizontal because otherwise, the length is too large:

$H=nh+(n+1)g=n(20000n^{2})+(n+1)(200n)<30000n^{3}=m.$

It can be checked that

  * •

$H=nh+(n+1)g=nh+(n+1)(200n)<nh+500n^{2}=nh+\frac{h}{40}$ and

  * •

$W=mt+4g=mt+800n<mt+30000n^{3}<m(t+1)$.

Moreover, straight paths in the same block must be in $h$ consecutive
horizontal rows because the end of one segment must be next to the beginning
of the other. Therefore, by Lemma 4.1, there exists a matching for
$(a_{i})_{i=1}^{n}$, $(b_{i})_{i=1}^{n}$, and $(c_{i})_{i=1}^{n}$.

###  5.3 Matching implies Chain

Now we show that if there exists a matching in the instance of Numerical 3DM,
i.e., permutations $\sigma$ and $\pi$ such that
$a_{i}+b_{\sigma(i)}+c_{\pi(i)}=t$ for all $i$, then we can construct a chain
that satisfies the program.

First, we note that a chain occupying a $h\times ma_{i}$ block can be made to
satisfy the block gadget $\langle A_{i}\rangle$, as shown in Figure 2(a).
Represent $\langle A_{i}\rangle$ with that chain, and similarly, represent
$\langle B_{i}\rangle$ and $\langle C_{i}\rangle$ with $h\times mb_{i}$ block
and $h\times mc_{i}$ block. We then place those blocks similar to Figure 2(b):
divide the box into $n$ parts horizontally and putting block $\langle
A_{i}\rangle$, $\langle B_{\sigma(i)}\rangle$, and $\langle C_{\pi(i)}\rangle$
on the $i$-th part. We also leave gaps exactly $g$ between any two adjacent
blocks. Notice that since $a_{i}+b_{\sigma(i)}+c_{\pi(i)}=t$ for all $i$, the
block placement allows leaving every gap exactly $g$.

Then, we will apply the wire lemma to turn a string of *’s into a subchain
connecting all these blocks. Divide the whole box into $2\times 2$ grid of
cubes, and consider each $2\times 2$ grid as a $1\times 1$ square. The gaps
between blocks have width of $g/2=100n$ squares, and the width of the grid
equals $w_{A}=W/2$ squares for wires among $(\langle A_{i}\rangle)_{i=1}^{n}$.

For wires among $A_{i}$ blocks, Lemma 4.4 implies that there exists a sequence
of $\ell_{A}=8nw_{A}=4nW$ squares of size $2\times 2$ that connects $A_{i}$
and $A_{i+1}$ for each $i$. Moreover, a subchain of cubes following a program
of $16nW$ * can fill the space regardless of the direction of how squares of
size $2\times 2$ connect by filling each $2\times 2$ subgrid as shown in
Figure 8(a) for straight squares, Figure 8(b), and Figure 8(c) for both
directions of a turn.

For $B_{i}$ and $C_{i}$ blocks, we can set $w_{X}$ in the lemma to be
$w_{B}=w_{A}/2$ and $w_{C}=w_{A}/4$, respectively due to the constraints
$a_{i}\in(0.5t,0.6t)$, $b_{i}\in(0.25t,0.3t)$, and $c_{i}\in(0.125t,0.15t)$
for all $i$. Thus, the wires between $B_{i}$ and $C_{i}$ blocks can be set to
be $\ell_{B}=\ell_{A}/2$ and $\ell_{C}=\ell_{A}/4$, respectively, and be
placed in the same way as wires between $A_{i}$ do.

For the wire between $A_{n}$ and $B_{1}$, they should be long enough to
connect

  * •

The last cubes of $A_{n}$ to the square $m_{n}$ for $A_{i}$ blocks in the
notation of Lemma 4.4. This accounts for $\ell_{A}/2$ cubes.

  * •

The square $m_{n}$ for $A_{i}$ blocks to the square $m_{0}$ for $B_{i}$
blocks. This accounts for at most $4W$ cubes.

  * •

The square $m_{0}$ for $B_{i}$ blocks to the first tile in the $B_{1}$ block.
This accounts for $\ell_{B}/2$ cubes.

This uses $\ell_{A}/2+\ell_{B}/2+4W<\ell_{A}$ cubes. The extra length of cubes
the space may be adjusted at the bottom space below the reserved space of
$A_{i}$ blocks, whose area is at least $(g/2)(W/2)=gW/4>\ell_{A}$ cubes. Thus,
it is possible to do so. Also, the wire between $B_{n}$ and $C_{1}$ can be
placed similarly. This concludes that all blocks can be connected by wires,
and there is a space of one $2\times 2$ square between wires in arbitrary
arrangement.

asy/subgrid_wildcard_s.asy

(a) Filling “straight” squares with wildcard

asy/subgrid_wildcard_t1.asy

(b) Filling “turn” squares with wildcard, starting from the inner corner

asy/subgrid_wildcard_t2.asy

(c) Filling “turn” squares with wildcard, starting from the outer corner

Figure 8: Filling a $2\times 2$ square with * cubes.

Lastly, we need to justify that the remaining space after placing all the
wires and blocks can be completely filled. Notice that the construction we
described so far is aligned with the $2\times 2$ polygrid, and it is connected
because the blocks and wires are topologically equivalent to a path. Each
piece is at least one cell apart from the others, so it cannot form a closed
loop anywhere. By Lemma 4.6, there exists a Hamiltonian cycle that passes all
the remaining squares. Thus, a string of only * with length equal to the
number of empty squares can be placed along the cycle and thus covers all the
remaining space.

###  5.4 Proof for Packing

In this section, we will give an outline of a proof of Theorem 5.2. The idea
is mostly the same as 5.1, but not allowing wildcards makes the proof
different in a few places.

#### Setup.

Given an instance of Numerical 3DM $a_{1},\dots,a_{n}$, $b_{1},\dots,b_{n}$,
$c_{1},\dots,c_{n}$ with target sum $t$, we set up the exact same parameters
$g$, $h$, $H$, $W$, $m$ as in Section 5.1. The parameters $\ell_{A}$,
$\ell_{B}$, and $\ell_{C}$ are changed to the following to address the modulo
$4$ issue, which is discussed at the end of this subsection:

$\ell_{A}=16nW+2,\qquad\ell_{B}=8nW+2,\quad\text{and}\quad\ell_{C}=4nW+2.$

The block gadgets are also exactly the same. However, since we are not allowed
to use *, we need to change our program to

$\displaystyle\mathcal{P}={}$ $\displaystyle\langle
A_{1}\rangle(\texttt{T})^{\ell_{A}}\langle
A_{2}\rangle(\texttt{T})^{\ell_{A}}\dots(\texttt{T})^{\ell_{A}}\langle
A_{n}\rangle(\texttt{T})^{\ell_{A}}$ $\displaystyle\langle
B_{1}\rangle(\texttt{T})^{\ell_{B}}\langle
B_{2}\rangle(\texttt{T})^{\ell_{B}}\dots(\texttt{T})^{\ell_{B}}\langle
B_{n}\rangle(\texttt{T})^{\ell_{B}}$ $\displaystyle\langle
C_{1}\rangle(\texttt{T})^{\ell_{C}}\langle
C_{2}\rangle(\texttt{T})^{\ell_{C}}\dots(\texttt{T})^{\ell_{C}}\langle
C_{n}\rangle(\texttt{T})^{\ell_{C}},$

where all * are changed to T and the $\langle\texttt{*}\rangle^{\ell}$ at the
end is removed.

#### Chain $\boldsymbol{\Rightarrow}$ Matching.

This part is exactly the same as Section 5.2 since it only uses block gadget.

#### Matching $\boldsymbol{\Rightarrow}$ Path Chain.

If there is a solution to an instance of Numerical 3DM, we will construct a
chain satisfying $\mathcal{P}$. To that end, we use the exact same setup as
Section 5.3 by arranging the blocks according to the solution of Numerical 3DM
as in Figure 2(b). Like Section 5.3, we divide the grid into $2\times 2$
subgrids and ensure that all blocks fit within the subgrid. However, the major
difference here is that we don’t have the wildcard, so we need to wire every
block using only “Turn” cubes. To fix this, we use the patterns in Figure 9 to
fill it. Observe that only using patterns in Figure 9(b) and Figure 9(c) will
make the average number of cubes per square strictly less than $4$, so the
total number of cubes in a wire would be less than the specified wire length.
Thus, we need to change patterns used at some turns from Figures 9(b) and 9(c)
to 9(d) and 9(e), respectively. This can adjust the number of cubes by $4$ at
a time. Moreover, observe that using only patterns in Figure 9(d) and Figure
9(e) makes the average number of cubes per square strictly greater than $4$.
This guarantees that the number of cubes used can be adjusted to be off by
less than $4$ cubes from the exact length.

asy/subgrid_pack_s.asy

(a) Packing “straight” $2\times 2$ squares with turn cubes

asy/subgrid_pack_t1.asy

(b) Packing “turn” $2\times 2$ squares with turn cubes, starting from the
inner corner

asy/subgrid_pack_t2.asy

(c) Packing “turn” $2\times 2$ squares with turn cubes, starting from the
outer corner

asy/subgrid_pack_t3.asy

(d) Adjustment to the pattern in 9(b)

asy/subgrid_pack_t4.asy

(e) Adjustment to the pattern in 9(c)

Figure 9: Packing cubes in the wire aligned in $2\times 2$ subgrids

Finally, we need to argue that length adjustment by a multiple of $4$ (as in
Figure 9) is sufficient to get the exact length. To do that, we color each
cube $(x,y)$ by the residues $(x\bmod 2,y\bmod 2)$. It can be shown that if
the path uses the “Turn” instruction only, it will cycle through the four
colors in a periodic fashion, making the number of cubes used invariant modulo
$4$. Specifically, this number must be $2$ modulo $4$ because the width of the
block is always even, forcing the wires to connect two cubes (namely, the
cubes at the bottom left corner of one block and the top left corner of the
other) with the same parity of $x$-coordinate but different parity of
$y$-coordinate, and it is not hard to see that there exists a wire with length
of $2$ modulo $4$ that follows “Turn” instruction only and connects two such
cubes (ignoring crossing). Hence, all the wires with this property must have
length $2$ modulo $4$, and length adjustments by multiples of $4$ are enough
to adjust the length of the wire to any target.

Note that we did not require filling the remaining space.

##  6 Snake Cube Puzzles in $\boldsymbol{2\times H\times W}$ box

In this section, $2\times H\times W$ Snake Cube is NP-complete with a
reduction from Numerical 3-dimensional matching.

######  Theorem 6.1.

$2\times H\times W$ Snake Cube is NP-hard, and therefore, NP-complete.

The rest of this section is devoted to proving Theorem 6.1.

###  6.1 Reduction Overview

We follow the block and wire reduction infrastructure introduced in Section 3
and used in Section 5.

Given an instance of Numerical 3DM $a_{1},\dots,a_{n}$, $b_{1},\dots,b_{n}$,
$c_{1},\dots,c_{n}$ with target sum $t$, and assuming the condition of
Proposition 2.8 that $a_{i}\in(0.5t,0.6t)$, $b_{i}\in(0.25t,0.3t)$, and
$c_{i}\in(0.125t,0.15t)$ for all $i$, we set the following parameters to
construct the input program of $2\times H\times W$ Snake Cube.

$\begin{array}[]{rclrcl}g=&\text{gap width}&=1200n,&H=&\text{height of the
box}&=n(h+6g+4)+2,\\\\[2.0pt] h=&\text{height of
blocks}&=60000n^{2},&W=&\text{width of the box}&=4g+mt+6,\\\\[2.0pt]
m=&\text{multiplier of widths}&=70000n^{3},&\ell_{A}=&\text{length of the
wires}&=96nW,\\\\[2.0pt] \ell_{B}=&\text{length of the
wires}&=48nW,&\ell_{C}=&\text{length of the wires}&=24nW.\end{array}$

In three dimensions, each block gadgets $\langle A_{i}\rangle$, $\langle
B_{i}\rangle$, and $\langle C_{i}\rangle$ will correspond to block of size
$2\times h\times ma_{i}$, $2\times h\times mb_{i}$, and $2\times h\times
mc_{i}$. A second layer in the third dimension provides us the freedom to fill
(not just pack) the space using a long sequence of T’s, which we were unable
to accomplish in 2D. However, the second layer also brings a major obstacle to
constructing block gadgets. The naive block gadgets similar to Section 5 could
inadvertently swap between layers anytime, causing an unequal distribution of
rows corresponding $a_{i}$, $b_{i}$, and $c_{i}$ between layers that causes
Lemma 4.1 to fail. To get around this issue, we will introduce a new gadget
called a shelf. A shelf is a well-chosen set of instructions that divides the
box into $n$ regions, each of height roughly $h$. The shelf will effectively
constrain how and where these blocks fold so that each block will have height
approximately $h$ in each layer. The exact description will be provided in
Section 6.2.

Here, we provide an overview of the construction. We start our program with a
sequence of instructions, denoted $\langle\text{shelf}\rangle$, that forces
the construction of the _shelf_ , which will be provided in Section 6.2. As
described in Section 3, the core of the program will consist of block gadgets

$\displaystyle\langle A_{i}\rangle$
$\displaystyle=(\texttt{S})^{ma_{i}-1}(\texttt{TT}(\texttt{S})^{ma_{i}-2})^{2h-1}\texttt{S},$
$\displaystyle\langle B_{i}\rangle$
$\displaystyle=(\texttt{S})^{mb_{i}-1}(\texttt{TT}(\texttt{S})^{mb_{i}-2})^{2h-1}\texttt{S},$
$\displaystyle\langle C_{i}\rangle$
$\displaystyle=(\texttt{S})^{mc_{i}-1}(\texttt{TT}(\texttt{S})^{mc_{i}-2})^{2h-1}\texttt{S}.$

Block $\langle A_{i}\rangle$, $\langle B_{i}\rangle$, and $\langle
C_{i}\rangle$ are expected to be represented by a chain that occupies blocks
of size $2\times h\times ma_{i}$, $2\times h\times mb_{i}$, and $2\times
h\times mc_{i}$ respectively, as shown in Figure 10.

asy/2xmxn_block.asy

Figure 10: Illustration of chain satisfying block gadget $\langle
A_{i}\rangle$ in $2\times H\times W$ Snake Cube. The colors red and blue
represent different layers of cubes.

The wiring gadget consists of a long sequence of T’s. Lastly, we end with a
long sequence of turns $(\texttt{T})^{\ell}$ that provides just enough cubes
to fill the remaining space if the instance Numerical 3DM is solvable.

The program is then the following.

$\displaystyle\mathcal{P}=\langle\text{shelf}\rangle$ $\displaystyle\langle
A_{1}\rangle(\texttt{T})^{\ell_{A}}\langle
A_{2}\rangle(\texttt{T})^{\ell_{A}}\dots(\texttt{T})^{\ell_{A}}\langle
A_{n}\rangle(\texttt{T})^{\ell_{A}}$ $\displaystyle\quad\langle
B_{1}\rangle(\texttt{T})^{\ell_{B}}\langle
B_{2}\rangle(\texttt{T})^{\ell_{B}}\dots(\texttt{T})^{\ell_{B}}\langle
B_{n}\rangle(\texttt{T})^{\ell_{B}}$ $\displaystyle\quad\langle
C_{1}\rangle(\texttt{T})^{\ell_{C}}\langle
C_{2}\rangle(\texttt{T})^{\ell_{C}}\dots(\texttt{T})^{\ell_{C}}\langle
C_{n}\rangle(\texttt{T})^{\ell_{C}}(\texttt{T})^{\ell},$

where $\ell$ is such that the entire length of the program is $2HW$.

###  6.2 “Shelf” Construction

We begin by specifying the set of instructions that will force the formulation
of a shelf with $n$ rows, shown below.

asy/shelf_top.asy

(a) Top layer of the “shelf” construction

asy/shelf_bottom.asy

(b) Bottom layer of the “shelf” construction

Figure 11: The “shelf” configuration highlighted in 6.2. Whenever there is a
discontinuity, the chain moves to the other layer.

We first trace out the blue _frame_ of the shelf (shown in Figure 11)
traversing from the starting point labeled “Start” to $P_{1}$ in the top
layer, $P_{1}$ to $P_{2}$ in the bottom layer, and finishing the border in the
top layer.

$\langle\text{outer
frame}\rangle=\texttt{SSSST}\texttt{S}^{H-2}\texttt{T}\texttt{S}^{W-2}\texttt{TT}\texttt{S}^{W-2}\texttt{T}\texttt{S}^{H-2}\texttt{T}\texttt{S}^{W-2}\texttt{TT}\texttt{S}^{W-6}.$

We now trace out the black frame $n$ shelves by following the path in black.
Each shelf can be traced with the instructions

$\langle\text{top shelf frame}\rangle=\texttt{
T}\texttt{S}^{h+6g}\texttt{T}\texttt{S}^{W-g-6}\texttt{TSST}\texttt{S}^{W-g-6}.$

We repeat this $n$ times to trace out the shelves in the top layer. At point
$P_{3}$, we switch to the bottom layer and trace the $n$ shelves for the
bottom layer as well. The tracing instructions for the bottom layer is the
reverse of the top one:

$\langle\text{bottom shelf
frame}\rangle=(\texttt{S})^{W-g-6}\texttt{TSST}\texttt{S}^{W-g-6}\texttt{T}\texttt{S}^{h+6g}\texttt{T}.$

Then, the entire structure of the frame is

$\langle\text{shelf frame}\rangle=\langle\text{outer
frame}\rangle\left(\langle\text{top shelf
frame}\rangle\right)^{n}\texttt{TT}\left(\langle\text{bottom shelf
frame}\rangle\right)^{n-1}(\texttt{S})^{W-g-6}\texttt{TSST}\texttt{S}^{W-g-6}\texttt{T}\texttt{S}^{h-2},$

where the ending instructions trace out the last shelf in the bottom layer.
This completes the frame of the shelf. It is not hard to see the construction
of the frame is unique. (Notably, whenever there is a continuous sequence of
$\Theta(W)$ straights, the corresponding cubes must be aligned in a line along
the length of the box, constraining the orientation and placement of all cubes
along the frame to the unique representation.)

We now fill the inside of the shelf (shown in gray in Figure 11). If we follow
the instructions above with $\texttt{TSST}\texttt{S}^{H-5}$, the chain must
turn into the shelf as there is no other way to place the straight line of
$H-4$ cubes otherwise. Now, observe that there is only one exit to the inside
of the shelf construction. If the snake cube box is to be filled, then the
inside of the shelf must be completely filled before the chain of cubes exits
the shelf; the exact filling instructions is not important. One possible way
is to start filling the bottom layer, move up, and then fill the top layer.

$\displaystyle\langle{\text{bottom filling}}\rangle$
$\displaystyle\quad=\texttt{TSST}(\texttt{S})^{H-5}\texttt{TSSTT}(\texttt{S})^{W-g-6}\texttt{TT}(\texttt{S})^{W-g-5}\texttt{TTT}(\texttt{S})^{H-7}\texttt{TT}(\texttt{S})^{H-9}\texttt{TT}\left((\texttt{S})^{h+6g+1}\texttt{T}(\texttt{S})^{W-g-6}\texttt{TT}(\texttt{S})^{W-g-6}\texttt{TS}\right)^{n-1}\texttt{S},$
$\displaystyle\langle{\text{top filling}}\rangle$
$\displaystyle\quad=\left(\texttt{
ST}\texttt{S}^{W-g-6}\texttt{TT}\texttt{S}^{W-g-6}\texttt{T}\texttt{S}^{h+6g+1}\right)^{n-1}\texttt{TT}\texttt{S}^{H-9}\texttt{TT}\texttt{S}^{H-7}\texttt{TTT}\texttt{S}^{W-g-5}\texttt{TT}\texttt{S}^{W-g-6}\texttt{TTSST}\texttt{S}^{H-5}\texttt{TSSTTSS}.$

The above instructions can form the gray subchain shown in Figure 11. The
final construction of the shelf is then

$\langle\text{shelf}\rangle=\langle\text{shelf frame}\rangle\langle\text{top
filling}\rangle\texttt{TT}\langle\text{bottom filling}\rangle\texttt{TTSSSS}.$

###  6.3 Chain implies Matching

We now show that a solution to $2\times H\times W$ Snake Cube implies a
matching for Numerical 3DM. This time, we do not need Lemma 4.1 because the
shelf already significantly constrained the construction. We simply argue
directly.

Let $X_{i}$ denote either $A_{i}$, $B_{i}$, or $C_{i}$. Since $m>H$, each of
the long straight sequences of length $mx_{i}-2$ in $\langle X_{i}\rangle$
must form a continuous segment of $mx_{i}$ cubes lying in the horizontal
direction. Additionally, since $m>g$, all cubes within a $\langle
X_{i}\rangle$ block gadget must lie entirely within one row of the shelf.

As a result, all of $2h$ segments of length $mx_{i}$ in each block must
entirely lie in the volume $2\times(h+6g)\times(W-6)$ of one row of the shelf.
We claim that each row of shelf must contain exactly one $A_{i}$, $B_{i}$, and
$C_{i}$ block. To see this, observe that it is impossible to have two $A_{i}$
blocks in the same row of the shelf; otherwise, if $A_{i}$ and $A_{j}$ lie in
the same row of the shelf, there are $2\cdot 2h$ segments of length at least
$m\min\\{a_{i},a_{j}\\}\geq 0.5m(t+1)>W/2$. Since $4h>2(h+6g)$, there must be
two segments in the same row. Their combined length is at least
$2m\min\\{a_{i},a_{j}\\}>W$, yielding a contradiction. Thus, each row must
contain exactly one $A_{i}$ block. Assuming this result, we can also show that
each row must contain exactly one $B_{i}$ block and one $C_{i}$ block as
desired.

Now consider each $X_{i}$ block as $2h$ straight segment of size $1\times
mx_{i}$. We claim that in a row of the shelf that contains block $A_{i}$,
$B_{j}$, and $C_{k}$ there exists a $1\times 1\times(W-6)$ row that contains
three segments of lengths $ma_{i}$, $mb_{j}$, and $mc_{k}$. To prove that this
row exists, we can use a similar argument to Lemma 4.1. Define
$n_{A},n_{B},n_{C},n_{\text{good}}$ as same as in the proof of Lemma 4.1 but
counting only rows in between shelf we are considering (but summing across
both layers), which has size $2\times(h+6g)\times(W-6)$. Thus,
$n_{A}+n_{B}+n_{C}+n_{\text{good}}=2(h+6g)$. However, by counting the number
of A-segments, B-segments, and C-segments, we get, respectively, that

$\displaystyle n_{A}$ $\displaystyle=2(h+6g)-2h=12g$ $\displaystyle 2h\leq
3n_{A}+n_{C}+n_{\text{good}}\implies n_{B}$ $\displaystyle\leq
2n_{A}+2(h+6g)-2h\leq 36g$ $\displaystyle 2h\leq
7n_{A}+3n_{B}+n_{\text{good}}\implies n_{C}$ $\displaystyle\leq
6n_{A}+2n_{B}+2(h+6g)-2h=156g$

Since $2(h+6g)>12g+36g+156g$ for all $n>1$, there must be at least one good
row as desired.

Consider the row that contains all segments of length $ma_{i}$, $mb_{j}$, and
$mc_{k}$, we must have

$\displaystyle ma_{i}+mb_{j}+mc_{k}$ $\displaystyle\leq W=mt+4g+6<m(t+1),$
$\displaystyle a_{i}+b_{j}+c_{k}$ $\displaystyle\leq t.$

Summing the inequality above over all rows, we get
$nt=\sum_{i}a_{i}+\sum_{j}b_{j}+\sum_{k}c_{k}\leq nt$, so therefore the
equality $a_{i}+b_{j}+c_{k}=t$ must hold for all rows of the shelf. This
implies a path filling necessarily implies the existence of matching.

###  6.4 Matching implies Chain

Now we show that if there exists a matching in Numerical 3DM, i.e.,
permutations $\sigma$ and $\pi$ such that $a_{i}+b_{\sigma(i)}+c_{\pi(i)}=t$
for all $i$, then we can construct a chain that satisfies the program.

First, we note that a chain occupying a $2\times h\times ma_{i}$ block can be
made to satisfy the block gadget $\langle A_{i}\rangle$. Note that we will
need the starting and ending points to be on different rows, which can be done
by letting the chain alternate between the top and bottom layers every two
rows, as shown in Figure 10. Represent $\langle A_{i}\rangle$ with that chain,
and similarly, represent $\langle B_{i}\rangle$ and $\langle C_{i}\rangle$
with $2\times h\times mb_{i}$ block and $2\times h\times mc_{i}$ block. We
then place those blocks similar to Figure 2(b): divide the box into $n$ parts
horizontally and putting block $\langle A_{i}\rangle$, $\langle
B_{\sigma(i)}\rangle$, and $\langle C_{\pi(i)}\rangle$ on the $i$-th part. We
also leave gaps of exactly $g$ between any two adjacent blocks and gaps of
$3g$ between each block and the shelf. Notice that since
$a_{i}+b_{\sigma(i)}+c_{\pi(i)}=t$ for all $i$, the block placement allows for
leaving gaps of exactly $g$ between adjacent blocks.

To connect blocks together, we observe the following property of traversing
with a long sequence of turns in 3-dimensional space.

######  Lemma 6.2 ($2\times 2\times 2$ Traversal).

Given the instructions $(\texttt{T})^{8}$ and a $2\times 2\times 2$ cube, if
the subchain following these instructions enters the cube from one face, it
may exit the cube from any other face.

###### Proof.

This result is shown in Abel et. al.’s paper [ADD+13]. We include the images
from their paper in Figure 12 to provide a visual proof of our claim above.

Figure 12: All possible configurations of a subchain entering from one face
and exiting through another face, as shown in [ADD+13, Figure 6,7].

∎

Since $h$ and $m$ are multiples of $4$, the remaining unfilled space in the
box can be partitioned into $2\times 4\times 4$ blocks of space. From here on,
we view the remaining space as a smaller 2D grid where each cell corresponds
to a $2\times 2\times 2$ cube in the original box. The unfilled space in the
box is then a connected $2\times 2$ polygrid. Traversing between $2\times
2\times 2$ blocks of space with $(\texttt{T})^{8}$’s gives the same movement
freedom as traversing between cells in a 2D grid given a wildcard. Therefore,
the remaining proof closely follows that in Section 5. However, the shelf
poses an obstacle, and wires must detour around the shelf.

We define $W^{*}=\frac{W}{2}$, $g^{*}=g/2=600n$,
$\ell_{A}^{*}=\ell_{A}/8=24nW^{*}$, $\ell_{B}^{*}=\ell_{B}/8=12nW^{*}$, and
$\ell_{C}^{*}=\ell_{C}/8=6nW^{*}$ which are the equivalent quantities of $W$,
$g$, $\ell_{A}$, $\ell_{B}$, and $\ell_{C}$ in the new $1\times 0.5H\times
0.5W$ box. By Lemma 4.4, it is possible to connect each of the $\langle
X_{i}\rangle$ blocks in order while ensuring the remaining space is continuous
$2\times 2$ polygrid, if we, as in Section 5, allow the wires to be two cells
thick. Note these constants are $\frac{3}{2}$ times those in Section 5 because
the wires must detour around the shelf, as mentioned briefly in Lemma 4.4. (To
detour around the shelf, each wire will have an additional $4nw_{X}$ length in
the notation of Lemma 4.4 because each wire has to detour around at most $n$
shelf frame, each for $2$ times. Each time, the wire has to detour with length
at most $2w_{X}$. This sums up to $2n(2w_{X})=4nw_{X}$ as desired.)

Moreover, when all the wires detour around the same shelf, wires need to stack
into more layers, requiring wider gaps. Note that there are $3n$ wires in
total, and each wire contributes to at most $4$ layers around each shelf (each
wire is split into $U_{i}$ and $V_{i}$, both need to travel up and drop down).
We need to leave a square between each layer of wires, the stack of wires can
fit in the gap of width $2(2\cdot(3n\cdot 4))=48n<g^{*}$. (Note that a square
means $2\times 2$ polygrid in the equivalent 2D grid.) This justifies that the
extra gap of width $3g$ on each shelf and the gap of width $g$ on the right of
the box is sufficient.

asy/shelf_detour.asy

Figure 13: Wires detour around the shelf

All that is left is to fill the remaining space. Since the remaining space is
$2\times 2$ polygrid (or a $2\times 4\times 4$ polygrid when viewed in three
dimensions), we can fill it by Lemma 4.6.

Therefore, there exists a matching Numerical 3DM if and only if there exists a
solution to snake cube $2\times H\times W$ Snake Cube. Since our reduction
takes polynomial time, $2\times H\times W$ Snake Cube is NP-hard.

##  7 Snake Cube Puzzles with Hexagonal Prisms

In this section, we consider a version of a 2D Snake cube with a chain of
hexagonal prisms. From now on, we represent each prism by points. Two prisms
are adjacent if and only if the points corresponding to them are adjacent in
the triangular lattice. Thus, the problem becomes a triangular grid variant of
the flattening fixed-angle chains problem in [DILU22].

An infinite triangular grid is a two-dimensional lattice generated by vectors
$v_{1}=\left(\begin{smallmatrix}1\\\ 0\end{smallmatrix}\right)$ and
$v_{2}=\left(\begin{smallmatrix}\cos 60^{\circ}\\\ \sin
60^{\circ}\end{smallmatrix}\right)$; each point represents a hexagonal prism.
Two points in a triangular grid are adjacent if they are distance $1$ apart. A
$\boldsymbol{60^{\circ}}$ parallelogram box of dimension $H\times W$ is the
set of $HW$ points obtained by translating the set
$\\{iv_{1}+jv_{2}:i\in\\{1,\dots,W\\},j\in\\{1,\dots,H\\}\\}$ by some lattice
vector.

For this section, a program is a string that consists of only characters S,
$\texttt{T}_{60}$, and $\texttt{T}_{120}$, where S denotes straights,
$\texttt{T}_{60}$ denotes $60^{\circ}$ turns (forming $120^{\circ}$ angle),
and $\texttt{T}_{120}$ denotes $120^{\circ}$ turns (forming $60^{\circ}$
angle). We say that a chain $C=(p_{1},p_{2},\dots,p_{\lvert s\rvert})$ (length
$\lvert s\rvert$) satisfies $s$ if and only if for every
$i\in\\{2,3,\dots,\lvert s\rvert-1\\}$, the angle between $p_{i-1}$, $p_{i}$,
$p_{i+1}$ is $180^{\circ}$ if $s_{i}=\texttt{S}$, $60^{\circ}$ if
$s_{i}=\texttt{T}_{120}$, and $120^{\circ}$ if $s_{i}=\texttt{T}_{60}$. $C$ is
closed if and only if $p_{1}=p_{|s|}$.

We will consider two versions of this problem.

  * •

Triangular Closed Chain: given an program $\mathcal{P}$, decide there is a
closed chain that satisfies the program $\mathcal{P}$.

  * •

Bounded Triangular Path Packing: given a $60^{\circ}$ parallelogram box $B$,
an program $\mathcal{P}$, and two adjacent vertices $u$ and $v$ on a boundary
of $B$, decide whether there is a chain from $u$ to $v$ that satisfies program
$s$.

In particular, the Triangular Closed Chain version is the triangular analog of
the flattening problem in [DILU22]. We will prove the following.

######  Theorem 7.1.

Both Triangular Closed Chain and Bounded Triangular Path Packing are NP-
complete.

Clearly, these two problems are in NP with certificates being the sequence of
points in the chain. The rest of this section is devoted to proving that these
two problems are NP-hard. In particular, Section 7.1, 7.2, and 7.3 will show
that Bounded Triangular Path Packing is NP-hard by using a similar reduction
from Numerical 3DM following the same outline in Section 3, except that
everything will be sheared to align with the parallelogram. Then, in Sections
7.4, we will show how to convert Bounded Triangular Path Packing to Triangular
Closed Chain by introducing a new gadget called a frame.

######  Remark 7.2.

With the same proof, we can show that the problem of “given a $60^{\circ}$
parallelogram box $B$ and a program $\mathcal{P}$, decide whether there is a
chain of points in $B$ satisfying instruction $\mathcal{P}$” is NP-Complete.
We omit the proof for this version.

###  7.1 Setup and the Block Gadget

The reduction will be very similar to the one outlined in Section 3. However,
we will shear everything to align with the parallelogram. In particular, when
we talk about the width and the height of the grid, we mean the length
parallel to the sides of $B$.

Same as before, we fix an instance of $3$-partition $a_{1},\dots,a_{n}$,
$b_{1},\dots,b_{n}$, $c_{1},\dots,c_{n}$ with target sum $t$. Assume the
condition of Proposition 2.8 that $a_{i}\in(0.5t,0.6t)$,
$b_{i}\in(0.25t,0.3t)$, and $c_{i}\in(0.125t,0.15t)$ for all $i$.

We set the following parameters.

$\begin{array}[]{rclrcl}g=&\text{gap width}&=300n,&H=&\text{height of the
box}&=nh+(n+1)g,\\\\[2.0pt] h=&\text{height of
blocks}&=60000n^{3},&W=&\text{width of the grid}&=mt+4g,\\\\[2.0pt]
m=&\text{multiplier of widths}&=90000n^{3},&\ell_{A}=&\text{length of the
wires}&=32nW/3,\\\\[2.0pt] \ell_{B}=&\text{length of the
wires}&=16nW/3,&\ell_{C}=&\text{length of the wires}&=8nW/3.\end{array}$

We take an $H\times W$ parallelogram box depicted in Figure 14. First, we have
the following strings of block gadgets for all $i=1,2,\dots,n$

$\displaystyle\langle A_{i}\rangle$
$\displaystyle=(\texttt{S})^{ma_{i}-1}\texttt{T}_{120}\texttt{T}_{60}\,(\texttt{S})^{ma_{i}-2}\left(\texttt{T}_{60}\texttt{T}_{120}\,(\texttt{S})^{ma_{i}-2}\,\texttt{T}_{120}\texttt{T}_{60}\,(\texttt{S})^{ma_{i}-2}\right)^{h/2-1}\texttt{S},$
$\displaystyle\langle B_{i}\rangle$
$\displaystyle=(\texttt{S})^{mb_{i}-1}\texttt{T}_{120}\texttt{T}_{60}\,(\texttt{S})^{mb_{i}-2}\left(\texttt{T}_{60}\texttt{T}_{120}\,(\texttt{S})^{mb_{i}-2}\,\texttt{T}_{120}\texttt{T}_{60}\,(\texttt{S})^{mb_{i}-2}\right)^{h/2-1}\texttt{S},$
$\displaystyle\langle C_{i}\rangle$
$\displaystyle=(\texttt{S})^{mc_{i}-1}\texttt{T}_{120}\texttt{T}_{60}\,(\texttt{S})^{mc_{i}-2}\left(\texttt{T}_{60}\texttt{T}_{120}\,(\texttt{S})^{mc_{i}-2}\,\texttt{T}_{120}\texttt{T}_{60}\,(\texttt{S})^{mc_{i}-2}\right)^{h/2-1}\texttt{S},$

which folds into a parallelogram block as depicted in Figure 14.

The program we will use is

$\displaystyle\mathcal{P}={}$ $\displaystyle\langle
A_{1}\rangle\,(\texttt{T}_{60})^{\ell_{A}}\,\langle
A_{2}\rangle\,(\texttt{T}_{60})^{\ell_{A}}\dots(\texttt{T}_{60})^{\ell_{A}}\,\langle
A_{n}\rangle\,(\texttt{T}_{60})^{\ell_{A}}$ $\displaystyle\langle
B_{1}\rangle\,(\texttt{T}_{60})^{\ell_{B}}\,\langle
B_{2}\rangle\,(\texttt{T}_{60})^{\ell_{B}}\dots(\texttt{T}_{60})^{\ell_{B}}\,\langle
B_{n}\rangle\,(\texttt{T}_{60})^{\ell_{B}}$ $\displaystyle\langle
C_{1}\rangle\,(\texttt{T}_{60})^{\ell_{C}}\,\langle
C_{2}\rangle\,(\texttt{T}_{60})^{\ell_{C}}\dots(\texttt{T}_{60})^{\ell_{C}}\,\langle
C_{n}\rangle\,(\texttt{T}_{60})^{\ell_{C}}.$

###  7.2 Chain implies Matching

Suppose that there is a chain that satisfies program $\mathcal{P}$ above.
Observe that the block gadget must form $h$ straight segments of length
$ma_{i}$, $mb_{i}$, or $mc_{i}$. All of these straight segments must be
horizontal with respect to the longer sides; otherwise, placing any of the
segments in $60^{\circ}$ or $120^{\circ}$ to the longer sides will make the
segments exceed the boundary because

$H=nh+(n+1)g=n(60000n^{2})+(n+1)(200n)<90000n^{3}=m.$

It can be checked that

  * •

$H=nh+(n+1)g=nh+(n+1)(600n)<nh+1500n^{2}=nh+\frac{h}{40}$

  * •

$W=mt+4g=mt+2400n<mt+90000n^{3}<m(t+1)$.

Moreover, straight paths in the same block must be in $h$ consecutive
horizontal rows because the end of one segment must be next to the beginning
of the other. Therefore, applying Lemma 4.1, there is a solution to Numerical
3DM for $(a_{i})_{i=1}^{n}$, $(b_{i})_{i=1}^{n}$, and $(c_{i})_{i=1}^{n}$.

asy/triangular_setup.asy

Figure 14: An example of the bounding box and a block gadget. The gray dots
represent prisms in the triangular grid.

###  7.3 Matching implies Chain

Numerical 3DM, i.e., permutations $\sigma$ and $\pi$ such that
$a_{i}+b_{\sigma(i)}+c_{\pi(i)}=t$ for all $i$, then we can construct a chain
that satisfies the program.

First, we note that a chain occupying a $h\times ma_{i}$ parallelogram block
can be made to satisfy the block gadget $\langle A_{i}\rangle$, shown in
Figure 14. Represent $\langle A_{i}\rangle$ with that chain, and similarly,
represent $\langle B_{i}\rangle$ and $\langle C_{i}\rangle$ with $h\times
mb_{i}$ parallelogram block and $h\times mc_{i}$ parallelogram block. We then
place those blocks similar to Figure 2(b), but sheared by $60^{\circ}$: divide
the box into $n$ parts horizontally and putting block $\langle A_{i}\rangle$,
$\langle B_{\sigma(i)}\rangle$, and $\langle C_{\pi(i)}\rangle$ on the $i$-th
part. We also leave gaps exactly $g$ between any two adjacent blocks. Notice
that since $a_{i}+b_{\sigma(i)}+c_{\pi(i)}=3t$ for all $i$, the block
placement allows leaving every gap exactly $g$.

Now, we need to connect between blocks using a sequence of
$\texttt{T}_{60}$’s. First, in the triangular grid, we embed the hexagonal
grid as shown in Figure 15(a).

asy/triangular_grid_1.asy

(a) Embedding hexagonal grid inside triangular grid

asy/triangular_grid_2.asy

(b) Embedding parallelogram grid (the circled dots) and an example of wire
path

Figure 15: Wiring the blocks together

In the hexagonal grid (Figure 15(a)), it is easy to see that one can move
between two adjacent (distance $\sqrt{3}$ unit apart) black vertices by
traveling through solid edges only. Since all angles between solid edges are
$120^{\circ}$, traveling through solid edges uses only a sequence of
$\texttt{T}_{60}$’s.

Next, we embed a parallelogram grid inside the grid of black vertices as shown
in Figure 15(b). This is a $3\times 3$-refinement of the original
parallelogram grid. Thus, we may now apply the wire lemma (Lemma 4.4) on the
entire figure scaled down by $3$. In particular, to connect the $\langle
A_{i}\rangle$ blocks, we use parameters $g^{\prime}=g/3=100n$, $w_{A}=W/3$,
and travel between two adjacent squares correspond to four movements in the
triangular grids, giving $\ell_{A}=4(8nw_{A})=32nW/3$ tiles. Blocks $\langle
B_{i}\rangle$’s and $\langle C_{i}\rangle$’s can be connected similarly with
wire lengths divided by two and by four respectively. Finally, we transform
the sequence from the embedded grid to the original triangular grid
accordingly; an example of a wire path is shown in Figure 15(b). This implies
that there is the desired path.

###  7.4 Reduction from Closed Chain to Bounded Path

To turn Bounded Triangular Path Packing to Triangular Closed Chain, we need a
new structure called a frame, which is a structure that confines the rest of
the construction into a bounded parallelogram, making the reduction similar to
previous subsections work. This construction is similar to the frame gadget in
[DILU22], but we need to do a parity in modulo a much larger prime since
triangular grids have more possibilities for angles of each edge.

The reduction goes as follows. Suppose that $\mathcal{P}$ is the instance of
Bounded Triangular Packing. Then, we first blow up $\mathcal{P}$ by $101$
times by replacing

$\texttt{S}\text{ with
}\underbrace{\texttt{SSS}\dots\texttt{S}}_{101},\qquad\texttt{T}_{60}\text{
with
}\underbrace{\texttt{SSS}\dots\texttt{S}}_{100}\texttt{T}_{60},\quad\text{ and
}\quad\texttt{T}_{120}\text{ with
}\underbrace{\texttt{SSS}\dots\texttt{S}}_{100}\texttt{T}_{120}.$

This gives a new program $101\mathcal{P}$ that will constrain a chain in the
bounding box $101B$ and will connect two vertices $101u$ and $101v$ on the
boundary of $101B$ that has distance $101$ apart. We now append this with the
frame program $F$, defined to be folded as in Figure 16.

asy/triangular_frame.asy

Figure 16: The Frame Gadget

We now claim that the concatenation of $101\mathcal{P}$ and $F$ is a valid
reduction to Triangular Closed Chain. To prove this, we first show that the
frame works as expected.

######  Claim 7.3.

Any chain satisfying program $F$ must look like 16 up to global rotation and
reflection.

###### Proof.

We first note that the vertices in each line segment must be connected by the
“straight” instruction, so it must be a long line segment. There are six
segments whose length is not $0\pmod{101}$, lengths $1$, $2$, $3$, $7$, $15$,
$22$, and we need to group them into three groups (corresponding to three
possible orientations of the segment) and assign a $+$ or $-$ sign for each
segment so that the sum turns out to be equal. An exhaustive check reveals
that the only way to do so in modulo $101$ is $\\{-1,-2,3\\}$,
$\\{-7,-15,22\\}$, and $\emptyset$. This forces all segments to be at one of
the two angles; without loss of generality, let them be as shown in Figure 16.
Moreover, the $22\pmod{101}$ segment must have opposite orientation from the
$7$ and $15\pmod{101}$ segment, and the $3\pmod{101}$ segment must have
opposite orientation from the $1$ and $2\pmod{101}$ segment. This suffices to
force the construction of the outer frame.

For the inner frame, note that the $0\pmod{101}$ segment right after the
segment of length $1$ must be forced to be that angle (otherwise, it collides
with the outer frame), and this subsequently forces all other segments up to
the point $101v$. The construction up to point $101u$ is then forced because
there is only one possible angle for the path to leave $101u$ avoiding a
collision. Hence, the entire frame is forced. ∎

Finally, it suffices to prove the following.

######  Claim 7.4.

Let $\mathcal{P}^{\prime}$ be the concatenation of the blown-up string
$101\mathcal{P}$ and the frame construction $F$. Then, there is a closed chain
satisfying $\mathcal{P}^{\prime}$ if and only if there is a chain inside $B$
that goes from $u$ to $v$ satisfying $\mathcal{P}$.

###### Proof.

For the direction $(\Rightarrow)$, if there is a closed chain satisfying
$\mathcal{P}^{\prime}$, note that by Claim 7.3, $F$ must be folded into the
structure shown in the figure above. Since $101\mathcal{P}$ can travel between
points with coordinates $0\pmod{101}$, $101\mathcal{P}$ must travel inside the
bounding box $101B$. Hence, $\mathcal{P}$ must travel inside the bounding box
$B$.

For the direction $(\Leftarrow)$, if $\mathcal{P}$ travels inside bounding box
$B$ from $u$ to $v$, then $101\mathcal{P}$ must travel inside $101B$ from
$101u$ to $101v$. The frame construction as shown in Figure 16 then connects
$101v$ back to $101u$, forming a closed chain. ∎

This establishes the NP-hardness of Triangular Closed Chain.

##  8 Weak NP-Hardness of Filling a Rectangular Grid

In this section, we consider 2D Snake Cube, where the chain must fill a
$1\times H\times W$ rectangle. However, we allow the instructions to be
encoded using the shorthand notation, which keeps the inputs polynomial with
respect to the input integers. Since this modification means the problem may
no longer be in NP, this reduction only proves NP-hardness. For any set $S$,
let $\sum S$ be the sum of its elements.

Let $A$ be the multiset of positive integers, a 2-Partition instance. We
select $H=2|A|+4$ and $W=4\sum A+1$. The program comprises the caps at either
end and $|A|$ layers in between, encoding each $a_{i}$ in $A$ sequentially.
The swivel points join each gadget and allow the layers to flip horizontally.
The orientation of each layer left or right corresponds to assigning each
$a_{i}$ to either partition (Figure 17).

[width=0.55]asy/weak2D_overall.asy

Figure 17: Chain for $A=\\{1,2,1\\}$, emphasizing the different gadgets,
highlighting the swivel points (in magenta), and demonstrating the 3 variants
of layers.

###  8.1 Gadgets

The starting cap is the subsequence (the ending cap being the reverse):

$\displaystyle(\texttt{S})^{\frac{W-1}{2}-1}\texttt{TT}(\texttt{S})^{W-2}\texttt{TT}(\texttt{S})^{\frac{W+1}{2}-1}\texttt{T}\ldots$

Since $W>H$, the $W$-segments in the caps can only fit horizontally, forcing
the orientation of the entire chain. To avoid creating unfillable empty space,
the other segments in the cap must be on the same side of the $W$-segments
because the $W$-segments obstruct any other part of the chain from filling it
(Figure 18(a)). This forces the $W$-segments to be at the top and bottom, and
this in turn forces the swivel points joining the caps and the layers to be
both horizontally centered and vertically one square from the boundaries,
regardless of either horizontal reflection of the caps (Figure 18(b)).

[width=]asy/weak2D_incorrectcap.asy

(a) An arrangement that creates unfillable space (red, crossed) regardless of
the rest of the chain (gray)

[width=]asy/weak2D_correctcap.asy

(b) Intended folding allowing the rest of the chain (gray) to fill the
remaining space.

Figure 18: Forced arrangement of cap segments.

For each $a_{i}$, let $A_{i}=\\{a_{1},a_{2},\dots,a_{i}\\}$,
$w_{i}=4\sum(A\setminus A_{i-1})+1$, $x_{i}=(w_{i}-1)/2$, and $h_{i}=2\lvert
A\setminus A_{i-1}\rvert$. There are 3 variants of the corresponding layer
gadget. For ease of discussion, sections of the gadget are named ( Figure 19).

  * •

Variant 1: If $4a_{i}\leq x_{i}$ and $h_{i}>2$, then the layer is the
subsequence:

$\displaystyle\ldots\texttt{T}(\texttt{S})^{x_{i}-1}\texttt{T}$ “arm”
$\displaystyle(\texttt{S})^{h_{i}-2}(\texttt{T}\texttt{T}(\texttt{S})^{h_{i}-3})^{4a_{i}-1}\texttt{T}$
“padding”
$\displaystyle(\texttt{S})^{x_{i}-4a_{i}+1}(\texttt{T})^{2(2a_{i}-1)}$ “shift”
$\displaystyle(\texttt{S})^{x_{i}-2a_{i}}\texttt{T}\texttt{T}(\texttt{S})^{x_{i}-2a_{i}-1}\texttt{T}\ldots$
“return”

The “arm” can be though of as shifting the chain to a corner of the remaining
space. Similarly, the “padding” fills up $4a_{i}$ units of horizontal space,
the “shift” fills space to shift the swivel axis, and the “return” properly
positions the next swivel point in the middle of the remaining space.

  * •

Variant 2: If $4a_{i}>x_{i}$ and $h_{i}>2$, informally the padding can be
visualized as spilling over into the shift, resulting in these differences:

$\displaystyle(\texttt{S})^{{h_{i}}-2}(\texttt{T}\texttt{T}(\texttt{S})^{{h_{i}}-3})^{x_{i}}(\texttt{T}\texttt{T}(\texttt{S})^{{h_{i}}-2})^{4a_{i}-x_{i}-1}\texttt{T}$
“padding” $\displaystyle(\texttt{T})^{2(2a_{i}-1-(4a_{i}-x_{i}-1))}$ “shift”

  * •

Variant 3: If $h_{i}=2$, informally the padding can be visualized as subsuming
the shift entirely, resulting in these changes from the first variant:

$\displaystyle\texttt{T}(\texttt{S})^{x_{i}}(\texttt{T})^{2(2a_{i}-1)}$
“padding” TS “return”

[width=]asy/weak2D_layer_variant1.asy

[width=]asy/weak2D_layer_variant2.asy

[width=]asy/weak2D_layer_variant3.asy

[width=]asy/weak2D_layer_key.asy

Figure 19: Layer gadget mechanics. Top left shows an example of Variant 1, top
right shows Variant 2, and bottom left shows Variant 3. For all examples,
$w_{i}=17$. For the example for Variant 1, $a_{i}=1,h_{i}=6$; for Variant 2,
$a_{i}=3,h_{i}=6$; for Variant 3, $a_{i}=4,h_{i}=2$.

Each layer gadget has a $w_{i}\times h_{i}$ rectangular space available to it
and leaves behind a $w_{i+1}\times h_{i+1}$ rectangular space, while
displacing the next swivel point horizontally by $2a_{i}$ left or right and
vertically up by $2$ relative to the previous swivel point, thus keeping the
swivel point horizontally centered at the bottom of each space (Figure 19).
The horizontal reflection of this gadget also must have these properties. To
show this, we use induction starting from the first layer. Note that the arm
and padding sections are all forced by space constraints. The shift section is
forced since turning the chain outward at any point in the subsequence of
repeated turns (T) would leave behind a $1\times 1$ space (Figure 20), which
can only be filled by the endpoints of the chain since once filled, the chain
cannot continue onwards. However, the position of the endpoints is forced by
the cap gadgets and cannot fill this space for any of the layer gadgets. Then,
the return section is also forced by space constraints.

[width=]asy/weak2D_layershift1.asy

[width=]asy/weak2D_layershift2.asy

Figure 20: Arrangements of the shift section that leave behind unfillable
space.

###  8.2 Reduction

If there exists a solution to 2-Partition, then construct all the gadgets and
flip the layer gadgets so that arms for all numbers in $A_{1}$ point to the
left, and those for numbers in $A_{2}$ point to the right. The horizontal
displacements of the swivel points must sum to $0$, so the last layer can
connect to the upper cap.

If there exists a solution for 2D Snake Cube, then we have demonstrated the
gadgets are forced to be constructed in the correct orientation. Since the
last layer gadget connects to the upper cap gadget, the horizontal
displacements of the swivel points must sum to $0$. Reverse the above process
to obtain a solution to the 2-Partition instance.

## Acknowledgements

This work was conducted during open problem-solving in the MIT class on
Algorithmic Lower Bounds: Fun with Hardness Proofs (6.5440) in Fall 2023. We
thank the other participants in the class—particularly Papon Lapate, Benson
Lin Zhan Li, and Kevin Zhao—for related discussions and for providing an
inspiring atmosphere.

## References

  * [AD11] Zachary Abel and Erik D. Demaine.  Edge-unfolding orthogonal polyhedra is strongly NP-complete.  In Proceedings of the 23rd Annual Canadian Conference on Computational Geometry (CCCG 2011), 2011.
  * [ADD+13] Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B. Schardl.  Finding a Hamiltonian path in a cube with specified turns is hard.  Journal of Information Processing, 21(3):368–377, 2013.
  * [CDBG11] Kenneth C. Cheung, Erik D. Demaine, Jonathan R. Bachrach, and Saul Griffith.  Programmable assembly with universally foldable strings (moteins).  IEEE Transactions on Robotics, 27(4):718–729, 2011.
  * [DE11] Erik D. Demaine and Sarah Eisenstat.  Flattening fixed-angle chains is strongly NP-hard.  In Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 2011), pages 314–325, August 15–17 2011.
  * [DILU22] Erik D. Demaine, Hiro Ito, Jayson Lynch, and Ryuhei Uehara.  Computational complexity of flattening fixed-angle orthogonal chains.  arXiv:2212.12450, 2022.  https://arXiv.org/abs/2212.12450. Preliminary version in CCCG 2022\.
  * [GJ90] Michael R. Garey and David S. Johnson.  Computers and Intractability; A Guide to the Theory of NP-Completeness.  W. H. Freeman & Co., USA, 1990.