Solving the Rubik’s Cube optimally is NP-complete
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 firs...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121410 |