Pressing Toward the Prize

God’s Number?

Posted on: December 4, 2010

I recently came upon an article in Math Horizons magazine (Nov. 2010) that caught my eye: The Quest for God’s Number. Now I never knew God had a number, so I thought I better stop and check it out. The first thing I discovered is that God’s number is linked to God’s algorithm… who knew?

What this really has to do with is solving a Rubik’s Cube in the fewest moves, and hence the shortest amount of time. According to the article by Rik van Grol, “God’s algorithm is the procedure to bring back Rubik’s Cube from any random position to its solved state in the minimum number of steps. The maximum of all minimally needed number of steps is referred to as God’s number. This number can be defined in several ways. The most common is in terms of the number of face turns required, but it can also be measured as the number of quarter turns… Earlier this year, after decades of gradual progress, it was determined that God’s number is 20 face turns. Thus, if God’s algorithm were used to solve the cube, no starting position would ever require more than 20 face turns.” The article chronicles the process used to determine that God’s number is 20, and as one might imagine, it involves looking at an astronomically large number of possible pattern combinations, more than 4.3 x 10^19.

It was interesting to find that one of the mathematicians working on lowering the upper bound in search of God’s number used group theory in his calculations. He used the cube group, similar to the shape groups we studied in Abstract Algebra. His group had 6 moves on a cube fixed in space, Left, Right, Front, Back, Up, and Down, and the group operation was concatenation. He then divided the cube group into a nested chain of subgroups, and created an algorithm to eliminate some of the moves early on in the process. Using this method, he was able to show that the Rubik’s Cube could be solved in at most 85 moves. This was in 1979. By January of 1980 he had reduced it to 80, and by the end of that year, to 52. In 1995, another mathematician brought the upper bound to 29 face turns, but it was not until July of this year that the upper bound met the lower bound at 20.

Now that they have found God’s number for the classic 3x3x3 cube, they have turned their attention to the 4x4x4, 5x5x5, 6x6x6, and 7x7x7 cubes, all of which are currently on the market. There might be a hitch in this, though, since the 7x7x7 cube has 2.0 x 10^160 possible positions. Good luck with that!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


    • gramsonjanessa: I can't wait to listen to your capstone presentation in the spring! Your proposal was really interesting and I'm interested to see how the linear alge
    • dewittda: This is impressive! I thought I was good because I solved a rubik’s cube once in an hour. I served with a guy in the Air Force who could solve a r
    • ZeroSum Ruler: The Euclidean algorithm should me the mainstream way we teach students how to find the GCF. Why isn't it? A mystery.

    Categories

    %d bloggers like this: