8
$\begingroup$

Let $C_n$ be a cubical $n \times n \times n$ subset of the integer lattice, so consisting of $n^3$ vertices. I am interested in special Hamiltonian cycles in $C_n$, special in the sense that (a) each edge of the cycle has unit length, and (b) no two adjacent edges are collinear---the path turns $90^\circ$ at every vertex. Call these orthogonal Hamiltonian cycles. For $C_2$, this is straightforward:


        HamCube

I believe that $C_3$ has no orthogonal Hamiltonian cycle. However, I don't have a clean proof, just an unconvincing exhaustive case analysis.

Q1. Prove (or disprove) that $C_3$ has no orthogonal Hamiltonian cycle.

For $C_4$, the below shows an orthogonal Hamiltonian cycle (colored on the right to reveal its structure). This is known as a Moore curve, a space-filling curve.


Ham444

The next level Moore curve, however, has collinear edges, as do Hilbert curves.

Q2. For which $n$ does $C_n$ have an orthogonal Hamiltonian cycle?

It is natural to hope that $8$ copies of the $C_4$ solution could be stitched $(2 \times 2 \times 2)$-together to form an ortho-Ham cycle for $C_8$, but I couldn't see my way through the complications.

$\endgroup$
6
  • 3
    $\begingroup$ chess coloring proves that for odd $n$ there is no Hamiltonian cycle in $C_n$ (orthogonal or not) $\endgroup$ May 4, 2021 at 13:45
  • $\begingroup$ @FedorPetrov: Nice! Thanks. That settles Q1. $\endgroup$ May 4, 2021 at 14:27
  • $\begingroup$ It seems that 4 vertices are not visited in $C_4$, looking near two of the yellow sticks (or I need to change my glasses). $\endgroup$ May 4, 2021 at 20:26
  • $\begingroup$ Ah, but this is easily fixed by adding edges. $\endgroup$ May 4, 2021 at 20:34
  • 1
    $\begingroup$ You could try small instances with a SAT solver. The standard reduction of Hamiltonian cycle to SAT has variables $x_{ij}$ encoding "the $i$th element of the cycle is vertex $j$", and appropriate constraints. It would seem straightforward to add constraints to enforce orthogonality, namely, after given two vertices you cannot next visit the third vertice that would continue the straight line. $\endgroup$ May 5, 2021 at 6:25

2 Answers 2

5
$\begingroup$

Partial answer: It is possible for $C_n$ if $n$ is a power of two.

$C_2$ and $C_4$ are shown in the question. For larger $n$ the idea is to take a three-dimensional Moore curve (a recursive construction of a Hamiltonian circuit), and fix any straight-edge trouble locally.

By "recursive" I mean the construction breaks the cube into 8 subcubes, recursively, until the smallest cubest are $C_2$.

The key part is the "local fixing". Take a 3D Moore curve on $C_n$ (with $n=2^k$). Look at each of its $C_2$ subcubes. Each such subcube is entered at one corner, and exited at another corner, in some direction. If the path in the subcube turns properly (both immediately after entering, and also immediately before exiting), we are happy with that subcube. Otherwise, we rotate the path in the subcube so that it turns properly. This is a local fix that does not affect any other parts of the Hamiltonian circuit, and fixes any straight-edge trouble associated with that subcube. Do it for all offending subcubes and you are done.

The only remaining question is whether we can always perform such rotations. In fact we can (see below).

Examples

First, a Hamiltonian circuit on $C_8$ before and after fixing. On the left, red edges are defects (consecutive straight edges).

Hamiltonian circuits on C8

Then the same on $C_{16}$. Of course it is impossible to verify its correctness from the picture, but you get the idea, and the red edges again show the defects, which are fixed on the right.

Hamiltonian circuits on C16

Details: Recursive construction

First we need a 3D Moore curve (allowing straight-edge defects for the moment). From Wikipedia we learn that you just take eight smaller 3-dimensional Hilbert curves, "rotate them and connect them by line segments". Let's do that carefully. One way to actually do it is with 3-dimensional turtle graphics. We use the following primitives:

  • F = forward move one step
  • L = left turn
  • R = right turn
  • U = upward turn ("pitch" if you think of airplane movement)
  • D = downward turn
  • C = clockwise roll (again, think of an airplane rolling to the right, with nose direction not changing)
  • A = anticlockwise roll

Then define some auxiliary terms.

$R(2)$ is a "right-handed" Hamiltonian path on $C_2$. If you place the cube in front of you, you enter the front lower left corner, with your head up. You visit the 8 vertices, and when you exit, you are facing the opposite direction. This can be done with moves UFDFDFRFRFDFDFU.

$L(2)$ is the mirror image of the previous: You enter the cube at its front lower right corner. The moves are UFDFDFLFLFDFDFU.

$R(n)$ is a generic version where you enter a big cube ($n=2^k$ with $n\ge 4$) from the front lower left corner, facing forwards, and exit at front lower right corner, facing back. It is defined as 'C2RF 1LF L1F C2RF R2F A1LF L1F R2A', spaces are just filler for easier reading. If you plug in $R(2)$ for all occurrences of "1", and $L(2)$ for all occurrences of "2", you get a "right-handed" Hamiltonian path on $C_4$. Note that it is not a Hamiltonian circuit since entrance (left corner) and exit (right corner) are far apart.

$L(n)$ is the corresponding generic left-handed Hamiltonian path. The moves are 'A1LF 2RF R2F A1LF L1F C2RF R2F L1C'.

