Home »

Has God's Algorithm been discovered yet?

Submitted by TonyVarden on Mon, 02/28/2005 - 10:42.
I apologize if this question is too elementary for your group. My sister is a math teacher & is trying to find the answer for her class. Has an algorithm been discovered that will solve any configuration of the cube in smallest possible number of moves? What is the smallest number of moves that will solve any configuration? Thanx much for any help.
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

The answer is yes

Submitted by cubex on Mon, 02/28/2005 - 18:35.
Optimal programs to solve specific cube positions started to appear in 1997 from two people: Herbert Kociemba and Richard Korf. You can read about it here: Progress in Solving Algorithms.

The idea of solving the cube using a series of nested subgroups was first proposed by Morwen B. Thistlethwaite. An earlier near-optimal algorithm by Herbert Kociemba was posted to cube-lovers in May 1992 which was able to solve all cube positions in 21 moves (q+h) or less. One can read about this in the cube-lovers archives cube-mail-08.

Various God's Algorithm calculations have been completed (click on the lemniscate to the right) but no one has exhaustively analyzed all the 4.3x10^19 positions of the 3x3x3 cube. According to a poll most people think that an exhaustive search of the cube could become possible in 25 years or more.

You can read more about Mr. Kociemba's program on his web page: Herbert Kociemba's Cube Explorer

> What is the smallest number of moves that will solve any configuration?

That is still unknown but we know it is at least 20 q+h turns or face turns. So far, no position has required more turns than that but we haven't tried all the positions, there are far too many.
» login or register to post comments

There are two possible meanin

Submitted by jaap on Thu, 03/03/2005 - 02:49.
There are two possible meaning's of God's Algorithm:
A. Every position has been solved optimally.
B. Any position can be solved optimally (within a reasonable time).

Personally I think A is the real God's Algorithm. As explained above, we have B but not A.

> An earlier near-optimal algorithm by Herbert Kociemba [...]
> was able to solve all cube positions in 21 moves (q+h) or less.

Just to clarify, it was able to solve all positions given to it in that many moves.

It has been proven that 29 face turns is certainly enough to solve any position, but it is thought that the actual worst case is around 20-23 turns.


Jaap's Puzzle Page:
http://www.geocities.com/jaapsch/puzzles/
» login or register to post comments