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