One more: $C(n)$ is a Hamiltonian circuit on a big cube ($C_n$). Its moves are '1LF A1LF L1F 1CRF RA1F 1LF L1F CL1 F'.

Now, for example, you get a circuit on $C_{16}$ by taking the string of $C(n)$, and plugging in $R(8)$ for each occurrence of "1", and $L(8)$ for each occurence of "2".

That gives you a Hamiltonian circuit, but it may have defects.

Fixing the defects

Actually, this is the easier part, but there are a few cases to consider. In the 3D Moore curve, as constructed above, each $C_2$ has the same kind of Hamiltonian path, in some orientation: It contains two parallel "U" curves, joined by an edge. Consider the three cases in this figure. Blue edges show the path inside our cube. Green edges are the entering and exiting edges from an adjacent cube. The magenta dashed line is not part of the path, but it is useful for illustration: it connects the entrance vertex and the exit vertex, and we call it the rod.

Three cases of defects, with fixes

  1. Top left: Both green edges are collinear with the adjoining blue edges. Both defects are fixed by mirroring our curve (top right).
  2. Middle left: Only one of the green edges is collinear with its blue edge. The other green is collinear with the rod. Again we mirror the curve (middle right).
  3. Bottom left: Only one of the green edges is collinear with its blue edge. The other green is orthogonal to its blue and to the rod. This is problematic: mirroring does not help. Here we replace our curve with a different Hamiltonian path on the $C_2$ (bottom right).

These cases cover all possible defects, so all defects are locally fixed.

In fact, given the kind of 3D Moore curve described previously, it seems that we never even encounter case 3, at least not up to $C_{256}$, so it seems the mirroring operation is enough! But I did not prove this, so I'm leaving case 3 there "just in case".

The $C_6$ case

Update: $C_6$ is also possible. We use the following six primitives, each implementing a Hamiltonian path in a $(2 \times 2 \times 3)$ box (big dot indicates entrance). Arranging nine of them suitably, we can fill a $(6 \times 6 \times 3)$ box; this is the top half of our solution. The bottom half is its mirror image.

Six 223 primitives

Hamiltonian circuit on C6

$\endgroup$
4
  • $\begingroup$ Beautiful! Exactly my hope, that such a recursive structure was possible. $\endgroup$ May 8, 2021 at 23:42
  • $\begingroup$ This kind of construction won't work for 6*6*6, because if you divide it into 3*3*3 small $C_2$ cubes, you cannot visit each cube once and come back, by the chess coloring argument that Fedor mentioned. So the 6*6*6 case is open; if it is possible, you'll at least need to split some of the $C_2$ cubes, with the parts visited separately. $\endgroup$ May 9, 2021 at 7:06
  • $\begingroup$ Even though the general question is open, starting with $6 \times 6 \times 6$, your recursive $2^n$ construction is a nice advance. $\endgroup$ May 9, 2021 at 12:50
  • 1
    $\begingroup$ The $C_6$ solution seems regular enough that one might be able to extend the construction to larger even cubes. At least the primitives can be easily extended in the vertical direction. Also the horizontal arrangement of the primitives would need to be extended (so as to build a larger cube), it might work but I haven't checked the details. $\endgroup$ May 10, 2021 at 21:54
8
$\begingroup$

In the recent book "Bicycle or Unicycle?" by Velleman and Wagon, this is problem #16 "Wiggle Room." (Actually, there it's generalized to computing the maximum length path, with a Hamiltonian path in the next-best case, and the best case being a Hamiltonian cycle.) It's known that there is a Hamiltonian cycle for all even $n$, and a nice parity argument that there isn't even a path for $n=3$, and evidence for conjecture that there is a path (but not necessarily a cycle) for all $n\geq 4$.

$\endgroup$
6
  • 1
    $\begingroup$ Ah, I didn't know about this book---Thanks! AMS link. I'm having difficulty reconciling "there is a Hamiltonian cycle for all even $n$" with "evidence for conjecture that there is a path (but not necessarily a cycle) for all $n \ge 4$." Could you clarify please? $\endgroup$ May 12, 2021 at 16:43
  • $\begingroup$ A Hamiltonian PATH (as opposed to circuit = cycle) need not come back where it started, it just visits all vertices. The chess coloring argument does not prevent such paths. $\endgroup$ May 12, 2021 at 17:39
  • $\begingroup$ For $n=3$ one can prove that a path traversing the cube completely must contain at least 2 straight edges. The argument is to label the positions: $V,E,F,C$ (vertex, edge, face, center). Then a path is a walk on the graph $V-E-F-C$, and if there is no straight edge then some patterns like $VEV$ are excluded. Considering the number of $V,E,F,C$ positions ($8,12,6,1$), one quickly reaches a contradiction. $\endgroup$ May 12, 2021 at 18:39
  • $\begingroup$ Joseph, I think it is about the odd cases. There might be a path, although there cannot be a cycle (by the parity argument). $\endgroup$ May 12, 2021 at 18:43
  • 1
    $\begingroup$ The book that possiblywrong mentioned is a gem. Besides the conjecture that "Hamiltonian snakes" (Hamiltonian paths that always turn) exist for all $C_n$ cubes with $n \ge 4$, it also tells that for $C_5$ and $C_7$ such snakes are known (and given in the book), "discovered by Rob Pratt and Stan Wagon using a computer search based on integer-linear programming". $\endgroup$ May 13, 2021 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.