Algorithms for solving Rubik's cubes

DOI10.1007/978-3-642-23719-5_58zbMATH Open1346.91022DBLPconf/esa/DemaineDELW11arXiv1106.5736OpenAlexW1848047021WikidataQ56804097 ScholiaQ56804097MaRDI QIDQ3092271FDOQ3092271

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)

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).

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

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 }\)

zbMATH Keywords

combinatorial optimizationdiametercombinatorial puzzlesGod's number

Mathematics Subject Classification ID

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

Cited In (15)

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

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)