Message #1804

From: Melinda Green <melinda@superliminal.com>
Subject: Re: [MC4D] Re: God’s Number for n^3 cubes.
Date: Wed, 29 Jun 2011 22:48:35 -0700

I knew that I knew him from somewhere too, and after digging, discovered
that he featured in a nice PBS documentary
<http://www.greenfusefilms.com/index.html> I had seen about the art and
science of paper folding. I don’t remember any mention of twisty puzzles
in the film.

My first thought about this new result was "Cool!". My second thought
was "What about for n^d?" I hope that we find out. I’m also hoping that
you or some other math wizard in this group will read the paper when it
comes out and translate it for us.

I’m not surprised to see a proof for God’s number come out; I’m most
surprised about their claim to have an software that will actually find
the shortest sequence of moves to solve a worst case scramble. I mean
this is called "God’s Algorithm", so does that mean that the software
written to implement it should be called "God"? That’s some pretty smart
software, but certainly not all-knowing. :-) In fact, I bet this is
the only thing that it knows, but if true, it sure does know it really well!

-Melinda

On 6/29/2011 9: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 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