Message #1805

From: schuma <mananself@gmail.com>
Subject: [MC4D] Re: God’s Number for n^3 cubes.
Date: Thu, 30 Jun 2011 07:45:50 -0000

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 introduction and glanced through the rest. I apologize if there’s any mistake.

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

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

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

Let’s ask an easier question. Let’s say we only care about nxnxn for very large n. If n = 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 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.

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 constant 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 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 authors 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 number for n=1000 is 5 million or 7 million, they don’t know. If you ask the god’s number for n=5, 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 solve 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 gather 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 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 (constant* n^2) turns. This kind of algorithms is referred to as "folk algorithms" in this paper.

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

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 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 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. This is very interesting but I don’t know the details yet. I have no idea how their algorithm works.

They considered three variations of puzzles:

(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 <http://www.shapeways.com/model/96696/overlap_cube_2x2x23.html>, where c1=c2=2 and n=23. For this type of puzzles, they have a good news that there exists an efficient method to find the optimal solution from arbitrary starting state. But this good news can not be extended to nxnxn or nxnx1. Actually 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.

Summary of key results:

(1) For the important puzzle nxnxn, they found the order-of-magnitude of the god’s number. For example, if n=1000, they know the god’s number is about millions.

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

(3) 23x2x2 is easy to solve optimally, but 23x23x1 is hard to solve optimally.

Melinda, I searched through the document using the word "software". The only 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 were talking about.

Nan

— In 4D_Cubing@yahoogroups.com, Melinda Green <melinda@…> wrote:
>
> I knew that I knew him from somewhere too, and after digging, discovered
> that he featured in a nice PBS documentary
> <http://www.greenfusefilms.com/index.html> 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
>