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
>
>
>
>