God’s Algorithm

rubik iconostasis

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.

One Comment to “God’s Algorithm”

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.