God's number: solving every one of 43 quintillion Rubik's Cube positions.

With the Kannada film Kantara taking cinemas by storm, I was wondering whether there is something to do with God in math as well. Well, that's precisely what we discuss in story #51: God's number, and God's algorithm.

God's algorithm is a notion that originated in discussions of ways to solve the Rubik's Cube, but it applies to other combinatorial puzzles and mathematical games too. It refers to any algorithm which produces a solution in the fewest possible moves. The allusion to God rests on the assumption that only an omniscient being would know the optimal step from any given configuration.

The Rubik's Cube — one of the world's best-selling toys — is a 3-D puzzle invented by Ernő Rubik in 1974. There are 43,252,003,274,489,856,000 possible arrangements of the cube.

With about 35 CPU-years of idle computer time donated by Google, a team of researchers essentially solved every position of the cube. Every position can be solved in 26 quarter-turn moves or fewer (or 20 moves, if a half-turn counts as one move).

Every solver uses an algorithm — a sequence of steps for solving the cube. One algorithm might use a sequence of moves to solve the top face, then another to position the middle edges, and so on. There are many different algorithms, varying in complexity and number of moves, but the ones a mortal can memorise typically need more than forty moves.