Number crunching

Ok, I am seriously confused about this one…

The BBC reports this morning that some (obviously very bored) computer scientists have used their supercomputer to work towards an ultimate solution of the fabled Rubik’s Cube. Its something to do with finding the minimum number of moves needed to solve the puzzle.

rubiks cube

Now, aside from questions as to how on earth they got a research grant for this, the line in the story that jumped out at me was this:

“It took some smart thinking by graduate student Daniel Kunkle and Gene Cooperman from Northeastern University in Boston to come up with the proof because cranking through the 43 billion billion possible Rubik’s cube positions would take too long even for a supercomputer”

Excuse me?!? 43 billion billion combinations?!?!

A Rubik’s Cube has 6 faces, each split in to 9 pieces. Now, even not taking into account the fact that many of these face pieces are joined to adjacent pieces on other faces, surely the maximum number of combinations is 96 = 531441 (not 43,000,000,000,000,000,000)?

Somebody tell me what’s wrong with my maths…


5 thoughts on “Number crunching

  1. Andy mate… Your maths wrong.

    Wiki ('s_Cube) has “A normal (3×3×3) Rubik’s Cube can have (8! × 3^(8−1)) × (12! × 2^(12−1))/2 = 43,252,003,274,489,856,000 different positions (permutations), or about 4.3 × 10^19, forty-three quintillion (short scale) or forty-three trillion (long scale), but the puzzle is advertised as having only “billions” of positions, due to the general incomprehensibility of such a large number to laymen. Despite the vast number of positions, all Cubes can be solved in twenty-six or fewer moves (see Optimal solutions for Rubik’s Cube).”

    I’d have to sit down and review my probability studies to confirm their numbers but if wiki says so it must be true 😉

  2. OK, so the mighty Wikipedia agrees with the BBC, but it doesn’t really tell you why. My proability is suffering from years of underuse, but I’m still floored by the sheer number of combinations here…
    Thanks for the link DJ

  3. mikew says:

    To calculate the number of possible configurations on the cube, note that corners always go to corners, edges to edges, and the centers remain centers. So we just have to calculate how many of these moves are possible. With the 8 corners, there are 8! = 40,320 possible rearrangements (if they’re all possible; more about that in a minute), and each corner has 3 different possible orientations, so there can be 3 to the 8th possible orientations of the corners.

    However, with the way the cube works, not all of these orientations are possible. It’s only mildly difficult to prove that once the first 7 corners are oriented, the orientation of the 8th is determined uniquely, so there are only 3 raised to the 7th power, or 2,187, orientations possible. Therefore, the number of possible arrangements of the corners, is 40,320 X 2,187 = 88,179,840. By the same kind of analysis, we can see that there are, among the 12 edge pieces, 12! = 479,001,600 ways to locate the edges, but on the actual cube once 11 of these are set the location of the 12th one is fixed (you can’t swap only two edges), a fact that can be proved by noting that a certain kind of parity among the edges is preserved by every rotation, so there are half this many ways of arranging the edge pieces, or 239,500,800 in total. But each edge can be in either of two orientations in its position, so you have to multiply this number by 2 to the 12th power. Again, however, a subtle parity preservation on the actual cube means that once the orientations of 11 of the edges is set the orientation of the 12th is forced, so the number of orientations is 2 raised to the 11th power, or 2,048. So the number of possible edge configurations is 239,500,800 X 2,048 = 490,497,638,400.If we consider only these configurations, which is all you have to consider on a standard cube, the number of possible configurations is the product of these two numbers, 88,179,840 x 490,497,638,400 = 43,252,003,274,489,856,000, or about 43 X 10 to the 18th, or 43 billion billion, which is also called 43 sextillion.

  4. flower says:

    Computer scientists aren’t interested in actually finding out the answer you know, they just need some standard endless task with which to calibrate their computer speed. 😉

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s