Message #1816

From: schuma <>
Subject: Re: God’s Number for n^3 cubes.
Date: Sat, 02 Jul 2011 01:13:05 -0000


Let’s assume that a k-color piece takes a^k moves on average. (previously we assumed a=2) This might be the performance after using parallelization. I re-calculated the result.

(1) The total number of moves ~ (2a+1)^n.
(2) The dominating type of pieces has n*2a/(2a+1) colors.

When a is between 1 and 2, which is probably true, the dominating type is indeed between (2/3)n and (4/5)n. Your intuition was right.


— In, Roice Nelson <roice3@…> wrote:
> Very interesting that the asymptotics change if you use macros or not.
> Parallelization may also change the balancing point, since the 4/5 point is
> currently contingent on our assumption of 2^k sequences. Presumably, we may
> instead have another expression for sequence length as a function of piece
> type, and some other piece will then dominate. Can one make an
> argument that the final point will live somewhere within this (2/3,4/5)
> interval? As long as the difficult of solving pieces increases with k, it
> seems safe to claim that will be the case.
> Roice
> On Fri, Jul 1, 2011 at 6:20 PM, schuma <mananself@…> wrote:
> > Yes the ability of parallelization is hard to specify. It’s also the key
> > contribution of Demaine’s paper.
> >
> > An interesting interpretation of my calculation is as follows. The
> > (2/3)n-color pieces are the most, but the number of moves per piece is not
> > the greatest. The n-color pieces requires the most number of moves per
> > piece, but there’re not too many of them. So there’s a balancing point
> > between them, in terms of the total number of moves. That balancing point is
> > (4/5)n-color pieces. Those are the hardest part.
> >
> > If one is using macro to solve it and has recorded a 3-cycle macro for each
> > type of pieces, the solving time is proportional to the number of pieces
> > rather than the total number of moves. In that case (2/3)n-color pieces are
> > the major difficulty.
> >
> > Nan
> >