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