Thread: "God's Number for n^3 cubes."

Very interesting.=20

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 e=
very information theorist would consider the asymptotics as the dimension g=
oes to infinity because that's what happens in information theory.

In this type of results, the lower bound (converse) is typically more trick=
y to find. But this paper shows that for n^3 it can be found by a rather si=
mple counting argument. This is an encouraging message. Maybe the asymptoti=
cs of 3^n can also be established by a counting argument.=20

I've heard of Erik Demaine before because of his entertaining research abou=
t origami. But I never knew he was interested in twisty puzzles.=20

Nan



--- In 4D_Cubing@yahoogroups.com, Roice Nelson wrote:
>
> The following preprint showed up on arxiv.org yesterday, and will likely =
be
> interesting to some here.
>=20
> Algorithms for Solving Rubik's Cubes
>=20
> The abstract reads:
>=20
> The Rubik's Cube is perhaps the world's most famous and iconic puzzle,
> > well-known to have a rich underlying mathematical structure (group theo=
ry).
> > 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 fro=
m
> > effectively parallelizing standard Theta(n^2) solution algorithms, whil=
e 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 C=
ube
> > when the positions and colors of some of the cubies are ignored (not us=
ed in
> > determining whether the cube is solved).
>=20
>=20
> A popular summary is here:
>=20
> http://www.physorg.com/news/2011-06-math-rubik-cube.html
>

--------------010406020007040808070308
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

I knew that I knew him from somewhere too, and after digging, discovered
that he featured in a nice PBS documentary
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 wrote:
>> The following preprint showed up on arxiv.org yesterday, and will likely be
>> interesting to some here.
>>
>> Algorithms for Solving Rubik's Cubes
>>
>> 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

--------------010406020007040808070308
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit




http-equiv="Content-Type">


I knew that I knew him from somewhere too, and after digging,
discovered that he featured in a nice href="http://www.greenfusefilms.com/index.html">PBS documentary
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

Since somebody in this group may not know the big-O notation, let me brief =
the main results of this paper without using it. I've only read the introdu=
ction and glanced through the rest. I apologize if there's any mistake.=20

About the god's number, we know it is 20 for 3x3x3. What about 4x4x4, 5x5x5=
, and, nxnxn? It would be ideal if we can get a formula of the god's number=
for n^3, for arbitrary n. The exact formula might be something like=20

floor[ 10 * n^2/log(n) + 2*n + 7 ].

But the goal of finding the exact formula is out of reach. Too hard.=20

Let's ask an easier question. Let's say we only care about nxnxn for very l=
arge n. If n =3D 1000, then the term (10 * n^2/log(n)) is about a million, =
the term (2*n) is two thousand, the term 7 is still 7. In this case we can =
comfortably ignore (2*n + 7) and only keep (10 * n^2/log(n)), because doing=
that only incurs a small error of 0.2%. We can get pretty high precision f=
rom the "leading term" (10 * n^2/log(n)). So finding the leading term is ou=
r next goal. Unfortunately, this goal is still out of reach. Forget it.

Let's make it even easier. Let's not care if the leading term is (10 * n^2/=
log(n)) or (2 * n^2/log(n)). I'm satisfied as long as I know it's a constan=
t factor times (n^2/log(n)) but not something like (n^3) or (n). This level=
of result will tell us whether the god's number for 1000x1000x1000 is in t=
he order of magnitude of millions (n^2/log(n)), instead of billions (n^3) o=
r thousands (n). So we still have some valuable information about the god's=
number. This goal is realistic. This is what the paper is about. The autho=
rs showed that the god's number is basically a constant C times (n^2/log(n)=
). But they couldn't show what the constant C is. They only provided the or=
der of magnitude of the god's number, for large n. If you ask the god's num=
ber for n=3D1000 is 5 million or 7 million, they don't know. If you ask the=
god's number for n=3D5, they can only tell you it may be tens or hundreds.=
This is only a very rough estimate, which becomes important only when n is=
very large.

There's a story about the formula C*(n^2/log(n)). Once you know how to solv=
e 4x4x4 and 5x5x5, solving nxnxn is just a matter of time. Most people use =
reduction method. They will first gather all the face pieces on the correct=
faces and the edge pieces on the correct edges, and finally solve it like =
a 3x3x3, won't they? For very large n, most of the pieces are face pieces. =
There are 6*(n-2)^2 of them. One may solve them piece by piece, or first ga=
ther some of them into a line and solve a face line by line. But anyway on =
average one needs about 3~5 turns per piece. Therefore solving them takes a=
bout some constant (maybe 20~30) * n^2 turns. After that the edge pieces an=
d 3x3x3 phases are relatively easy. So solving nxnxn takes about (constant*=
n^2) turns. This kind of algorithms is referred to as "folk algorithms" in=
this paper.=20

The question is, are the "folk algorithms" based on reduction close to opti=
mum? Can one greatly improve the efficiency of such algorithms not by a fac=
tor of 2 or 3, but by an order of magnitude? No one knows the answer before=
this paper (as claimed in this paper).=20

Surprisingly the authors can improve on the folk algorithms by a factor of =
log(n). For very very large n, log(n) could be a great number. So this is a=
n order of magnitude improvement. As a result, the number of turns can be i=
mproved from (constant* n^2) to (constant * n^2/log(n)). Then they showed t=
hat NO ONE can do further order of magnitude improvement. Therefore if you =
only care about the order-of-magnitude efficiency, they are the best.

How did they achieve it? They talked about "cubie clusters". They said that=
they can solve a lot of the face pieces in parallel, at the same time. Thi=
s is very interesting but I don't know the details yet. I have no idea how =
their algorithm works.=20

They considered three variations of puzzles:=20

(1) n x n x n: I've talked about their result about the order-of-magnitude =
of god's number.

