Paper by Erik D. Demaine

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²/log n). The upper bound comes from effectively parallelizing standard Θ(n²) 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)