Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.
      Dice Rolling

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.
share|improve this question
2  
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
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
    
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
1  
this is really an amazing answer –  alberto.bosia Feb 27 '12 at 4:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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