  In this paper, we prove that optimally solving an $n \times n \times n$
Rubik's Cube is NP-complete by reducing from the Hamiltonian Cycle problem in
square grid graphs. This improves the previous result that optimally solving an
$n \times n \times n$ Rubik's Cube with missing stickers is NP-complete. We
prove this result first for the simpler case of the Rubik's Square---an $n
\times n \times 1$ generalization of the Rubik's Cube---and then proceed with a
similar but more complicated proof for the Rubik's Cube case.
