Message #1803

From: schuma <mananself@gmail.com>
Subject: Re: God’s Number for n^3 cubes.
Date: Thu, 30 Jun 2011 04:39:18 -0000

Very interesting.

I’m actually more interested in the asymptotics of the god’s number for 3^n, instead of n^3. Maybe 2^n is easier because it only contains nC pieces. I thought about this question before but never took it seriously. Actually every information theorist would consider the asymptotics as the dimension goes to infinity because that’s what happens in information theory.

In this type of results, the lower bound (converse) is typically more tricky to find. But this paper shows that for n^3 it can be found by a rather simple counting argument. This is an encouraging message. Maybe the asymptotics of 3^n can also be established by a counting argument.

I’ve heard of Erik Demaine before because of his entertaining research about origami. But I never knew he was interested in twisty puzzles.

Nan

— In 4D_Cubing@yahoogroups.com, Roice Nelson <roice3@…> wrote:
>
> 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
>