(2) n x n x 1: For this kind of puzzle the god's number is proved to be in =
the same order-of-magnitude as for nxnxn. Actually they studied this first.=
The result for nxnxn is based on that of nxnx1.

(3) n x c1 x c2: (c1, c2 are fixed constant) Think of Oskar's 23x2x2 //www.shapeways.com/model/96696/overlap_cube_2x2x23.html>, where c1=3Dc2=3D=
2 and n=3D23. For this type of puzzles, they have a good news that there ex=
ists an efficient method to find the optimal solution from arbitrary starti=
ng state. But this good news can not be extended to nxnxn or nxnx1. Actuall=
y they show that nxnx1 could be pretty hard to solve optimally. The last st=
atement is tricky to phrase rigorously, but that's the main message.=20

Summary of key results:=20

(1) For the important puzzle nxnxn, they found the order-of-magnitude of th=
e god's number. For example, if n=3D1000, they know the god's number is abo=
ut millions.

(2) They improved the "folk algorithms" by doing something in parallel.=20

(3) 23x2x2 is easy to solve optimally, but 23x23x1 is hard to solve optimal=
ly.=20

Melinda, I searched through the document using the word "software". The onl=
y result I found is in page 18, the proof of Lemma 9. That doesn't seem to =
be directly related to any result. So I don't know which "software" you wer=
e talking about.

Nan

--- In 4D_Cubing@yahoogroups.com, Melinda Green wrote:
>
> I knew that I knew him from somewhere too, and after digging, discovered=
=20
> that he featured in a nice PBS documentary=20
> I had seen about the art and=20
> science of paper folding. I don't remember any mention of twisty puzzles=
=20
> in the film.
>=20
> My first thought about this new result was "Cool!". My second thought=20
> was "What about for n^d?" I hope that we find out. I'm also hoping that=20
> you or some other math wizard in this group will read the paper when it=20
> comes out and translate it for us.
>=20
> I'm not surprised to see a proof for God's number come out; I'm most=20
> surprised about their claim to have an software that will actually find=20
> the shortest sequence of moves to solve a worst case scramble. I mean=20
> this is called "God's Algorithm", so does that mean that the software=20
> written to implement it should be called "God"? That's some pretty smart=
=20
> software, but certainly not all-knowing. :-) In fact, I bet this is=20
> the only thing that it knows, but if true, it sure does know it really we=
ll!
>=20
> -Melinda
>=20

I don't usually post, but I wanted to make a quick correction:

Big-O notation has nothing to do with the size of God's Number for a n^3 cu=
be, but with the number of computational operations needed to compute that =
number. For instance, an O(n^2) sort algorithm requires a number of operati=
ons proportional to the square of how many entries are being sorted.

So anyway, the big-O is used for measuring time, not the scale of your answ=
er. And, as a useful speed comparison, the difference of a factor of log(n)=
is approximately the difference between the best available sorting algorit=
hm (O(n*log(n))) and your average high-schooler's algorithm (O(n^2)). (Yes,=
yes, I know, log^2(n) =3D/=3D n, but it seemed like a good scale reference=
)


