Paper by Erik D. Demaine
- Reference:
- Erik D. Demaine, Sarah Eisenstat, and Mikhail Rudoy, “Solving the Rubik's Cube Optimally is NP-complete”, in Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France, February 28–March 3, 2018.
- Abstract:
-
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. Our results hold both when the goal is make
the sides monochromatic and when the goal is to put each sticker into a
specific location.
- Comments:
- The full version of this paper is available as arXiv:1706.06708.
- Length:
- The paper is 13 pages.
- Availability:
- The paper is available in PDF (658k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Rubik_ESA2011 (Algorithms for Solving Rubik's Cubes)
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated November 27, 2024 by
Erik Demaine.