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 http://cs.smith.edu/~orourke/MathOverflow/DiceRolling.jpg
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.