--- In 4D_Cubing@yahoogroups.com, "schuma" wrote:
>
> Since somebody in this group may not know the big-O notation, let me brie=
f the main results of this paper without using it. I've only read the intro=
duction and glanced through the rest. I apologize if there's any mistake.=20
>=20
> About the god's number, we know it is 20 for 3x3x3. What about 4x4x4, 5x5=
x5, and, nxnxn? It would be ideal if we can get a formula of the god's numb=
er for n^3, for arbitrary n. The exact formula might be something like=20
>=20
> floor[ 10 * n^2/log(n) + 2*n + 7 ].
>=20
> But the goal of finding the exact formula is out of reach. Too hard.=20
>=20
> Let's ask an easier question. Let's say we only care about nxnxn for very=
large n. If n =3D 1000, then the term (10 * n^2/log(n)) is about a million=
, the term (2*n) is two thousand, the term 7 is still 7. In this case we ca=
n comfortably ignore (2*n + 7) and only keep (10 * n^2/log(n)), because doi=
ng that only incurs a small error of 0.2%. We can get pretty high precision=
from the "leading term" (10 * n^2/log(n)). So finding the leading term is =
our next goal. Unfortunately, this goal is still out of reach. Forget it.
>=20
> Let's make it even easier. Let's not care if the leading term is (10 * n^=
2/log(n)) or (2 * n^2/log(n)). I'm satisfied as long as I know it's a const=
ant factor times (n^2/log(n)) but not something like (n^3) or (n). This lev=
el of result will tell us whether the god's number for 1000x1000x1000 is in=
the order of magnitude of millions (n^2/log(n)), instead of billions (n^3)=
or thousands (n). So we still have some valuable information about the god=
's number. This goal is realistic. This is what the paper is about. The aut=
hors showed that the god's number is basically a constant C times (n^2/log(=
n)). But they couldn't show what the constant C is. They only provided the =
order of magnitude of the god's number, for large n. If you ask the god's n=
umber for n=3D1000 is 5 million or 7 million, they don't know. If you ask t=
he god's number for n=3D5, they can only tell you it may be tens or hundred=
s. This is only a very rough estimate, which becomes important only when n =
is very large.
>=20
> There's a story about the formula C*(n^2/log(n)). Once you know how to so=
lve 4x4x4 and 5x5x5, solving nxnxn is just a matter of time. Most people us=
e reduction method. They will first gather all the face pieces on the corre=
ct faces and the edge pieces on the correct edges, and finally solve it lik=
e a 3x3x3, won't they? For very large n, most of the pieces are face pieces=
. There are 6*(n-2)^2 of them. One may solve them piece by piece, or first =
gather some of them into a line and solve a face line by line. But anyway o=
n average one needs about 3~5 turns per piece. Therefore solving them takes=
about some constant (maybe 20~30) * n^2 turns. After that the edge pieces =
and 3x3x3 phases are relatively easy. So solving nxnxn takes about (constan=
t* n^2) turns. This kind of algorithms is referred to as "folk algorithms" =
in this paper.=20
>=20
> The question is, are the "folk algorithms" based on reduction close to op=
timum? Can one greatly improve the efficiency of such algorithms not by a f=
actor of 2 or 3, but by an order of magnitude? No one knows the answer befo=
re this paper (as claimed in this paper).=20
>=20
> Surprisingly the authors can improve on the folk algorithms by a factor o=
f log(n). For very very large n, log(n) could be a great number. So this is=
an order of magnitude improvement. As a result, the number of turns can be=
improved from (constant* n^2) to (constant * n^2/log(n)). Then they showed=
that NO ONE can do further order of magnitude improvement. Therefore if yo=
u only care about the order-of-magnitude efficiency, they are the best.
>=20
> How did they achieve it? They talked about "cubie clusters". They said th=
at they can solve a lot of the face pieces in parallel, at the same time. T=
his is very interesting but I don't know the details yet. I have no idea ho=
w their algorithm works.=20
>=20
> They considered three variations of puzzles:=20
>=20
> (1) n x n x n: I've talked about their result about the order-of-magnitud=
e of god's number.
>=20
> (2) n x n x 1: For this kind of puzzle the god's number is proved to be i=
n the same order-of-magnitude as for nxnxn. Actually they studied this firs=
t. The result for nxnxn is based on that of nxnx1.
>=20
> (3) n x c1 x c2: (c1, c2 are fixed constant) Think of Oskar's 23x2x2 p://www.shapeways.com/model/96696/overlap_cube_2x2x23.html>, where c1=3Dc2=
=3D2 and n=3D23. For this type of puzzles, they have a good news that there=
exists an efficient method to find the optimal solution from arbitrary sta=
rting state. But this good news can not be extended to nxnxn or nxnx1. Actu=
ally they show that nxnx1 could be pretty hard to solve optimally. The last=
statement is tricky to phrase rigorously, but that's the main message.=20
>=20
> Summary of key results:=20
>=20
> (1) For the important puzzle nxnxn, they found the order-of-magnitude of =
the god's number. For example, if n=3D1000, they know the god's number is a=
bout millions.
>=20
> (2) They improved the "folk algorithms" by doing something in parallel.=20
>=20
> (3) 23x2x2 is easy to solve optimally, but 23x23x1 is hard to solve optim=
ally.=20
>=20
> Melinda, I searched through the document using the word "software". The o=
nly result I found is in page 18, the proof of Lemma 9. That doesn't seem t=
o be directly related to any result. So I don't know which "software" you w=
ere talking about.
>=20
> Nan
>=20
> --- In 4D_Cubing@yahoogroups.com, Melinda Green wrote:
> >
> > I knew that I knew him from somewhere too, and after digging, discovere=
d=20
> > that he featured in a nice PBS documentary=20
> > I had seen about the art and=
=20
> > science of paper folding. I don't remember any mention of twisty puzzle=
s=20
> > in the film.
> >=20
> > My first thought about this new result was "Cool!". My second thought=20
> > was "What about for n^d?" I hope that we find out. I'm also hoping that=
=20
> > you or some other math wizard in this group will read the paper when it=
=20
> > comes out and translate it for us.
> >=20
> > I'm not surprised to see a proof for God's number come out; I'm most=20
> > surprised about their claim to have an software that will actually find=
=20
> > the shortest sequence of moves to solve a worst case scramble. I mean=20
> > this is called "God's Algorithm", so does that mean that the software=20
> > written to implement it should be called "God"? That's some pretty smar=
t=20
> > software, but certainly not all-knowing. :-) In fact, I bet this is=20
> > the only thing that it knows, but if true, it sure does know it really =
well!
> >=20
> > -Melinda
> >
>

Shevek,=20

You seem to have a very different understanding of the paper. In my underst=
anding, they are showing that the god's number itself =3D Theta(n^2*log(n))=
. But in your understanding, the number of operation to compute the god's n=
umber is Theta(n^2*log(n)). I checked the paper again and hold my point.

In computational complexity, big-O notation is used to measure the computat=
ional time. But in other fields, it can be used to measure anything, in thi=
s paper, the god's number itself. I wonder if you buy it or now.

Nan

--- In 4D_Cubing@yahoogroups.com, "shevek1248" wrote:
>
> I don't usually post, but I wanted to make a quick correction:
>=20
> Big-O notation has nothing to do with the size of God's Number for a n^3 =
cube, but with the number of computational operations needed to compute tha=
t number. For instance, an O(n^2) sort algorithm requires a number of opera=
tions proportional to the square of how many entries are being sorted.
>=20
> So anyway, the big-O is used for measuring time, not the scale of your an=
swer. And, as a useful speed comparison, the difference of a factor of log(=
n) is approximately the difference between the best available sorting algor=
ithm (O(n*log(n))) and your average high-schooler's algorithm (O(n^2)). (Ye=
s, yes, I know, log^2(n) =3D/=3D n, but it seemed like a good scale referen=
ce)
>=20
>=20

