# 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