Algorithms for solving Rubik's cubes

DOI10.1007/978-3-642-23719-5_58MaRDI QIDQ3092271zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, Andrew Winslow

Publication date 16 September 2011

Published in Algorithms – ESA 2011 (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimizationcombinatorial puzzlesdiameterGod's number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Combinatorial games (91A46)

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 x n x n Rubik's Cube, as well as the n x n x 1 variant, has a "God's Number" (diameter of the configuration space) of Theta(n^2/log n). The upper bound comes from effectively parallelizing standard Theta(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 x O(1) x O(1) Rubik's Cube. Finally, we show that finding this optimal solution becomes NP-hard in an n x n x 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).

Recommendations

• Solving the Rubik's Cube Optimally is NP-complete
• scientific article; zbMATH DE number 5494046
• The Diameter of the Rubik's Cube Group Is Twenty
• The diameter of the Rubik's Cube group is twenty.
• Twenty-two moves suffice for Rubik's Cube\(^{\circledR }\)

Cited in

(16)

• Harnessing parallel disks to solve Rubik's cube
• A real-time algorithm for the \((n^{2}-1)\)-puzzle
• Analysis of the picture cube puzzle
• On God's number(s) for Rubik's slide
• Solving combinatorial puzzles with parallel evolutionary algorithms
• Solving the Rubik's Cube Optimally is NP-complete
• Proof Pearl: Revisiting the Mini-rubik in Coq
• Cubelike Puzzles--What are They and How do you Solve Them
• On then×n×nRubik's Cube
• The first law of cubology for the Rubik's Revenge
• scientific article; zbMATH DE number 5494046 (Why is no real title available?)
• Solving Rubik’s cube via quantum mechanics and deep reinforcement learning
• The Invisible Solutions of the Rubik’s Cube
• Computational complexity of puzzles and related topics
• Reconfiguring shortest paths in graphs
• Twenty-two moves suffice for Rubik's Cube\(^{\circledR }\)

This page was built for publication: Algorithms for solving Rubik's cubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3092271)