--000325556062899cb404a6f97267
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

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 abou=
t
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 effectivel=
y be
all of them.
- Related to the above, 1C pieces are solved already (2n of these), but
they become negligible. O(3^n-2n) =3D O(3^n)
- I think no particular cubie type will dominate the calculations, thoug=
h
cubie types with smaller numbers of colors become less important with la=
rger
n. For example, see these google charts made for counts for a
3^106767,11.5,0,lt,676767&chxt=3Dx,y&chs=3D660x330&cht=3Dlxy&chco=3D3072F3&chds=
=3D0,10,0,15360&chd=3Dt:0,1,2,3,4,5,6,7,8,9,10|1,20,180,960,3360,8064,13440=
,15360,11520,5120,1024&chdlp=3Db&chls=3D2,4,1&chma=3D5,5,5,25&chtt=3DNumber=
+of+cubies+vs.+cubie+type+in+3^10>and
counts
for a 3^200&chxs=3D0,676767,11.5,0,lt,676767&chxt=3Dx,y&chs=3D660x330&cht=3Dlxy&chco=
=3D3072F3&chds=3D0,20,0,635043840&chd=3Dt:0,1,2,3,4,5,6,7,8,9,10,11,12,13,1=
4,15,16,17,18,19,20|1,40,760,9120,77520,496128,2480640,9922560,32248320,859=
95520,189190144,343982080,515973120,635043840,635043840,508035072,317521920=
,149422080,49807360,10485760,1048576&chdlp=3Db&chls=3D2,4,1&chma=3D5,5,5,25=
&chtt=3DNumber+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 bee=
n a
good "folk algorithm length" for how long it takes me to solve a piece w=
ith
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 ma=
ny
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 opportuni=
ty
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 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 piec=
es.
> I thought about this question before but never took it seriously. Actuall=
y
> every information theorist would consider the asymptotics as the dimensio=
n
> 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 th=
e
> 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 wrote:
> >
> > The following preprint showed up on arxiv.org yesterday, and will likel=
y
> be
> > interesting to some here.
> >
> > Algorithms for Solving Rubik's Cubes
> >
> > 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 underlyi=
ng
> > > 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" (diamete=
r
> 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 a=
n
> > > asymptotically optimal algorithm for solving a general Rubik's Cube i=
n
> 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 sho=
w
> 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
>
>
>
>

--000325556062899cb404a6f97267
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

=C2=A0=20



Small typo correction in the second to last bullet about parallelizing... =
=C2=A0I meant to write O(3^n) pieces will move during a twist. =C2=A0I seem=
to have trouble with accidentally reversing this notation some times :S


Roice


On Thu, Jun 30, 2011 at 10:16 PM, Roice Nelson wrote:


I've seen the origami documentary Melinda mentions, and really enjoyed it.=
=C2=A0 Definitely recommended for members of this group.=C2=A0 I also hadn'=
t known Erik Demaine was interested in twisty puzzles till I saw this paper=
yesterday.=C2=A0 I got to see him give a talk at the Gathering For Gardner=
last year, on origami derived fonts.=C2=A0 There was a Rubik block at that=
conference, and about 6 of us=C2=A0presented (mine was an intro to MagicTi=
le and the Klein Quartic hyperbolic puzzle).=C2=A0 I'd like to think that b=
lock of talks=C2=A0helped stoke interest towards a paper like this, though =
I'm sure it's just the dominating gravitational pull of Rubik's Cube=C2=A0-=
it is=C2=A0bound to suck in=C2=A0anyone who dares wander too close :)
=C2=A0
After reading the paper=C2=A0intro and a few of the sections while thinking=
about the 3^n, it feels like the latter would be a more difficult problem.=
=C2=A0 It does seems quite possible that=C2=A0the order of God's Number for=
the 3^n will=C2=A0grow exponentially rather than polynomially.=C2=A0 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).=C2=A0=C2=A0=
When limiting=C2=A0to 3-per-side, we won't get any dimensional reduction li=
ke they did (where number of cubies they had to=C2=A0solve ended up being p=
roportional to area rather than volume).=C2=A0 The number of cubies to solv=
e will effectively be all of them.
Related to the above, 1C pieces are solved already (2n of these), but they =
become negligible.=C2=A0 O(3^n-2n) =3D O(3^n)
I think no particular cubie type will dominate the calculations, though cub=
ie types with smaller numbers of colors become less important with larger n=
. =C2=A0For example, see these google charts made for counts for a 3^10 and=
=C2=A0counts for a 3^20.

Unlike in the n^3, the growing number of higher-C piece types in the 3^n ta=
ke 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.=C2=A0 2^C has been a go=
od "folk algorithm length" for how long it takes me to solve a piece with C=
colors.=C2=A0 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.=C2=A0 It seems complicated since many indivi=
dual piece type counts get involved.
In the paper, they are able to divide out a factor by showing parallelizati=
on is possible on the O(n) pieces that move during a twist of an n^3.=C2=A0=
On the 3^n, a full third of the puzzle moves during a twist,=C2=A0so O(n^3=
), and this is a much more significant number to have the opportunity to tr=
y to parallelize.=C2=A0=C2=A0But=C2=A0I have no clue how to estimate how mu=
ch parallelization might be possible. =C2=A0Even if one found some desirabl=
e 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 appl=
icability to the 3^n problem.=C2=A0
Cheers,
Roice




=C2=A0
On Wed, Jun 29, 2011 at 11: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 e=
very information theorist would consider the asymptotics as the dimension g=
oes to infinity because that's what happens in information theory.

In this type of results, the lower bound (converse) is typically more trick=
y to find. But this paper shows that for n^3 it can be found by a rather si=
mple counting argument. This is an encouraging message. Maybe the asymptoti=
cs of 3^n can also be established by a counting argument.

I've heard of Erik Demaine before because of his entertaining research abou=
t origami. But I never knew he was interested in twisty puzzles.

Nan





--0-2042231771-1309513306=:75038
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

