The Rubik Cube and God's Algorithm

Jack Dikian

Sep 2006

Introduction

In 1974 Erno Rubik, an admirer of geometry and 3-D forms created the world's most perfect puzzle. More than 30 years later the Rubik's cube is still a best selling brainteaser. By the mid-eighties almost every child had the puzzle. Did I say “Child”? I certainly was playing with one when I was about 12 or 13 with little success in solving.

So you can imagine our astonishment when a whole first year pure mathematics class was asked to go out and purchase the puzzle from the university co-op bookshop. I think, like others, I had always suspected that there would a mathematical approach to solving the puzzle. After all, many real-world, albeit, obscure problems such as the four-color map(1) and The Seven Bridges of Konigsberg(2) inspired rigorous mathematical solutions. I, off course didn’t have the mathematical repertoire – instead the brute force method, not in the mathematical sense, was always adopted.

Background

The Rubik’s Cube has a straightforward basis. The faces of the cube are covered by nine stickers in six colours. The puzzle is solved, when each face is of one solid colour. When you start to rotate the rows and columns and see the different mix of colour rows/columns you begin to appreciate the difficulty involved. There is, in-fact, 43 million million possible pattern combinations - but just one right one.

it's been proven that you can solve a Rubik's cube in 26 moves. Computer science professor Gene Cooperman and graduate student Dan Kunkle of the Northeastern University in Boston used algebra and fast parallel computing to show that no matter how scrambled the cube is, it is possible to solve (generate a cube with solid colors on each face, or the home state) in 26 steps. There are however claims that it can be solved in 22 or even 20 steps (see later).

The Rubik's cube has served as a guinea pig for testing techniques to solve large-scale combinatorial problems. "The Rubik's cube has been a testing ground for problems of search and enumeration. Search and enumeration is a large research area encompassing many researchers working in different disciplines — from artificial intelligence to operations. The Rubik's cube allows researchers from different disciplines to compare their methods on a single, well-known problem.

Mathematically

There are many algorithms to solve scrambled Rubik's cubes. It is not known how many moves is the minimum required to solve any instance of the Rubik's cube, although the latest claims put this number at 22. This number is also known as the diameter of the Cayley graph of the Rubik's Cube group. An algorithm that solves a cube in the minimum number of moves is known as 'God's algorithm'. Most mathematicians think it may only takes 20 moves to solve any Rubik's cube – and it’s a question of proving this to be true.

Any state of the cube corresponds to a permutation of its facelets — a rule that assigns to each facelet in the home state a new location on the cube in the scrambled state. Not every permutation of facelets can be achieved by a sequence of moves — for example no move can shift the centre facelet of a face — so when trying to solve Rubik's cube you restrict your attention to a collection of legal permutations.

These form a self-contained system. If you follow one legal permutation by another, the end result is also a legal permutation. If you've done one legal permutation, you can always find another one — namely the reverse of what you've just done — that will get you back to the position you started with. Doing absolutely nothing to the cube is also a legal move and corresponds to the permutation that leaves every facelet where it is, known to mathematicians as the identity permutation.

The problem of solving Rubik's cube can be visualised using what is called the group's Cayley graph — a network whose nodes are the legal states of the cube (corresponding to legal permutations) and which has two nodes linked up if you can get from one to the other by a legal move, which, incidentally, is itself a permutation. The home state of the cube corresponds to one of the nodes (and the identity permutation) and solving the cube corresponds to finding a path from one of the nodes to the home state along a sequence of linked-up nodes.

A brute-force approach to showing that you can always solve the cube in N moves would be to show that no such path involves more than N steps. This sounds good in theory, but there is a huge problem as the Cayley graph of the group of legal permutations has 43,252,003,274,489,856,000 nodes, a number that challenges even the fastest of supercomputers.

The (3 x 3 x 3) Rubik's Cube has eight corners and twelve edges. There are 8! (40,320) ways to arrange the corner cubes. Seven can be oriented independently, and the orientation of the eighth depends on the preceding seven, giving 37 (2,187) possibilities.

There are 12!/2 (239,500,800) ways to arrange the edges, since an odd permutation of the corners implies an odd permutation of the edges as well. Eleven edges can be flipped independently, with the flip of the twelfth depending on the preceding ones, giving 211 (2,048) possibilities.

There are exactly 43,252,003,274,489,856,000 permutations. The full number is 519,024,039,293,878,272,000 or 519 quintillion possible arrangements of the pieces that make up the Cube, but only one in twelve of these are actually solvable. This is because there is no sequence of moves that will swap a single pair of pieces or rotate a single corner or edge cube.

(1) This problem is sometimes also called Guthrie's problem after F. Guthrie, who first conjectured the theorem in 1852. The was then communicated to de Morgan and thence into the general community. In 1878, Cayley wrote the first paper on the conjecture.

(2) One of these areas is the topology of networks, first developed by Leonhard Euler in 1735. His work in this field was inspired by the following problem: The Seven Bridges of Konigsberg.