2026-07-21T21:09:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8533 2024-03-06T10:42:18Z ddc:004 open_access

Solving the Rubik's Cube Optimally is NP-complete Demaine, Erik D. Eisenstat, Sarah Rudoy, Mikhail combinatorial puzzles NP-hardness group theory Hamiltonicity In this paper, we prove that optimally solving an n x n x 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 x n x 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 x n x 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Erik D. Demaine and Sarah Eisenstat and Mikhail Rudoy 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.24 urn:nbn:de:0030-drops-85336 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.24 eng https://creativecommons.org/licenses/by/3.0/legalcode