top" style=3D"font: inherit;"> How about restricting oneself to God's a= lgorithm for the 3^4 case? I wanted to get an idea for the likely length of God's algorithm (both in the QTM and the= FTM). There must be some some heuristic results available now that the MC4D has been in= use for some years now. Even more so I am interested in any results for th= e 2^4 case in both metrics but in particular the quarter-turn one. Sorry if this information is i= n circulation elsewhere - too much information to sift through and too litt= le time! --- On Fri, 1/7/11, Roice Nelson <roice3@gmail.com= > wrote: px; MARGIN-LEFT: 5px"> From: Roice Nelson <roice3@gmail.com> Su= bject: Re: [MC4D] Re: God's Number for n^3 cubes. To: 4D_Cubing@yahoogro= ups.com Date: Friday, 1 July, 2011, 5:52  =20 Small typo correction in the second to last bullet about parallelizing= ...  I meant to write O(3^n) pieces will move during a twist. &= nbsp;I seem to have trouble with accidentally reversing this notation some = times :S Roice On Thu, Jun 30, 2011 at 10:16 PM, Roic= e Nelson <ompose?to=3Droice3@gmail.com" rel=3Dnofollow target=3D_blank ymailto=3D"mai= lto:roice3@gmail.com">roice3@gmail.com> wrote: _quote> I've seen the origami documentary Melinda mentions, and really enjoyed= it.  Definitely recommended for members of this group.  I also h= adn't known Erik Demaine was interested in twisty puzzles till I saw this p= aper yesterday.  I got to see him give a talk at the Gathering For Gar= dner 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 Mag= icTile and the Klein Quartic hyperbolic puzzle).  I'd like to think th= at block of talks helped stoke interest towards a paper like this, tho= ugh I'm sure it's just the dominating gravitational pull of Rubik's Cube&nb= sp;- it is bound to suck in anyone who dares wander too close :)<= /DIV>   After reading the paper intro and a few of the sections while thi= nking about the 3^n, it feels like the latter would be a more difficult pro= blem.  It does seems quite possible that the order of God's Numbe= r for the 3^n will grow exponentially rather than polynomially.  = Some simple observations I could make were the following (no accuracy guara= ntees!): The number of pieces (cubies) to solve will be of order O(3^n). &n= bsp;When limiting to 3-per-side, we won't get any dimensional reductio= n like they did (where number of cubies they had to solve ended up bei= ng 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 t= hey become negligible.  O(3^n-2n) =3D 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 larg= er n.  For example, see these google charts made for /chart.apis.google.com/chart?chxr=3D0,0,10%7C1%2C0%2C15360%26chxs%3D0%2C676= 767%2C11.5%2C0%2Clt%2C676767%26chxt%3Dx%2Cy%26chs%3D660x330%26cht%3Dlxy%26c= hco%3D3072F3%26chds%3D0%2C10%2C0%2C15360%26chd%3Dt:0,1,2,3,4,5,6,7,8,9,10%7= C1,20,180,960,3360,8064,13440,15360,11520,5120,1024&chdlp=3Db&chls= =3D2,4,1&chma=3D5,5,5,25&chtt=3DNumber+of+cubies+vs.+cubie+type+in+= 3%5E10" rel=3Dnofollow target=3D_blank>counts for a 3^10 and  href=3D"http://chart.apis.google.com/chart?chxr=3D0,0,20%7C1%2C0%2C6350438= 40%26chxs%3D0%2C676767%2C11.5%2C0%2Clt%2C676767%26chxt%3Dx%2Cy%26chs%3D660x= 330%26cht%3Dlxy%26chco%3D3072F3%26chds%3D0%2C20%2C0%2C635043840%26chd%3Dt:0= ,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20%7C1,40,760,9120,77520,4= 96128,2480640,9922560,32248320,85995520,189190144,343982080,515973120,63504= 3840,635043840,508035072,317521920,149422080,49807360,10485760,1048576&= chdlp=3Db&chls=3D2,4,1&chma=3D5,5,5,25&chtt=3DNumber+of+cubies+= vs.+cubie+type+in+3%5E20" rel=3Dnofollow target=3D_blank>counts for a 3^20<= /A>. 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 cou= ld 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 w= ith C colors.  I don't know how to combine piece type counts with leng= th-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 i= ndividual piece type counts get involved. In the paper, they are able to divide out a factor by showing paralleli= zation is possible on the O(n) pieces that move during a twist of an n^3.&n= bsp; 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 t= o try to parallelize.  But I have no clue how to estimate ho= w much parallelization might be possible.  Even if one found some desi= rable tactics, finding an optimal parallelization and showing it so seems m= uch 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, schu= ma <?to=3Dmananself@gmail.com" rel=3Dnofollow target=3D_blank ymailto=3D"mailto= :mananself@gmail.com">mananself@gmail.com> wrote: _quote>Very interesting. I'm actually more interested in the asympto= tics of the god's number for 3^n, instead of n^3. Maybe 2^n is easier becau= se it only contains nC pieces. I thought about this question before but nev= er took it seriously. Actually every information theorist would consider th= e asymptotics as the dimension goes to infinity because that's what happens= in information theory. In this type of results, the lower bound (co= nverse) 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 encouragi= ng message. Maybe the asymptotics of 3^n can also be established by a count= ing argument. I've heard of Erik Demaine before because of his enter= taining research about origami. But I never knew he was interested in twist= y puzzles. Nan >

--0-2042231771-1309513306=:75038--

Hi Roice,

Here's my calculation based on your suggestion:

(1) The number of k-color pieces on a 3^n is 2^k*(n choose k). [footnote 1]=
In terms of the number, (2/3*n)-color pieces are dominating. [footnote 2]

(2) I think your proposal of using 2^k moves to solve a k-color piece is go=
od, because it basically means one can use a nested commutator with k layer=
s to=20

construct a pure 3-cycle for a kC piece. This coincide with my intuition. I=
wonder if the MC7D solvers have more insights. Andrey and Charlie, how do =
you=20

guys solve the 7D pieces?

(3) Let's assume we solve one piece at a time, with no parallelization. Act=
ually, if one can do parallelization, but cannot achieve an exponential gai=
n=20

