Die-rolling Hamiltonian cycles

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.


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