We've all seen the algorithms for solving Rubik's Cube by hand using a step-by-step approach: get all the corners done, then get the side cubelets done. Or: do a complete side, then do the next one, then the next.
There are several approaches and, by dint of some fairly rigorous practice, experts can solve a cube in under a minute. But how jumbled can a cube get? Or, to put it another way: what's the minimum number of moves necessary? Enter God's Algorithm.
Way back when, I studied mathematics at Kings College, London. Every year, in the summer term, the Mathematical Society organised a weekend away in Windsor Great Park, where we'd invite guest speakers to present topics we wouldn't normally encounter in our regular maths courses.
Gleaning the cube
In 1979, we had Professor David Singmaster as our guest. His topic was a brand-new toy called Rubik's Cube – not yet officially available in England – and the use of combinatorial mathematics to solve it.
The cube had been invented by Erno Rubik in Hungary some five years previously and at that point Ideal Toys were just on the verge of licensing the cube from Rubik for worldwide distribution. Singmaster had a set of cubes with him that we could buy and, needless to say, after his talk he sold the lot.
Within a couple of months, I'd got the art of solving a cube sufficiently practised that I could regularly solve one within a couple of minutes. As we were maths students, we understood the mathematics behind the cube.
The initial solution that Singmaster discovered used combinatorial mathematics to solve it. In essence, he'd devised a set of combined moves (let's call them Moves, each containing about seven to 12 individual face rotations), that would move around three corners or three sides.
All of the Moves were of the form aba' – that is, a set of rotations a, followed by a single rotation b, followed by the reverse set of rotations that formed a.
Instead of hopelessly randomising the cubelets, the Moves were designed to only swap the positions of three cubelets around. By identifying three cubelets that were out of position, you could solve the cube by repeatedly applying these Moves.
I practised two Moves by heart – one to swap three corners, one to swap three side cubelets – until I could do them in my sleep. With my tuned cube, that meant I could solve a random position in about two minutes. That's not a brilliant time to be sure, but acceptable.
Two questions left open at that time were: how randomised could you make the cube, and what would be the optimal number of moves that an omnipotent solver – in other words a solver who could perfectly analyse the cube – would take in order to render the cube to its default state?
Obviously our combinatorial solution would require many moves – possibly 100 – but what about if you could visualise the solution perfectly? 10? 20? 42? This optimal cube analysis became known as God's Algorithm, not because there is such an algorithm necessarily, but because it gives us something to aim for in our ever-better algorithms for solving the cube.
Back in 1982, Singmaster hypothesised that God's Algorithm might only need a number of moves "in the low twenties", but he was unable to refine that hypothesis much further.
The magic cube
Before we can even begin to solve the cube, we need some notation so that we don't drown in descriptive phrases. Even today, we still use the same notation devised by Singmaster back in 1982 in his book Notes on Rubik's Magic Cube.
The Cube consists of three types of cubelets, assembled together with what looks to be utter magic in a 3 x 3 x 3 cube.
There are 12 edge cubelets, each with two faces of different colours.
Similarly, there are eight corner cubelets, each with three visible faces, with each face a different colour. Finally there are six centre cubelets each showing one face.
The centre squares form the sprung matrix that holds it all in place.
These centre pieces define the colour of their sides in the solved state. Hold the cube in front of you, such that there is one side directly facing you. The six sides of the cube are called Front, Back, Left, Right, Up and Down.
We use Up and Down instead of Top and Bottom because we're about to use the initial letters to signify the rotations of their respective face, and to use both Bottom and Back in this case would clash confusingly.
The letters F, B, L, R, U and D denote a clockwise quarter-turn of the respective face. By clockwise we refer to the direction you rotate the face if you were looking directly at it. A half turn of a face is denoted by either repeating the letter (for example, FF or UU) or by squaring the letter (such as B2 or R2).
A quarter-turn anti-clockwise is denoted by using a prime mark or apostrophe (such as D' or L'). Of course, a quarter-turn anticlockwise could be denoted by repeating a letter three times, but this is rarely seen.
As an example, here's how to get the simple crosses pattern from a default cube: L2R2U2D2F 2B2 (or LLRRUU DDFFBB). To return to the solved cube, just reverse the moves.
For the cleverer looking centre dots pattern, try L'R•U'D•B'F•L'R (here I've separated the moves in pairs to make it easier to see what's going on). Again, to return to the pristine cube, just reverse the moves.
Singmaster's original solution was in three main stages: First, choose a colour (I always go for white as it's the most visible) and then restore that particular face. In general, you do this by first restoring the edge cubelets and then the corner cubelets.
CROSS PATTERN: Putting the Cross pattern on the Rubik's Cube can set you up for some quickfire puzzle-solving
Second, restore the middle layer. This of course means making sure the four edge cubelets are properly positioned and in the correct orientation.
Third, restore the final face. Singmaster did this part in four main phases: flipping the edge cubelets so that they all showed the final colour, forming a cross with the centre cubelet (of course, they could be in the wrong position); restore the edge cubelets to their proper position; place the corner cubelets in their proper position (although they may be oriented incorrectly); twist the corners until they are in the correct orientation.
Singmaster's algorithm was guaranteed to solve the cube, but the number of moves was not optimal in any sense of the word. It could take over 100 moves to solve the cube using his algorithm.
Once Singmaster had published his algorithm (a solution that required you to learn six basic Moves and then apply them over and over), the race was on to reduce the number of moves drastically in order to solve the cube more quickly.
Quite soon after Singmaster published his initial book, Jessica Fridrich devised a four-pass algorithm known as CFOP (Cross, First two layers, Orient last layer, Permute last layer) that proved to be extremely fast for the new sport of speedcubing – that is, solving the cube very fast in competitions.
Unfortunately, the algorithm requires the knowledge and use of some 120 Moves, but offset against that a practiced speedcuber can analyse and solve a randomised cube in about 55 rotations.
Picking up speed
Philip Marshall then described an algorithm that only required learning two Moves (plus the art of knowing how to recognise when to apply them), but that would solve the cube in somewhere around 65 moves.
It's a five-step process: Cross, centre section edges, top edges, five corner pieces, end game. Next up was Lars Petrus' method, which he devised at roughly the same time as everyone else in the early '80s.
He decided to avoid the traditional layered approach used by everyone else and to restore the cube from one corner, building it out via a solved 2 x 2 x 2 cube, to a 2 x 2 x 3 rectangular block (otherwise known as a cuboid) to the completed cube.
Although the first few passes use several types of Moves, the final stages of the Petrus System only use three. Overall the cube can be solved in 45 moves, provided that time is available to study the cube in advance.
In speed contests, the number of moves increases somewhat to something in the region of 60 moves because there's less time to study the cube in order to devise the most efficient solution. Apart from some tweaks of these methods over the years, that's where human-solving now stands.
The fastest speedcubers use some variant of these methods. But what about computer solutions? Can they get closer to God's Algorithm through lengthy analyses of the randomised cube?
The first approaches were made by professor Morwen B Thistlethwaite at the same time as Singmaster was explaining his method, and were published in Scientific American in 1981 by Douglas Hofstadter. In essence, Thistlethwaite divided up the solving process into subproblems.
Rather than concentrating on solving portions of the cube and endeavouring to not jumble up those parts as you tried to solve the remainder of the cube, he concentrated on the kinds of moves you were allowed to make. To do this, he made use of group theory and searching by computer.
He started off with what's known as the cube group. This is a mathematical group whose operations are all the usual moves we've discussed here: F, B, L, R, U, D and the moves obtainable from them (F 2, F', B2, B' and so on).
The number of possible positions in this cube group is immense: 4.3 x 1,019. He then posited another smaller group, one that only allowed the following moves: L, R, F, B, U2 and D2 . Next he worked out a set of tables of the Moves that would take the cube from the larger group to the smaller group.
Once in this smaller group, he devised yet another smaller group that only allowed L, R, F 2, B2, U2 and D2, and then worked out how to transform the cube into a member of this group. From there he went to the next more restrictive group that only allowed L2, R2, F2, B2, U2 and D2. From this particular group it was a small search that led to the final and smallest group of all: the identity group (the solved cube).
It is important to note that Thistlethwaite's algorithm requires many searches at each step down the group chain and is only feasible for computers to do, not humans. Using this algorithm, it is possible to solve the cube in a maximum of 52 moves.
Nearing God's algorithm
The final improvement was made by Herbert Kociemba in 1992. He built his algorithm based on Thistlethwaite's by removing most of the interim groups. Kociemba's algorithm just used three groups: the cube group, the U, D, F2, B2, L2 and R2 group, and the identity group.
He called it a two-phase algorithm, because you transform the cube into a member of the smaller group, and then transform that into the only member of the identity group.
The important thing about the U, D, F2, B2, L2 and R2 group is that the orientations of the corners and edges cannot be changed using those particular operations.
Furthermore, the edges in the middle slice between the Up and Down faces stay within that slice. The first phase uses a modified A* search algorithm known as iterative deepening A* (or IDA) in order to find the moves that will constrain the corners and edges (and the middle slice) of the cube to fit into the second group.
The second phase then searches for the moves to solve the cube using only the restricted moves allowed. In fact the algorithm is a little cleverer than it may at first appear: it solves the cube multiple times in order to find the shortest solution path available.
First it uses the shortest path provided by the first search and transforms the resulting cube to the solved state. Then it uses the less successful paths from the original search and tries to transform those to the solved state.
After completing this process, it chooses the shortest path it finds as the solution. In general, it finds a path that is 20 moves or shorter to solve the cube. Note however, that the shortest path it finds is not necessarily guaranteed to be the most optimal solution.
So, Kociemba's Algorithm, although very effective, can only ever approximate God's Algorithm. We're still waiting for that one.
First published in PC Plus Issue 298
Liked this? Then check out Why computers suck at maths
Sign up for TechRadar's free Weird Week in Tech newsletter
Get the oddest tech stories of the week, plus the most popular news and reviews delivered straight to your inbox. Sign up at http://www.techradar.com/register