**Next:** Problem 69: Isoceles Planar Graph Drawing

**Previous:** Problem 67: Fair Partitioning of Convex Polygons

- Statement
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?

- Origin
Version posed by O’Rourke at the 2005

*Canadian Conference on Computational Geometry*[DO06], and subsequently substantially developed and embellished in [BBD+07].- Status/Conjectures
Open.

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

- Partial and Related Results
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.- Appearances
[DO06]; see above.

- Categories
combinatorial geometry

- Entry Revision History
J. O’Rourke, 17 Jul 2007; 2 Feb 2012.

- [BBD+07]
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.- [DO06]
Erik D. Demaine and Joseph O’Rourke. Open problems from CCCG 2005. In

*Proc. 18th Canad. Conf. Comput. Geom.*, pages 75–80, 2006.- [vD04]
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.