## Rubik’s Cube, God’s Number and the Superflip

On the 22nd of November, 2015, a US teenager solved the 3×3 Rubik’s Cube in 4.90 seconds.

Sounds impressive, but if (like most people) you don’t have much experience of the Rubik’s Cube beyond hours and hours of frustration and despair, you probably won’t be able to put that figure into much context.

The number of different combinations (known as ‘permutations’) on the 3×3 version of the cube is 43,252,003,274,489,856,000. And the task of any would-be solver of the cube, whether a professional or bored teenager wanting to kill time, is to organise these into the 1 permutation considered the cube’s ‘solution’.

As most of us know who’ve tried the puzzle without first learning to solve it, this is – if you’ll excuse a major understatement – easier said than done.

Lucas Etter managed to take one of the 43,252,003,274,489,856,000 permutations of the Rubik’s Cube, and convert it into another of these 43,252,003,274,489,856,000 in under 5 seconds.

An interesting aspect of the Rubik’s Cube is something known as ‘God’s Number’. This is the greatest number of moves needed to solve the hardest possible permutation of the cube. In other words, any permutation can be solved in 20 moves or less.

The most difficult permutation to solve is called the superflip (see right). This is the furthest away from being solved that you can get. It was proven that this permutation could not be solved in anything less than 20 moves. Even with the best computer program in the world, no combination of 19 moves can solve the cube in this position. It has to be 20. This is what led to the consideration the 20 was God’s Number. Of course, as with any mathematical conjecture, it’s not enough just to assume that it is true. You actually have to prove it.

It took a long time to prove this – after all, it’d be impossible to check all 43,252,003,274,489,856,000 permutations. Wouldn’t it? Well, that – in effect – is exactly what was done. Almost. The number of combinations they needed to check was gradually whittled down as it was realised that some permutations are effectively identical. Turn a scrambled Rubik’s Cube upside down, and it still has the same permutation. It’s just – well – upside down. As the number of cases needed to be checked was gradually reduced, the computers and programs used became more and more powerful – powerful enough to check every single permutation. This was done at Google’s Headquarters in San Francisco. This method of checking every available option is called a proof by exhaustion. This is an apt name – finding the proof by this method is, after all, absolutely exhausting.

But the 3×3 is not the only kind of Rubik’s Cube. The largest cube used in competitions is the 7×7 (the ‘V-Cube 7′). I thought about learning to solve this one before learning that it’s only got a small matter of 19 500 551 183 731 307 835 329 126 754 019 748 794 904 992 692 043 434 567 152 132 912 323 232 706 135 469 180 065 278 712 755 853 360 682 328 551 719 137 311 299 993 600 000 000 000 000 000 000 000 000 000 000 000 combinations.

I think I’ll stick with the 3×3.