Message #1810
From: PAUL TIMMONS <paul.timmons@btinternet.com>
Subject: Re: [MC4D] Re: God’s Number for n^3 cubes.
Date: Fri, 01 Jul 2011 10:41:46 +0100
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!
— On Fri, 1/7/11, Roice Nelson <roice3@gmail.com> wrote:
From: Roice Nelson <roice3@gmail.com>
Subject: Re: [MC4D] Re: God’s Number for n^3 cubes.
To: 4D_Cubing@yahoogroups.com
Date: Friday, 1 July, 2011, 5:52
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
Roice
On Thu, Jun 30, 2011 at 10:16 PM, Roice Nelson <roice3@gmail.com> wrote:
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 and counts for a 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