Monday, 9 March 2015

Why Is It So Hard to Solve a Rubik’s Cube?

by Henry Ling



Our greatest weakness lies in giving up. The most certain way to succeed is always to try just one more time” (Thomas Edison)

The Rubik’s cube, first invited by Mr Ernő Rubik in 1974, is one of the most well-known puzzles today, and I’m sure the majority of people will have one in their home, either unsolved and gathering dust on a shelf or in the attic, or solved due to much thought and much labour (or the cheap trick of peeling off the stickers). 

At the age of 8, I became very interested in this 3D combination puzzle of the 1980s and spent many hours working out how to solve it. However, since then I have managed to solve it numerous times, using a set of steps starting by solving the first face with all pieces orientated in the correct manner, and then working my way up to the top layer. Nowadays I have an average of a 45 second solve, for the regular 3x3x3 Rubik’s cube, which sounds great, until you take a look at the world record which accounts to an outstanding 5.55 seconds (by Mats Valk from the Netherlands). 

However, without a photographic memory, getting ridiculously short times proved to be challenging and soon the regular 3x3x3 became relatively dull to me. However, I managed to satisfy my appetite through a variety of other 3D puzzles, all of which were spawned from the one invention of Mr Rubik. Cubes today range from 8x8x8 Rubik’s cubes to ones with shapeshifting qualities. The principles of the 3x3x3 can be applied to the majority of these other cubes which led me, like many others before me, to solve these impeccable puzzles.

What I find most interesting, though, about the Rubik’s cube is the mathematics behind it. 

Being a person who enjoys a good bit of maths, naturally that would arouse my curiosity. People always find it hard to solve the Rubik’s cube and many people just keep turning the layers, hoping that they will eventually fit into place. I then wondered: what is the possibility of solving the Rubik’s cube, purely by chance alone? The first thing I then did was work out how many possible orientations of the Rubik’s cube are available.  Any of the 8 corner pieces can reside in one of the corner slots, therefore 7 corner pieces could reside in one of the other corner slots, 6 corner pieces for the next corner slot, and so on. Therefore for the positioning of the corner pieces you get 8x7x6x5x4x3x2x1= 8! Each corner piece can then go into each slot in 3 different ways (as each corner piece consists of three colours), as there are 8 different corner pieces we get 38 different ways of orientating each corner piece. If you then apply the similar method of working to the edge pieces (N.B the centres can’t move so they aren’t necessary), you can see that there are 12! possible positioning’s as each edge piece can be placed in 12 different places. Moreover there are only 2 possible orientations of the edge piece giving 212 possible orientations. If you then times all this together, 382128!12!,  it gives one 5.19 x 1020 (519 quintillion) possible configurations of the Rubik’s cube. Phew! That is indeed a very large number of possible configurations, so you can already see, that solving this without any method or help will prove extremely challenging, however not all hope is lost for not all those configurations are physically possible due to the nature of the cube. The total number of states is actually yielded by a set of values obtained by a robot programmed to execute a set of random 90 degree turns on a regular Rubik’s cube. What this resulted in was a multiplication of 227 x 314 x 53 x 72 x 11, which gives a final answer to the total number of cube positioning as    43, 252, 003, 274, 489, 856, 000 or 43 quintillion.

One could also bring in the second law of thermodynamics to help show the improbability of obtaining a solved cube, although this is theoretical and the reality is not the case. The law states that in a thermodynamic process, there is in an increase in the sum of the entropies of the participating systems. In terms most people are more likely to understand; a system tends to move from a state of order to a state of disorder. So this could be the scrambling of the cube, it goes from a state of order, solved with all pieces in their correct places, to a state of disorder, where all the pieces are in a completely jumbled up state. So this makes it very hard to solve the Rubik’s cube without external thought around where the pieces are supposed to go, and thought around algorithms to place the pieces in their correct slots.
Mentality is one of the other problems people face when trying to solve the Rubik’s cube, if you don’t have a desire to solve it, you are unlikely to solve it, and it is one of those things which takes time and effort. Most people don’t have the patience to solve the Rubik’s cube and thus it gets strewn across the room in a fit of rage and anger. What people also don’t understand is that there is a logic behind solving the Rubik’s cube, it cannot be done by simply twisting the layers round and round. One of the other things people ask me about the Rubik’s cube, is “is there a set of moves which you repeat and will always get the cube into the right place?” well no you cannot do just a string of 4 moves over and over to solve the cube for the reason I mentioned earlier, there is about 43 quintillion different ways the pieces can be represented, this means one cannot simply do one algorithm over and over. 