(solve a^n pieces at the same time for some constant a), it still cannot af=
fect the big picture.

Combine all these points, an estimate of the move count for solving a 3^n i=
s about:

summation_{k=3D0...n} 2^k * 2^k * (n choose k) =3D 5^n

In this summation, there's actually a dominating term: k =3D 0.8n [footnote=
3]. Solving the (0.8n)C pieces takes the most moves, which is about 5^n di=
vided by=20

a polynomial of n, which is essentially 5^n (note that I only care about th=
e base of the exponential function). This estimate is tighter than a quick =
upper=20

bound of 6^n, which can be obtained by noticing there are no more than 3^n =
pieces, each can be solved by no more than 2^n moves.=20

My conjecture is that one cannot improve the base of the exponential functi=
on, e.g., reduce 5^n to 4.9^n. A rigorous statement would be:

Conjecture: For any epsilon>0, there exists N>0, so that for all n>N, the g=
od's number of 3^n is between (5-epsilon)^n and (5+epsilon)^n.=20

Nan


Footnote:
[1]: ref: . Note that the =
m-dimensional boundary has (n-m) colors.
[2]: Use the same method as in [3].
[3]: Why k=3D0.8n dominates the number of moves:=20
Take the estimate (n choose k) is approximately 2^(n* h(k/n)), where h() is=
the binary entropy function=20

. The summation becom=
es:

summation_{k=3D0...n} 2^(n* (2k/n + h(k/n)) )

When n is large, what's important is the exponent. There's a dominating ter=
m in the summation, that is exponentially greater than all other terms. Sin=
ce the=20

function (2k/n + h(k/n) reaches it's maximum log5/log2 at k/n =3D 0.8, the =
(0.8n)-color pieces take most of the moves. The single term of k=3D0.8n

One can use the same technique to see why (2/3*n) pieces dominate the numbe=
r of pieces.






--- In 4D_Cubing@yahoogroups.com, Roice Nelson wrote:
>
> Small typo correction in the second to last bullet about parallelizing...=
I
> meant to write *O(3^n)* pieces will move during a twist. I seem to have
> trouble with accidentally reversing this notation some times :S
>=20
> Roice

--001636456f8c3ccf4904a709c54c
Content-Type: text/plain; charset=ISO-8859-1

Great stuff Nan!

I experimentally observed last night that there was a maximum at
(2/3*n)-color pieces, but my intuition was still telling me it wouldn't
dominate (that a smearing of pieces would continue to contribute). Love it
when my intuition gets put in it's place :D

Here are piece count graphs I had made for
250and
500 dimensional
Rubik's Cubes (I started overflowing double precision in the
600s). The cubie-count peak you calculated at 2/3rds is easy to see. The
curve is wider on the latter in an absolute sense, spanning some 70
significant piece types rather than 50. But as a proportion of the total
number of piece types, I see now it is still getting thinner. So as
dimension -> infinity, one can think about how this smooth peak approaches a
spike!

I love that you threw a conjecture out there too. All your reasoning looks
great, and the only biggish question for me right now is the
parallelization, and whether that could be leveraged to lower the base of
the exponent. I'm going to go out on a limb and say it's possible. After
your analysis, it feels more tractable to investigate too, because we only
need to parallelize one piece type.

One thought on that is not using 3-cycles. Say you could generate a
sequence that cycles a much larger number of pieces. You do preliminary
moves to put a bunch of pieces in the correct place in this cycle, run it,
then undo the preliminaries. I used this tactic with a 7-cycle of 3C pieces
on MC4D (in my glory days, when I used to still be in the running for
shortest solutions). Maybe cycles of exponential length are even possible
to take advantage of, since there are an exponential number of pieces to be
solved. I'll think on this stuff more.

seeya,
Roice

On Fri, Jul 1, 2011 at 3:31 PM, schuma wrote:

