Die-rolling Hamiltonian cycles

2012-02-03T14:07:55Z

Let $R$ be a rectangular region of the integer lattice $\mathbb{Z}^2$, each of whose unit squares is labeled with a number in $\lbrace 1, 2, 3, 4, 5, 6 \rbrace$. Say that such a labeled $R$ is die-rolling Hamiltonian, or simply rollable, if there is a Hamiltonian cycle obtained by rolling a unit die cube over its edges so that, for each square $s \in R$, the cube lands on $s$ precisely once, and when it does so, the top face of the cube matches the number in $s$. For example, the $4 \times 4$ "board" shown below is rollable.

Q. Is it true that, if $R$ is die-rolling Hamiltonian, then the Hamiltonian cycle is unique, i.e., there are never two distinct die-rolling Hamiltonian cycles on $R$?

This "unique-rollability" question arose out of a problem I posed in 2005, and was largely solved two years later, in a paper entitled, "On rolling cube puzzles" (complete citation below; the $4 \times 4$ example above is from Fig. 17 of that paper). Although the original question involved computational complexity, the possible uniqueness of Hamiltonian cycles is independent of those computational issues, so I thought it might be useful to expose it to a different community, who might bring different tools to bear. It is known to hold for $R$ with side lengths at most 8. If not every cell of $R$ is labeled, and unlabeled cells are forbidden to the die, then there are examples with more than one Hamiltonian cycle.

Edit1. Rolling a regular tetrahedron on the equilateral triangular (hexagonal) lattice is not as interesting. See the Trigg article cited below.

Edit2. Serendipitously, gordon-royle posted a perhaps(?) relevantly related question: "Uniquely Hamiltonian graphs with minimum degree 4."

The computational version is Open Problem 68 at The Open Problems Project.
"On rolling cube puzzles." Buchin, Buchin, Demaine, Demaine, El-Khechen, Fekete, Knauer, Schulz, Taslakian. Proceedings of the 19th Canadian Conference on Computational Geometry, Pages 141–144, 2007. PDF link to full paper.
Charles W. Trigg. "Tetrahedron rolled onto a plane." J. Recreational Mathematics, 3(2):82–87, 1970.

Answer by domotorp for Die-rolling Hamiltonian cycles

2012-02-25T16:08:54Z

UPDATE: I played around and came up with a construction (chance of containing a mistake is high!), below it I leave my original answer for explanation.

