Algorithms for Solving Rubik's Cubes

Details Algorithms for Solving Rubik's Cubes Algorithms for Solving Rubik's Cubes

2011-06-28

arxiv.org/abs/1106.5736v1

Computer Science

Data Structures and Algorithms

34 pages, 9 figures. A short version of this paper is to appear at the 19th Annual European Symposium on Algorithms

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Algorithms for Solving Rubik's Cubes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithms for Solving Rubik's Cubes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for Solving Rubik's Cubes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-41884