> Hi Roice,
>
> Here's my calculation based on your suggestion:
>
> (1) The number of k-color pieces on a 3^n is 2^k*(n choose k). [footnote 1]
> In terms of the number, (2/3*n)-color pieces are dominating. [footnote 2]
>
> (2) I think your proposal of using 2^k moves to solve a k-color piece is
> good, because it basically means one can use a nested commutator with k
> layers to
>
> construct a pure 3-cycle for a kC piece. This coincide with my intuition. I
> wonder if the MC7D solvers have more insights. Andrey and Charlie, how do
> you
>
> guys solve the 7D pieces?
>
> (3) Let's assume we solve one piece at a time, with no parallelization.
> Actually, if one can do parallelization, but cannot achieve an exponential
> gain
>
> (solve a^n pieces at the same time for some constant a), it still cannot
> affect the big picture.
>
> Combine all these points, an estimate of the move count for solving a 3^n
> is about:
>
> summation_{k=0...n} 2^k * 2^k * (n choose k) = 5^n
>
> In this summation, there's actually a dominating term: k = 0.8n [footnote
> 3]. Solving the (0.8n)C pieces takes the most moves, which is about 5^n
> divided by
>
> a polynomial of n, which is essentially 5^n (note that I only care about
> the base of the exponential function). This estimate is tighter than a quick
> upper
>
> bound of 6^n, which can be obtained by noticing there are no more than 3^n
> pieces, each can be solved by no more than 2^n moves.
>
> My conjecture is that one cannot improve the base of the exponential
> function, e.g., reduce 5^n to 4.9^n. A rigorous statement would be:
>
> Conjecture: For any epsilon>0, there exists N>0, so that for all n>N, the
> god's number of 3^n is between (5-epsilon)^n and (5+epsilon)^n.
>
> Nan
>
>
> Footnote:
> [1]: ref: . Note that the
> m-dimensional boundary has (n-m) colors.
> [2]: Use the same method as in [3].
> [3]: Why k=0.8n dominates the number of moves:
> Take the estimate (n choose k) is approximately 2^(n* h(k/n)), where h() is
> the binary entropy function
>
> . The summation
> becomes:
>
> summation_{k=0...n} 2^(n* (2k/n + h(k/n)) )
>
> When n is large, what's important is the exponent. There's a dominating
> term in the summation, that is exponentially greater than all other terms.
> Since the
>
> function (2k/n + h(k/n) reaches it's maximum log5/log2 at k/n = 0.8, the
> (0.8n)-color pieces take most of the moves. The single term of k=0.8n
>
> One can use the same technique to see why (2/3*n) pieces dominate the
> number of pieces.

--001636456f8c3ccf4904a709c54c
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

Yes the ability of parallelization is hard to specify. It's also the key co=
ntribution of Demaine's paper.=20

An interesting interpretation of my calculation is as follows. The (2/3)n-c=
olor pieces are the most, but the number of moves per piece is not the grea=
test. The n-color pieces requires the most number of moves per piece, but t=
here'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 p=
ieces. Those are the hardest part.=20

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 r=
ather than the total number of moves. In that case (2/3)n-color pieces are =
the major difficulty.=20

Nan

--- In 4D_Cubing@yahoogroups.com, Roice Nelson wrote:
>
> Great stuff Nan!
>=20
> I experimentally observed last night that there was a maximum at
> (2/3*n)-color pieces, but my intuition was still telling me it wouldn't
> dominate (that a smearing of pieces would continue to contribute). Love =
it
> when my intuition gets put in it's place :D
>=20
> Here are piece count graphs I had made for
> 250and
> 500 dimensi=
onal
> Rubik's Cubes (I started overflowing double precision in the
> 600s). The cubie-count peak you calculated at 2/3rds is easy to see. Th=
e
> curve is wider on the latter in an absolute sense, spanning some 70
> significant piece types rather than 50. But as a proportion of the total
> number of piece types, I see now it is still getting thinner. So as
> dimension -> infinity, one can think about how this smooth peak approache=
s a
> spike!
>=20
> I love that you threw a conjecture out there too. All your reasoning loo=
ks
> great, and the only biggish question for me right now is the
> parallelization, and whether that could be leveraged to lower the base of
> the exponent. I'm going to go out on a limb and say it's possible. Afte=
r
> your analysis, it feels more tractable to investigate too, because we onl=
y
> need to parallelize one piece type.
>=20
> One thought on that is not using 3-cycles. Say you could generate a
> sequence that cycles a much larger number of pieces. You do preliminary
> moves to put a bunch of pieces in the correct place in this cycle, run it=
,
> then undo the preliminaries. I used this tactic with a 7-cycle of 3C pie=
ces
> on MC4D (in my glory days, when I used to still be in the running for
> shortest solutions). Maybe cycles of exponential length are even possibl=
e
> to take advantage of, since there are an exponential number of pieces to =
be
> solved. I'll think on this stuff more.
>=20
> seeya,
> Roice
>=20
> On Fri, Jul 1, 2011 at 3:31 PM, schuma wrote:
>=20
> > Hi Roice,
> >
> > Here's my calculation based on your suggestion:
> >
> > (1) The number of k-color pieces on a 3^n is 2^k*(n choose k). [footnot=
e 1]
> > In terms of the number, (2/3*n)-color pieces are dominating. [footnote =
2]
> >
> > (2) I think your proposal of using 2^k moves to solve a k-color piece i=
s
> > good, because it basically means one can use a nested commutator with k
> > layers to
> >
> > construct a pure 3-cycle for a kC piece. This coincide with my intuitio=
n. I
> > wonder if the MC7D solvers have more insights. Andrey and Charlie, how =
do
> > you
> >
> > guys solve the 7D pieces?
> >
> > (3) Let's assume we solve one piece at a time, with no parallelization.
> > Actually, if one can do parallelization, but cannot achieve an exponent=
ial
> > gain
> >
> > (solve a^n pieces at the same time for some constant a), it still canno=
t
> > affect the big picture.
> >
> > Combine all these points, an estimate of the move count for solving a 3=
^n
> > is about:
> >
> > summation_{k=3D0...n} 2^k * 2^k * (n choose k) =3D 5^n
> >
> > In this summation, there's actually a dominating term: k =3D 0.8n [foot=
note
> > 3]. Solving the (0.8n)C pieces takes the most moves, which is about 5^n
> > divided by
> >
> > a polynomial of n, which is essentially 5^n (note that I only care abou=
t
> > the base of the exponential function). This estimate is tighter than a =
quick
> > upper
> >
> > bound of 6^n, which can be obtained by noticing there are no more than =
3^n
> > pieces, each can be solved by no more than 2^n moves.
> >
> > My conjecture is that one cannot improve the base of the exponential
> > function, e.g., reduce 5^n to 4.9^n. A rigorous statement would be:
> >
> > Conjecture: For any epsilon>0, there exists N>0, so that for all n>N, t=
he
> > god's number of 3^n is between (5-epsilon)^n and (5+epsilon)^n.
> >
> > Nan
> >
> >
> > Footnote:
> > [1]: ref: . Note that =
the
> > m-dimensional boundary has (n-m) colors.
> > [2]: Use the same method as in [3].
> > [3]: Why k=3D0.8n dominates the number of moves:
> > Take the estimate (n choose k) is approximately 2^(n* h(k/n)), where h(=
) is
> > the binary entropy function
> >
> > . The summation
> > becomes:
> >
> > summation_{k=3D0...n} 2^(n* (2k/n + h(k/n)) )
> >
> > When n is large, what's important is the exponent. There's a dominating
> > term in the summation, that is exponentially greater than all other ter=
ms.
> > Since the
> >
> > function (2k/n + h(k/n) reaches it's maximum log5/log2 at k/n =3D 0.8, =
the
> > (0.8n)-color pieces take most of the moves. The single term of k=3D0.8n
> >
> > One can use the same technique to see why (2/3*n) pieces dominate the
> > number of pieces.
>

--bcaec52e634992fb1104a70b4a59
Content-Type: text/plain; charset=ISO-8859-1

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

--bcaec52e634992fb1104a70b4a59
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

--00032555a7b6056b5f04a70b917a
Content-Type: text/plain; charset=ISO-8859-1

I'd like to see results here as well, though it is a very different kind of
problem than the one Nan proposed.

Since I can't seem to help myself from making predictions, mine here is that
things will follow what happened for the 3^3. That is, the lower/upper
bounds will get squeezed together over an extended time (the upper bound
requiring more effort) using group theory arguments, but that the group
theory arguments will run out of steam. cube20.org has a tabular history of
the 20 year saga to find God's Number for Rubik's Cube. Since they had to
finish off the final gap with computers, which will be impossible for the
3^4, the exact answer may literally never be known. Maybe the 2^4 will be
tractable though.

I don't recall specific bounds being mathematically defended here before,
but I may very well have missed them or may be forgetting. Perhaps some
wiki pages for God's Algorithm are in order to begin collating what we know.
We could have separate pages for the asymptotic and low-dimensional
problems.

Take Care,
Roice


On Fri, Jul 1, 2011 at 4:41 AM, PAUL TIMMONS wrote:

>
>
> How about restricting oneself to God's algorithm for the 3^4 case? I
> wanted to get an
> idea for the likely length of God's algorithm (both in the QTM and the
> FTM). There must
> be some some heuristic results available now that the MC4D has been in use
> for some years now. Even more so I am interested in any results for the 2^4
> case in both metrics
> but in particular the quarter-turn one. Sorry if this information is in
> circulation elsewhere - too much information to sift through and too little
> time!
>
>

