43 quintillions ways of amazing fun: Rubik’s Cube
We have all heard of The Rubik’s Cube. So, what makes it special and how can one find the solution. In this two-part series, we will first introduce Rubik's cube and its history. In the 2nd part, we will go through the whole process of solving the Rubik's cube.
What is the Rubik’s cube?
Answering this question is like answering “What is a plane or a building?”. We all know what a Rubik’s cube is, but just for definition’s sake:
Rubik's Cube is a 3-D combination puzzle invented in 1974 by ErnÅ‘ Rubik. The classic Rubik's Cube has six faces which are covered with nine stickers, each of one of the six solid colors, traditionally white, red, blue, orange, green, and yellow.( White is opposite yellow, blue is opposite green, and orange is opposite red, and the red, white and blue are arranged in a clockwise arrangement). There is an internal pivot mechanic which allows each face to turn independently, thus mixing up the colors. The challenge is to bring the cube back to an organized state where each side consists of only one color. Similar puzzles with various numbers of sides, dimensions, and stickers are now available.
The popularity of the Rubik’s cube: –
ErnÅ‘ Rubik with his invention of the Rubik’s cube captured the fascination of the entire world and soon it became the most popular game of 1980’s. As of records, on January 2009, sells had gone over 350 million cubes, making it the top-selling puzzle game in the world. And it should be mentioned that solving this masterpiece isn’t that easy. In fact, it is quite difficult. Many films and television shows have featured characters that solve Rubik's Cubes quickly to establish their high intelligence. And just not in tv shows and movies, there are also sculptures based on the Rubik’s cube.
The Mathematics of the Rubik’s Cube: –
And now comes the part you all have been waiting for (though some may not!), the Mathematics of Rubik’s cube. Well let’s start small. The Rubik’s cube is said to have a “billion”(I’ll prove how that is small) different positions. Where the facts are: –
- There are 8 corners, hence 8! Ways to arrange the corner cubes.
- Seven can be oriented independently, and the orientation of the eighth depends on the preceding seven, giving 3^{7}(2,187) possibilities.
- There are 12!/2 (239,500,800) ways to arrange the edges since an even permutation of the corners implies an even permutation of the edges as well.
- There are 12!/2 (239,500,800) ways to arrange the edges since even permutation of the corners implies an even permutation of the edges as well.
Hence, the number of different positions just by turning the sides of the of the cube is approximately 43 quintillions.
Rubik’s cube and Research: –
It has been 30 years since the Rubik's cube first appeared. Researchers have now proved that in any given configuration of the cube, it is only 20 moves away from being solved. The entire research took a span of 35 years of computation on a good modern computer even though they managed to avoid evaluation of all 43 quintillion configuration. Erik Demaine,and his father Martin Demaine, both scientist at MIT; Anna Lubiw, Demaine’s PhD thesis adviser; Sarah Eisenstat Andrew Winslow both graduate students, together showed that a Rubik’s cube with N squares per row requires moves proportional to N^{2}/log N to be solved. “That that’s the answer, and not N^{2}, is a surprising thing,” Demaine says.
The standard way to solve a Rubik’s cube is to find a square that’s out of position and move it into the right place while leaving the rest of the cube as little changed as possible. That approach will indeed yield a worst-case solution that’s proportional to N^{2 }states Demaine. Demaine and his colleagues recognized some circumstances yield situations where a single sequence of twists could move multiple squares into their proper places, thus reducing the total number of moves.
In the 2nd part, we will solve the Rubik's cube.