# Die-rolling Hamiltonian cycles

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 download.
• Charles W. Trigg. "Tetrahedron rolled onto a plane." J. Recreational Mathematics, 3(2):82–87, 1970.
• Your template is of a left-handed die, while your rollable board is for a right-handed die, and cannot be rolled with a lefty die. – Michael Biro Feb 3 '12 at 15:00
• Sharp eye, Michael!. Just replaced the Latin-cross unfolding with right-handed die. Thanks! – Joseph O'Rourke Feb 3 '12 at 15:36
• Oh, I see. My original template needed to be folded toward the viewer; the new one away from the viewer, which is more natural. – Joseph O'Rourke Feb 3 '12 at 16:12
• Wouldn't problem 68 in TOPP need an update? Marzio's paper seems to settle the question. – domotorp Mar 18 '19 at 21:44
• @domotorp: Good point. Will attend to that when time permits. – Joseph O'Rourke Mar 19 '19 at 11:00

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.

• Wow!! $\mbox{}$ – Joseph O'Rourke Feb 26 '12 at 19:36
• Page 17 of the cited paper says, "It remains open whether nonuniqueness of Hamiltonian cycles holds for fully labeled boards." If your example holds up, you have settled that question---Congrats! – Joseph O'Rourke Feb 26 '12 at 19:55
• this is really an amazing answer – alberto.bosia Feb 27 '12 at 4:02

While browsing the recreational-mathematics tag I noticed this old question again.

In 2012 I published on my blog a draft paper in which I give another example of a (bigger) board with two distinct Hamiltonian cycles (but domotorp was quicker to answer).

In the paper I also prove that the Rolling Cube Puzzle in labeled boards without free cells and with blocked cells is NP-complete (an open problem).

http://www.nearly42.org/cstheory/rolling-a-cube-can-be-tricky/

... I never had the time to clean it up and submit it to a journal for a serious review (though I tested the gadgets with Mathematica).

If someone wants to give it a look ...