--00032555a7b6056b5f04a70b917a
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

Hi,

Let's assume that a k-color piece takes a^k moves on average. (previously w=
e assumed a=3D2) This might be the performance after using parallelization.=
I re-calculated the result.=20

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

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

Nan


--- In 4D_Cubing@yahoogroups.com, Roice Nelson wrote:
>
> Very interesting that the asymptotics change if you use macros or not.
>=20
> 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 piec=
e
> 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, i=
t
> seems safe to claim that will be the case.
>=20
> Roice
>=20
>=20
> On Fri, Jul 1, 2011 at 6:20 PM, schuma wrote:
>=20
> > Yes the ability of parallelization is hard to specify. It's also the ke=
y
> > 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 poi=
nt 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 piece=
s
> > rather than the total number of moves. In that case (2/3)n-color pieces=
are
> > the major difficulty.
> >
> > Nan
> >
>

Hi Roice,

Today I computed a lower bound for the god's number of 3^n, using a simple =
counting argument. And the lower bound is in the order of 3^n. It's much mu=
ch lower than our heuristic upper bound 5^n. Currently I don't know any way=
to improve the lower bound. So if I have to guess the asymptotics of the g=
od's number, I have to change my mind to believe that the upper bound 5^n i=
s very loose.=20

If the god's number is really ~ 3^n, then the best solution uses only sub-e=
xponential moves per piece to solve all the pieces. It means there's a huge=
room for improvement. Maybe the way to go is like in 3^3, Kociemba's algor=
ithm has nothing to do with 3-cycles but is related to subgroups and cosets=
.=20

Nan

--- In 4D_Cubing@yahoogroups.com, Roice Nelson wrote:
>
> I'd like to see results here as well, though it is a very different kind =
of
> problem than the one Nan proposed.
>=20
> Since I can't seem to help myself from making predictions, mine here is t=
hat
> things will follow what happened for the 3^3. That is, the lower/upper
> bounds will get squeezed together over an extended time (the upper bound
> requiring more effort) using group theory arguments, but that the group
> theory arguments will run out of steam. cube20.org has a tabular history=
of
> the 20 year saga to find God's Number for Rubik's Cube. Since they had t=
o
> finish off the final gap with computers, which will be impossible for the
> 3^4, the exact answer may literally never be known. Maybe the 2^4 will b=
e
> tractable though.
>=20
> I don't recall specific bounds being mathematically defended here before,
> but I may very well have missed them or may be forgetting. Perhaps some
> wiki pages for God's Algorithm are in order to begin collating what we kn=
ow.
> We could have separate pages for the asymptotic and low-dimensional
> problems.
>=20
> Take Care,
> Roice
>=20
>=20
> On Fri, Jul 1, 2011 at 4:41 AM, PAUL TIMMONS wrote:
>=20
> >
> >
> > How about restricting oneself to God's algorithm for the 3^4 case? I
> > wanted to get an
> > idea for the likely length of God's algorithm (both in the QTM and the
> > FTM). There must
> > be some some heuristic results available now that the MC4D has been in =
use
> > for some years now. Even more so I am interested in any results for the=
2^4
> > case in both metrics
> > but in particular the quarter-turn one. Sorry if this information is in
> > circulation elsewhere - too much information to sift through and too li=
ttle
> > time!
> >
> >
>

My estimates show that lower counting limit L for God's number for 3^N is=
2/9*N*3^N for QFTM (as implemented in MC5D and MC7D - with 2*N*(N-1)*(N-2)=
possible twists) and 3/4*3^N for FTM (where any twist of face is counted a=
s 1, so we have N!*2^(N-1) possible twists). Actual God's number is probabl=
y between L and 2*L.
By the way, if we take puzzle 2*1^N (with only one twisting face), its Go=
d's number in QFTM is N. But counting limit gives something like
N*(log(2*N)/(2*log(N)) that is N/2*(1+o(N)). So lower limit is almost the h=
alf of the actual number.

Andrey