God’s algorithm is a notion originating in discussions of ways to solve the Rubik’s Cube puzzle, but which can also be applied to other combinatorial (sequential move) puzzles and mathematical games. It refers to any algorithm which produces a solution having the fewest possible number of moves, the idea being that an omniscient being would know an optimal step from any given configuration. The notion applies to puzzles that can assume a finite number of ‘configurations,’ with a relatively small, well-defined arsenal of ‘moves’ that may be applicable to configurations and then lead to a new configuration.
An algorithm for finding optimal solutions for Rubik’s Cube was published in 1997 by computer scientist Richard Korf. While it had been known since 1995 that 20 was a lower bound on the number of moves for the solution in the worst case, it was proved in 2010 through extensive computer calculations that no configuration requires more than 20 moves. Thus 20 is a sharp upper bound on the length of optimal solutions. This number is known as God’s number.
The Daily Omnivore 