I would love to give a full tutorial right here about how the cube can be solved, however it will take too long to transmit to words. However I can give you a brief overview to get you on your way. 


Start by picking a face to start solving, for example white. Find the white centre of on the cube, and form a white cross around that centre with edge pieces, this can be done by a few simple 90degree turn moves. Once you have the cross, check the orientation of your edge pieces. Is the white and red edge piece in line with the white centre and the red centre, if not make a 180 degree turn to put that piece on the top layer and turn the top face round to line up the red, and make another 180 degree turn to put it in place. That’s the easy bit. Now work on the corners get them in the right places again, by simple 90 degree turns of the top face and the side faces. Right, now your own your way. The real key to solving the Rubik’s cube though is understand what each turn move does and develop from that, ways of moving pieces around the cube, while making sure other pieces move back into their original positioning. Or if you’re really desperate I am sure there are many a video on YouTube describing how it can be solved.

All of these things make a very challenging puzzle but recent research has made an amazing discovery. Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge, proved that a regular 3x3x3 Rubik’s cube can be solved in 20 moves or less from any start position. This is incredible news and makes the number of moves I take look stupid, for on average I take about 105, 90degree turns of the cube in one solve, considerably more than 20. However to this you will have to memorize the algorithms for each of the 43 quintillion different possibilities of starting positons, as appose to my method of solving layer by layer. The way that this was discovered by that group of people, was through a branch of mathematics known as group theory. I would like to go into the gory details, but it would require me to give a vast amount of detail into notation and theory, which would take far too long, however look online for a paper on Group Theory and the Rubik’s Cube if you are interested, it is written by Janet Chen. Back to how it was done. They first split the 43 quintillion into 2,217,093,120 sets of 19,508,428,800 different positions. Each set was able to be worked out using a computer, and a variety of Cosets of the group formed by {U,F2,R2,D,B2,L2}, where U is the upper layer of the cube, F2 is the front face, R2 is the right face, D is the bottom face, B2 is the back face, and L2 is the left face. The number of sets needed to be solved was cut down to 55,882,296 due to symmetry around the cube. They then used a number of superfast computers to rapidly go through each set and calculate the shortest number of moves to solve it. They then used this to prove the number of moves it takes to solve the cube from each start position. The results are represented in the table below. Where distance is the number of moves from the start position.  
The number of moves to solve the Rubik cube has also be represented by Erik Demaine as  where n is the number of layers in a (n*n*n) Rubik’s cube, and  is a constant.
As you can see the Rubik’s cube requires a lot of thought and patience in order to complete, however it can be done and has on many occasions been done by your average Joe, such as myself. However when you delve into the maths behind the Rubik’s cube things become even more complicated. And to motivate you in all that you do, be the Rubik’s cube, an area of your course you find hard, a musical instrument or anything. 


Distance
Count of Positions
0
1
1
18
2
243
3
3,240
4
43,239
5
574,908
6
7,618,438
7
100,803,036
8
1,332,343,288
9
17,596,479,795
10
232,248,063,316
11
3,063,288,809,012
12
40,374,425,656,248
13
531,653,418,284,628
14
6,989,320,578,825,358
15
91,365,146,187,124,313
16
about 1,100,000,000,000,000,000
17
about 12,000,000,000,000,000,000
18
about 29,000,000,000,000,000,000
19
about 1,500,000,000,000,000,000
20
about 490,000,000

1 comment:

Comments with names are more likely to be published.