Paper by Erik D. Demaine
- 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.
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 Θ(n2/log n). The upper bound
comes from effectively parallelizing standard Θ(n2)
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).
- The full paper is available as arXiv:1106.5736 of the Computing Research Repository (CoRR).
- 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.
These pages are generated automagically from a
Last updated October 19, 2020 by