Solving the Rubik's Cube Optimally is NP-complete

DOI10.4230/LIPIcs.STACS.2018.24zbMath1487.68121arXiv1706.06708MaRDI QIDQ3304120

Mikhail Rudoy, Sarah Eisenstat, Erik D. Demaine

Publication date: 5 August 2020

Full work available at URL: https://arxiv.org/abs/1706.06708

zbMATH Keywords

group theoryHamiltonicityNP-hardnessRubik's Cubecombinatorial puzzles

Mathematics Subject Classification ID

Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (2)

Generalization of Rubik’s cube group to n-dimensional case ⋮ Solving Rubik’s cube via quantum mechanics and deep reinforcement learning

Cites Work

• Algorithms for Solving Rubik’s Cubes
• Hamilton Paths in Grid Graphs

This page was built for publication: Solving the Rubik's Cube Optimally is NP-complete