Solving a Rubik's Cube
You have a standard Rubik's cube which you bought from ToysRus whose sides can be rotated to change the face of each of the cube. Now assume the Rubik's cube HAVE 27 cubes somehow placed, one upon the other in the 3 X 3 X 3 fashion and solving a Rubik's cube means having same colors at each of the 6 faces.
What are the total number of combination you can get out of a Rubik's cube and how many of these combination is equal to solving a Rubik's cube.
* Note that the corner pieces of the rubik's cube only rotate and align with other corner pieces and so on.
What are the total number of combination you can get out of a Rubik's cube and how many of these combination is equal to solving a Rubik's cube.
* Note that the corner pieces of the rubik's cube only rotate and align with other corner pieces and so on.
Labels: friday special, mathemagic
posted by Rajesh Lal at
3:44 PM
12 Comments:
2, u said each face has to be different, but you didnt say how different, you just twist the middle one way, then, go the other!
The question is how many total combinations are there. Hint, it's a lot, and there are permutations that cannot be arrived at no matter how many times you twist it.
-----
It was recently proven that the cube can be solved no more than 26 moves.
http://www.sciencedaily.com/releases/2007/05/070531131326.htm
Surely it's only 26 cubes, because you never use the middle one, it holds the whole cube together (as I found out when mine broke).
Yanon Mous
When your cube broke, you may have noticed that the 6 center pieces also don't move.
Yeah, that's right.
Yanon Mous
actually, the center pieces actually rotate.
you notice this when solving supercubes (pictures instead of the traditional color)
Rotation doesn't have an impact on the number of combinations of a standard cube. Toss the cube in the air and you'll see that you can make the center rotate (with the cube).
Wiki answer:
There are (8! × 3^8) × (12! × 2^12) = 519,024,039,293,878,272,000 (about 5.2 × 10^20 or 519 quintillion on the short scale) possible arrangements of the pieces that make up the Cube, but only one in twelve of these are actually reachable. This is because there is no sequence of moves that will swap a single pair or rotate a single corner or edge cube. Thus there are twelve possible sets of reachable configurations, sometimes called "universes" or "orbits", into which the Cube can be placed by dismantling and reassembling it.
Explanation:
There are 8 corners with 3 possible orientations each, and 12 side pieces with 2 orientations each. So to get the total, you multiply the number of positions and number of oriantations for the sides, then multiply by same for corners. There are fewer (by 1/12th) when you rule out postions and orientations which you can't get to by scrambling the cube.
If you want to mess someone up, rotate just one corner or flip just one side piece: it's unsolvable in that case (although someone that knows how to solve it will immediately recognize what you've done.) For those that don't know how to solve it, it's basically unsolvable even if you don't dissasemble and rearrange the pieces, of course.
why would you post the wiki ansewr? I found out the number of combinations and then i noticed you had already posted it. that was just stupid
i got 79 different moves... i think its wrong...
As Steve said, there are: 519,024,039,293,878,272,000 possible configurations, but that's only if the cube is disassembled. He mentioned that only one in twelve are actually attainable, so the actual number of moves is:
8! * 3^7 * 12! * 2^10 = 4.33 * 10^19
So, there are exactly 43,252,003,274,489,856,000 possibilities which are attainable.
Steve also mentioned that the cube can be solved in 26 moves or less, no matter what. It's been lowered to 21 moves, actually. You can use the Cube Explorer to figure out the optimal solution.
Here's one way to think of generating the optimal solution. If you include slice moves (which actually lowers the number of moves required to solve the cube), there are 24 possible moves (18 if slice moves are disregarded, like in Cube Explorer):
F B L R U D
F' B' L' R' U' D'
F2 B2 L2 R2 U2 D2
MR ML
M2
CU CD
C2
To generate every possible combination of 21 moves, you'll need to generate:
24^21 + 24^20 + 24^19 + 24^18 + 24^17 + 24^16 + 24^15 + 24^14 + 24^13 + 24^12 + 24^11 + 24^10 + 24^9 + 24^8 + 24^7 + 24^6 + 24^5 + 24^4 + 24^3 + 24^2 + 24^1
or 1.0067450006418207 * 10^29
moves. In other words, there's not enough time in our lives to generate every possible combination of 21 moves, even using many many super computers. What this means is that the number of moves to solve a cube has not been proven necessarily, only hypothesized, and the number could be more or less than 21. The method used to solve the cube in less than 21 moves is highly optimized, but it can't really be proven to be "God's Algorithm," since every possible configuration simply can't be generated in our life times. No arrangement of the cube has been found to date that takes more than 20 moves to solve, however.
As an after thought, if you wanted to generate every possible move, you could do so like this (C# code.. it should also compile in java and C++ if you change the datatypes and the Math.Pow() call):
private String toBase24(int i)
{
String s = "";
while (i > 23)
{
int r = i % 24;
i = i / 24 - 1;
s = (char)(r + 97) + s;
}
s = (char)(i + 97) + s;
return s;
}
String s;
int numPatterns = 0;
int depth = 21;
for (int i = depth; i > 0; i--)
numPatterns += (int)Math.Pow(26, i);
for (int i = 0; i < numPatterns; i++)
s = toBase26(i);
At this point s will contain a string in a 24-base number system. You could loop through each character in s, and select the appropriate move to apply to the cube.
To generate the first 100,000 patterns and apply them on a Prescott 3.0G machine takes 7.9375 seconds. So, to generate 1.0067450006418207 * 10^29 patterns would take about:
7.9375 / 100000 * 1.0067450006418207e29 seconds, or
2.53394166748936224 * 10^17 years.
Post a Comment
Links to this post:
Create a Link
<< Home