An amateur proof that the rolling cube puzzle is NP-complete.

**Abstract**

We settle two open problems related to the rolling cube puzzle: Hamil-

tonian cycles are not unique even in fully labeled boards and rolling

cube puzzle is NP-complete in labeled boards without free cells and with

blocked cells.

click here to download the paper

NOTE: another example of two distinct Hamiltonian cycles in a fully labeled board has also been found by Pálvölgyi Dömötör (see this post on mathoverflow).