Next: Problem 69: Isoceles Planar Graph Drawing
Previous: Problem 67: Fair Partitioning of Convex Polygons
Label the faces of a unit cube with numbers 1–6 as in a die. Place the cube to sit on an integer lattice grid, with one corner at the origin and sides aligned with the axes. Completely label every lattice square of a rectangular “board” R, whose corner is at the origin, with numbers in \{1,2,3,4,5,6\}. The problem is to roll the cube over its edges so that, for each square s \in B labeled l, the cube lands on s precisely once, and when it does so, the top face of the cube has label l.
What is the computational complexity of solving an instance of this problem?
Version posed by O’Rourke at the 2005 Canadian Conference on Computational Geometry [DO06], and subsequently substantially developed and embellished in [BBD+07].
Open.
This problem was inspired by van Deventer’s “Rolling block mazes” [vD04]. The paper [BBD+07] uncovered a rich history to rolling cube puzzles going back to the 1960’s, which will not be repeated here.
The original posed problem labeled an arbitrary connected set S of squares, rather than a rectangular board R; the cells outside of S are free, and may be visited any number of times with any number on the die top. That former problem is solved in [BBD+07], which establishes that, as conjectured, the problem is NP-complete.
The posed problem has no free cells, and in fact the labels are all in a rectangular board R. This seems the most interesting specific variant, for it is left possible in [BBD+07] that, if there is a solution for R, it is “uniquely rollable.” They establish that there are boards with labeled and blocked (i.e., forbidden) cells for which rollable Hamiltonian cycles are not unique, but they leave open fully labeled boards. The uniquely-rollable conjecture is settled for all boards with side lengths at most 8.
[DO06]; see above.
combinatorial geometry
J. O’Rourke, 17 Jul 2007; 2 Feb 2012.
Kevin Buchin, Maike Buchin, Erik D. Demaine, Martin L. Demaine, Dania El-Khechen, Sandor Fekete, Christian Knauer, André Schulz, and Perouz Taslakian. On rolling cube puzzles. In Proc. 19th Canad. Conf. Comput. Geom., pages 141–148, 2007.
Erik D. Demaine and Joseph O’Rourke. Open problems from CCCG 2005. In Proc. 18th Canad. Conf. Comput. Geom., pages 75–80, 2006.
M. Oskar van Deventer. Rolling block mazes. In Barry Cipra, Erik D. Demaine, Martin L. Demaine, and Tom Rodgers, editors, A Tribute to a Mathemagician, pages 241–250. A K Peters, November 2004.