**Reference**:- Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, and Andrew Winslow, “Algorithms for Solving Rubik's Cubes”, in
*Proceedings of the 19th Annual European Symposium on Algorithms (ESA 2011)*, September 5–9, 2011, pages 689–700. **Abstract**:-
The Rubik's Cube is perhaps the world's most famous and iconic puzzle,
well-known to have a rich underlying mathematical structure (group theory).
In this paper, we show that the Rubik's Cube also has a rich underlying
algorithmic structure. Specifically, we show that the
*n*×*n*×*n*Rubik's Cube, as well as the*n*×*n*× 1 variant, has a “God's Number” (diameter of the configuration space) of Θ(*n*^{2}/log*n*). The upper bound comes from effectively parallelizing standard Θ(*n*^{2}) solution algorithms, while the lower bound follows from a counting argument. The upper bound gives an asymptotically optimal algorithm for solving a general Rubik's Cube in the worst case. Given a specific starting state, we show how to find the shortest solution in an*n*×*O*(1) ×*O*(1) Rubik's Cube. Finally, we show that finding this optimal solution becomes NP-hard in an*n*×*n*× 1 Rubik's Cube when the positions and colors of some of the cubies are ignored (not used in determining whether the cube is solved). **Comments**:- The full paper is available as arXiv:1106.5736 of the Computing Research Repository (CoRR).
**Availability**:- The paper is available in PDF (212k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- Rubik_STACS2018 (Solving the Rubik's Cube Optimally is NP-complete)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.