$\begin{array}{ccccccccccccccccccccccccc} 3&-&2& &2&-&1&-&5&-&6& &5&-&1&-&2&-&6&-&5&-&1&-&2\cr |& &|& &|& & & & & &|& &|& & & & & & & & & & & &|\cr 1& &1& &3& &4&-&5&-&3& &4& &1&-&4&-&6&-&3&-&1&-&4\cr |& &|& &|& &|& & & & & &|& &|& & & & & & & & & & \cr 4& &5& &5& &1&-&5&-&6&-&2& &5&-&4&-&2&-&3&-&5&-&4\cr |& &|& &|& & & & & & & & & & & & & & & & & & & &|\cr 6& &6&-&4& &6&-&3&-&1&-&4&-&6&-&3&-&1&-&4&-&6& &6\cr |& & & & & &|& & & & & & & & & & & & & & & &|& &|\cr 3& &2&-&4&-&5& &4&-&2& &5&-&6&-&2& &2&-&4& &5& &3\cr |& &|& & & & & &|& &|& &|& & & &|& &|& &|& &|& &|\cr 1& &1& &1&-&5&-&6& &6& &3&-&6& &3&-&1& &1& &1& &1\cr |& &|& &|& & & & & &|& & & &|& & & & & &|& &|& &|\cr 4& &5& &3& &2&-&3& &5&-&3&-&2& &3&-&5& &3& &2& &4\cr |& &|& &|& &|& &|& & & & & & & &|& &|& &|& &|& &|\cr 6& &6& &6& &6& &6&-&5&-&1&-&2&-&6& &6& &6& &6& &6\cr |& &|& &|& &|& & & & & & & & & & & &|& &|& &|& &|\cr 3&-&2&-&4&-&5&-&3&-&2&-&4&-&5&-&3&-&2&-&4&-&5&-&3\cr |& & & & & & & &|& & & & & & & &|& & & & & & & &|\cr 1&-&2&-&6&-&5&-&1&-&2&-&6&-&5&-&1&-&2&-&6&-&5&-&1\cr |& &|& &|& &|& & & & & & & & & & & &|& &|& &|& &|\cr 4& &4& &4& &4& &4&-&5&-&3&-&2&-&4& &4& &4& &4& &4\cr |& &|& &|& &|& &|& & & & & & & &|& &|& &|& &|& &|\cr 6& &5& &1& &2&-&1& &5&-&1&-&2& &1&-&5& &1& &2& &6\cr |& &|& &|& & & & & &|& & & &|& & & & & &|& &|& &|\cr 3& &3& &3&-&5&-&4& &4& &1&-&4& &1&-&3& &3& &3& &3\cr |& &|& & & & & &|& &|& &|& & & &|& &|& &|& &|& &|\cr 1& &2&-&6&-&5& &6&-&2& &5&-&4&-&2& &2&-&6& &5& &1\cr |& & & & & &|& & & & & & & & & & & & & & & &|& &|\cr 4& &4&-&6& &4&-&1&-&3&-&6&-&4&-&1&-&3&-&6&-&4& &4\cr |& &|& &|& & & & & & & & & & & & & & & & & & & &|\cr 6& &5& &4& &3&-&5&-&4&-&2& &5&-&6&-&2&-&1&-&5&-&6\cr |& &|& &|& &|& & & & & &|& &|& & & & & & & & & & \cr 3& &3& &1& &6&-&5&-&1& &6& &3&-&6&-&4&-&1&-&3&-&6\cr |& &|& &|& & & & & &|& &|& & & & & & & & & & & &|\cr 1&-&2& &2&-&3&-&5&-&4& &5&-&3&-&2&-&4&-&5&-&3&-&2 \end{array}$

HOW THIS THING WORKS:

I think there are configurations that are not uniquely Hamiltonian. The example I have in mind should be around 14 times 14, except that I do not have a definite example, but I hope I can convince you that only a technical difficulty is missing.

Our goal is to prove a somewhat stronger statement, to exhibit an R that has two different die-rolling H-cycles in which the cube is in the same position over every field no matter which H-cycle you take. This allows us to define a nice graph on R. First we will give one H-cycle, then add the edges not contained in this H-cycle along which the cube could move, only allowing moves that take the cube into the same position over the field as it would have in the H-cycle. Denote the obtained graph by G. It is easy to see that G is a subgraph of the grid-graph, moreover, G cannot have cycles whose length is less than 10 and G has (at least) two H-cycles.

One such graph is given below on the 13 times 10 grid (130 vertices). Legend: X marks the squares contained in both H-cycles, while 1 and resp. 2 the squares contained in only one of them.

$\begin{array}{ccccccccccccc} %
X&X&X&X&X&X&X&X&X&X&X&X&X\cr X& & & & & & & & & & & &X\cr X& &X&X&X&X&X&X&X&X&X& &X\cr X& &X& & & & & & & &X& &X\cr 1&1&1&1&X&X&X&X&X&2&2&2&2\cr X& &X& & & & & & & &X& &X\cr X& &X&X&X&X&X&X&X&X&X& &X\cr X& & & & & & & & & & & &X\cr X&X&X&X&X&X&X&X&X&X&X&X&X\ \end{array} $

Unfortunately this graph is not yet good enough, we cannot give a good numbering of R to make the edges valid. However, we can play around (i.e. make more wiggly using more area) with the top and bottom parts (shared by both H-cycles) and I am sure that way we can ensure the validity of all edges. This is the only missing part which seems to be only technical.

Die-rolling Hamiltonian cycles - MathOverflow

Die-rolling Hamiltonian cycles

Answer by domotorp for Die-rolling Hamiltonian cycles