# Message #1802

From: Roice Nelson <roice3@gmail.com>

Subject: God’s Number for n^3 cubes.

Date: Wed, 29 Jun 2011 23:20:05 -0500

The following preprint showed up on arxiv.org yesterday, and will likely be

interesting to some here.

Algorithms for Solving Rubik’s Cubes <http://arxiv.org/abs/1106.5736>

The abstract reads:

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

A popular summary is here:

http://www.physorg.com/news/2011-06-math-rubik-cube.html