# Message #1808

From: Roice Nelson <roice3@gmail.com>

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!):

- The number of pieces (cubies) to solve will be of order O(3^n). When

limiting to 3-per-side, we won’t get any dimensional reduction like they did

(where number of cubies they had to solve ended up being proportional to

area rather than volume). The number of cubies to solve will effectively be

all of them. - Related to the above, 1C pieces are solved already (2n of these), but

they become negligible. O(3^n-2n) = O(3^n) - I think no particular cubie type will dominate the calculations, though

cubie types with smaller numbers of colors become less important with larger

n. For example, see these google charts made for counts for a

3^10<http://chart.apis.google.com/chart?chxr=0,0,10|1,0,15360&chxs=0,676767,11.5,0,lt,676767&chxt=x,y&chs=660x330&cht=lxy&chco=3072F3&chds=0,10,0,15360&chd=t:0,1,2,3,4,5,6,7,8,9,10|1,20,180,960,3360,8064,13440,15360,11520,5120,1024&chdlp=b&chls=2,4,1&chma=5,5,5,25&chtt=Number+of+cubies+vs.+cubie+type+in+3^10>and

counts

for a 3^20<http://chart.apis.google.com/chart?chxr=0,0,20|1,0,635043840&chxs=0,676767,11.5,0,lt,676767&chxt=x,y&chs=660x330&cht=lxy&chco=3072F3&chds=0,20,0,635043840&chd=t:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20|1,40,760,9120,77520,496128,2480640,9922560,32248320,85995520,189190144,343982080,515973120,635043840,635043840,508035072,317521920,149422080,49807360,10485760,1048576&chdlp=b&chls=2,4,1&chma=5,5,5,25&chtt=Number+of+cubies+vs.+cubie+type+in+3^20>

. - Unlike in the n^3, the growing number of higher-C piece types in the

3^n take longer and longer to solve, so it won’t be accurate to say each

could be solved in constant time, as was true in the paper. 2^C has been a

good "folk algorithm length" for how long it takes me to solve a piece with

C colors. I don’t know how to combine piece type counts with

length-to-solve estimates into the a very rough big O estimate for God’s

Number, but that feels like a first step. It seems complicated since many

individual piece type counts get involved.

- In the paper, they are able to divide out a factor by showing

parallelization is possible on the O(n) pieces that move during a twist of

an n^3. On the 3^n, a full third of the puzzle moves during a twist, so

O(n^3), and this is a much more significant number to have the opportunity

to try to parallelize. But I have no clue how to estimate how much

parallelization might be possible. Even if one found some desirable

tactics, finding an optimal parallelization and showing it so seems much

more daunting. - I wonder if some of the previous Goldilocks discussion might find some

applicability to the 3^n problem.

Cheers,

Roice

On Wed, Jun 29, 2011 at 11:39 PM, schuma <mananself@gmail.com> 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

> >

>

>

>

>

> ————————————

>

> Yahoo! Groups Links

>

>

>

>