Message #1808

From: Roice Nelson <>
Subject: Re: [MC4D] Re: God’s Number for n^3 cubes.
Date: Thu, 30 Jun 2011 22:16:45 -0500

I’ve seen the origami documentary Melinda mentions, and really enjoyed it.
Definitely recommended for members of this group. I also hadn’t known Erik
Demaine was interested in twisty puzzles till I saw this paper yesterday. I
got to see him give a talk at the Gathering For Gardner last year, on
origami derived fonts. There was a Rubik block at that conference, and
about 6 of us presented (mine was an intro to MagicTile and the Klein
Quartic hyperbolic puzzle). I’d like to think that block of talks helped
stoke interest towards a paper like this, though I’m sure it’s just the
dominating gravitational pull of Rubik’s Cube - it is bound to suck
in anyone who dares wander too close :)

After reading the paper intro and a few of the sections while thinking about
the 3^n, it feels like the latter would be a more difficult problem. It
does seems quite possible that the order of God’s Number for the 3^n
will grow exponentially rather than polynomially. Some simple observations
I could make were the following (no accuracy guarantees!):


On Wed, Jun 29, 2011 at 11:39 PM, schuma <> wrote:

> 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, Roice Nelson <roice3@…> wrote:
> >
> > The following preprint showed up on yesterday, and will likely
> be
> > interesting to some here.
> >
> > Algorithms for Solving Rubik’s Cubes <>
> >
> > 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:
> >
> >
> >
> ————————————
> Yahoo! Groups Links