2017/06/21 by Erik D. Demaine, Sarah Eisenstat, Mikhail Rudoy · 1 voice · 3 citations
Computer Science · #Algorithms and Data Compression #Embedded Systems Design Techniques #Parallel Computing and Optimization Techniques
paper · pdf · doi:10.4230/lipics.stacs.2018.24
In this paper, we prove that optimally solving an n × n × 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 × n × 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 × n × 1 generalization of the Rubik's Cube---and then proceed with a similar but more complicated proof for the Rubik's Cube case.