Author |
Topic: Rubik's Cube (Read 31128 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Rubik's Cube
« on: Oct 14th, 2002, 11:47pm » |
 Quote  Modify
|
You are given a Rubik's cube in a randomly chosen initial position. Denote a "move" as a 90 degree rotation of a face.
"God's Algorithm" is the name of an algorithm which solves a Rubik's cube in the fewest number of moves.
1. Determine a lower bound for the number of moves God's Algorithm requires.
2. Determine an upper bound.
3. Can you devise a small, simple algorithm to solve a Rubik's cube in the minimum number of moves? (e.g. not brute-force lookup tables)
// MODIFIED BY ADMINISTRATOR 18 OCTOBER 2002
|
| « Last Edit: Oct 18th, 2002, 8:09pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Rubik's Cube
« Reply #2 on: Oct 17th, 2002, 2:06am » |
Quote Modify
|
Way hard problems, William. I think there's a fairly extensive mathematical literature on Rubik's Cube. Back in the late 70's when the cube first came out, David Singmaster was the leading mathematician studying it. You can find a lot of material by searching for his name on the Web. One interesting link is http://www.zeta.org.au/~sausage/twistymegasite/interview-singmaster.html , an interview with Singmaster.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Rubik's Cube
« Reply #3 on: Oct 17th, 2002, 6:48am » |
Quote Modify
|
Well, apparently the Maximum Minimum Hamming Distance problem is known to be an unsolved problem, but that didn't stop anyone  Actually, someone who works on computational algebra software e-mailed me shortly after slashdot, saying that engineers currently get around the Hamming Distance problem by using lookup tables. But the problem didn't seem so impossible to me, so I refused to believe him at the time.
The latter two problems posted above are probably unreasonable, but the lower bound question might a reasonable -- although nasty -- exercise in combinatorics, given that some hints are added. To get the known lower bound, first assume that we can solve the cube in K moves. Then derive a function F for the number of distinct sequences of K moves from the starting position. Dirty overcounting issues here. After that, consider the number of possible positions for a Rubik's cube, which is about 43 quintillion. By using this number and the formula derived earlier, a lower bound can be achieved by experimenting with different values of K and evaluating F(K).
Devising an optimal algorithm for solving a Rubik's cube was a natural thought I had when I first encountered the toy; I was rather surprised when I found out that no one has solved it yet. It seems like someone will solve it someday, I mean, it's just a toy. I dunno.
Thanks for the links guys 
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Rubik's Cube
« Reply #4 on: Oct 17th, 2002, 1:57pm » |
Quote Modify
|
I don't understand the second question. I can make an unlimited number of moves without solving the cube. In fact, so can any toddler. And I can even devise an algorithm which is guaranteed to eventually solve it, but in an unbounded amount of moves.
What are you looking for, there?
And while we're at it, how many "moves" does it count as if you take all the stickers off? <EG>
|
|
IP Logged |
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Rubik's Cube
« Reply #5 on: Oct 17th, 2002, 6:07pm » |
Quote Modify
|
Come to think of it, I have a solution for problem 3, as well, which makes me suspect that the problem wasn't stated correctly.
At any given position, there are twelve possible moves: Six faces, and each can be turned 90 degrees clockwise or counterclockwise (I'm considering the 180 degree turn to be two moves). Well, then, every possible position connects to twelve other possible positions. Do a breadth-first search of all of the positions accessible from the starting position, and halt when you reach the solved position.
Now, admittedly, this algorithm is horribly inefficient, in both running time and memory. I can think of a few simple ways to improve it dramatically, and still leave it horribly inefficient. But it's guaranteed to conclude in a finite, bounded amount of time, and when it does, it'll be guaranteed to output the (or at least, an) optimal sequence of moves for getting to the solution.
This is obviously not what's wanted, but I can't think of any good way to phrase what is wanted. If the requirement is for an algorithm to produce the optimal solution on a real computer in a reasonable amount of time, then we need to specify what is a reasonable amount of time, and how much memory a real computer has. If we want to optimize for the combined time to generate the solution and to carry it out on a physical cube, then we need to specify how much time it takes to make a physical move, as compared to the time for a fundamental operation on the computer. If we want the fastest possible algorithm for finding the optimal solution, or even any solution, then the problem is rather nebulous: It's hard, to say the least, to prove that an algorithm for anything is perfectly optimized.
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Rubik's Cube
« Reply #6 on: Oct 17th, 2002, 9:57pm » |
Quote Modify
|
I should really let William clarify his own questions, but I think this is what he means:
It's possible to come up with algorithms for solving the cube from any position that are small and simple enough that a human can learn and do them quickly. Such an algorithm may not solve the cube in the smallest possible number of moves from each position, of course. Brute-force search (or equivalently, a quintillion entry lookup table) could do that, but they're impractical. (They're feasible as far as complexity theory is concerned, since the cube is of constant size, but that's not very comforting. Solving chess is theoretically feasible too, since the board is constant size.)
Suppose I have an algorithm A that solves the cube. For each starting position P, my algorithm takes A(P) moves to solve the cube, so there is some worst-case number M(A) = max{A(P)} moves required for A to solve the cube.
1) Find a lower bound on M. Obviously A can't be better than the optimal brute force algorithm, so if we knew how long that took, it would be a tight lower bound over all algorithms, and a lower bound (though perhaps not achievable) for small, simple algorithms. Do we know M(brute force)? Another name for this is diameter.
2) Find an upper bound on M for small, simple algorithms. This is just a way of saying "find the best small, simple algorithm you can." Maybe you can even find one whose M is as good as brute force -- this would happen if (for instance) your algorithm always takes M moves exactly, while brute force could be smarter and sometimes take fewer. If you don't find a way to do that well, since the notion of the algorithm being small and simple is fuzzy, it's not clear when you're done reducing the upper bound.
3) I think this question is, "can you encode the quintillion entry lookup table into a small, simple algorithm?" In other words, is there a small, simple algorithm that is as good as brute force for every starting position, not just for the worst case? This one is fuzzy too, but less so than (2).
|
|
IP Logged |
http://tim-mann.org/
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Rubik's Cube
« Reply #7 on: Oct 18th, 2002, 1:06pm » |
Quote Modify
|
OK, I rephrased the problem. Still don't like question 3 though ... too fuzzy.
I was going to say: devise an algo that solves the cube in the least number of moves, with a worst-case running time polynomial in terms of N. But is that not reasonable?
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Rubik's Cube
« Reply #8 on: Oct 18th, 2002, 6:30pm » |
Quote Modify
|
This does not directly address any of your questions, but about a year ago, because I was curious I figured out the probability distribution for the number of moves (defined as a quarter turn of a face) of a particular "solving method".
The results I got were that the method required at most 189 moves, and averaged about 111 moves. I never calculated the standard deviation but it looks to be about 20.
Some Caveats: The method I used was far from optimal. There were some short cuts I never brought in because it would of made the calculation a lot harder, (and even with them it still is far from optimal). Also, at one point in the middle I gave up trying to figure out the dependencies between certain placements of the middle edges, and just assumed they were independent as an approximation, so even barring any calculation errors (surely not!) the numbers are not completely accurate (the upper limit of 189 is, just not the probabilities).
I guess this does provide an answer to question 2: 189 is a bound, just not a very tight one.
If you are feeling masochistic, here is an outline of the solving method I analyzed: (pardon me if this is not the normal notation for denoting moves, but it is the one I used, and I am too lazy to look up the regular one and translate: Faces are:Top, Bottom, Front, Aft, Right, Left. Identified by their initial. Positive rotations are counter-clockwise, when you are looking directly at the face).
1) Place the top edges. This I examined by a "least number of moves I could figure out" method based on the initial placement of each of the edges. (Essentially the brute force lookup table method, except I won't guarentee I always found the shortest solution).
2) Place the top corners. Examined the same way.
3) Place the middle row edges. Basic maneuver: R+B-R-B-F-B+F+ (places LB edge into FR position). Move a middle edge on the bottom into the "ready" position, then use the move above (for the appropriate pair of sides) to put it where it belongs. If a middle edge is not on the bottom, and not where it belongs, bring it down to the bottom with the same maneuver (when possible by putting the correct piece in it's place), then position it.
4) Position, unoriented, the bottom corners. Turn the bottom to bring at least two into place. Perform this maneuver to exchange the front two corners (Reorient and perform again if caty-corners were switched): R-F+R+F-B-F-B+F+. At the end the corners will be in order, but rotated from the correct position. I only correct this once I am completely done with the corners.
5) Orient the bottom corners. Basic maneuver: R+B--R-B-R+B-R-. It may have to be done up to 3 times.
When finished turn bottom to correctly place corners.
6) Orient the bottom edges so that the bottom is all one color. Basic manuever: (I'm going to describe this one in the way I think of it, not as according to the format I listed above. In this, the Top corners, not the centers, now determine the cube orientation. M is the middle row of the front & top faces. Positive rotation is turning the top middle row down to the front middle row. Equivalent to R-L+ and a reorientation of the cube in the normal format.) M+B-M-B-M+B-M-B+M+B+M-B+. This will flip two adjacent edges. For two opposite edges I use M+B-M-B-M+B-M-B-M+B--M-B-M+B-M-B-M+B-M-B-- (I once knew a shorter way, but I have long since forgotten it - I remember this way because flipping the two sides is the ONLY effect it has - useful when playing around with designs). And yes, I did count each "M" move as two moves.
7 Position the bottom edges: There are a number of different moves I use here depending on how they are arranged. The most common is 3 edges permuted. The maneuver I used for this: position the middle of the three in front. Assuming the edge on the right is the one that goes in front: F++T+ Reorient cube so right face becomes front. M+B++M-B++. Return to original orientation. T-F++. (Reorientations of the cube do not count as moves).
I know that there are better ways of going about solving, but I am too stuck in my ways to figure them out.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Rubik's Cube
« Reply #9 on: Oct 18th, 2002, 7:35pm » |
Quote Modify
|
OK I rephrased it again because my previous rephrasing didn't make much sense. I was asking for a lower bound on the minimum number of moves required to solve a cube, and the answer to question 1 would have just been "1": I could rotate a solved cube once to make a randomized cube which requires 1 move to solve. But of course that wasn't what I was getting at. I think it's fixed now.
Incidentally, I bought a Rubik's cube a few hours ago. Rubik's cubes are new discoveries for me; I had one when I was really small but I never really played with it, and now I have my own and I'm fascinated! It was only $3.99 for two cubes: a regular sized one and a cute miniature one. I randomized the regular sized one and I can't get it back to normal, so now I'm afraid to randomize the miniature one  The little box also included a "magic cube quick solution diagram" which gives a suprisingly detailed six step process for solving the cube. Elements of Icarus's method are also present in this process. Maybe I'll scan the diagram for you guys later.
|
| « Last Edit: Oct 18th, 2002, 8:27pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Rubik's Cube
« Reply #10 on: Oct 21st, 2002, 11:15pm » |
Quote Modify
|
Quoth William Wu: Quote:| I was going to say: devise an algo that solves the cube in the least number of moves, with a worst-case running time polynomial in terms of N. But is that not reasonable? |
|
I don't understand... What is N? The cube is finite, and there is some constant upper bound (even if we don't know what it is) to the number of moves a solution need take, so a brute-force search must also have an upper bound to its running time. Constant time is certainly polynomial, in terms of anything.
By the way, if anyone wants to play with a cube without going out and buying one, I have a computerized one I wrote on my Web page. It's pretty primitive (MS-DOS, no mouse input), but it'll work, and if you get stuck, you can always just type "new"
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Rubik's Cube
« Reply #11 on: Oct 21st, 2002, 11:28pm » |
Quote Modify
|
Sorry about that. In a previous phrasing of the problem, N was denoted as the minimum number of moves required to solve a cube.
You know, feel free to ignore me on this thread; given the number of times I've fscked this one up, I'm convinced I really haven't a clue as to what I'm talking about
|
| « Last Edit: Oct 22nd, 2002, 1:43am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Kozo Morimoto
Junior Member
Posts: 114
|
|
Re: Rubik's Cube
« Reply #12 on: Oct 23rd, 2002, 5:47pm » |
Quote Modify
|
I believe the 'optimal' method quoted by cubists is the method where by you manipulate the corner-edge pairs. I believe there are standard list of moves which you can use to manipulate the corner-edge pairs to anywhere on the cube without disturbing the rest of the cube.
The layer method is easy to do, but far from optimal and not the method used by the extreme cubists who compete for the world record.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Rubik's Cube
« Reply #13 on: Oct 23rd, 2002, 7:13pm » |
Quote Modify
|
Yeah, I said the method I outlined was not optimal. I figured out early on that I was too clumsy to try for speed. So I have always stuck with the method I discovered myself. Most of my cube play was in figuring out what designs I could make. As for the methods used by competitors, they are designed for speed, not minimum moves. Trading off more moves for easier detection of what to do will often increase solving speed.
A lower bound (again, not very tight) for "God's Algorithm" can be obtained by noting that each cube position has 12 neighbors. So the number of positions obtainable from the solved position after N moves is < 12N. To reach the total number of legal positions (210378!12!) therefore requires at least 19 moves. Turning this about: Some cube positions are at least 19 moves away from solved.
Well now! I've done the hard work of reducing the possibilities for the max moves in God's Algorithm from an infinite number of choices down to a measly 171. Surely someone else can figure out these last few cases! 
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Rubik's Cube
« Reply #14 on: Oct 28th, 2002, 5:00pm » |
Quote Modify
|
I have an improvement on the previous calculation: It counts under the assumption that every sequence of moves gives a unique position. Since this is not true it over counts the number of positions reachable in N moves, or conversely, under counts the number of moves needed to reach every position. We can tighten the lower bound by removing from the count the most common situations where two sequences of moves lead to the same final position. In particular I want to remove the following: sequences with a particular move and then it's inverse, sequences where the same move occurs 3 or more times in a row (for three times, the same result is obtained by doing the move's inverse once). I also want to remove half the sequences involving a turn of one face, followed by a turn of the opposite face, since these two moves are commutative (switch the order and you get the same result).
To this end, select one of each pair of opposite faces to call the "high priority" face, and the other to be the "low priority" face. We build sequences of moves according to the following rules:
1) A move T cannot be followed by the move T-1.
2) If T is high priority move, it cannot be followed by a corresponding low priority move (i.e. a turn of the opposite face).
3) If the last two moves were both T, then T is not allowed for the next move.
I want to add up all the sequences of length n which follow these rules. To do this I use 4 variables:
SLn=# of sequences ending in a single occurence of a low priority move.
SHn=# of sequences ending in a single occurence of a high priority move.
DLn=# of sequences ending in a double occurence of a low priority move.
DHn=# of sequences ending in a double occurence of a high priority move.
These satisfy the following recurrence relations:
SLn+1= 4(SLn + SHn + DLn + DHn)
SHn+1= 4(SHn + DHn) + 6(SLn + DLn)
DLn+1= SLn
DHn+1= SHn
Let Tn = SUMi=1n(SLi + SHi + DLi + DHi) be the total number of sequences of length < n. Some play with a spread sheet gives:
T19 = 9.5783x1018
T20 = 9.3929x1019
Since the total number of positions of the cube is ~4.33x1019, it follows that it takes at least 20 moves to reach some cube positions from solved. Or conversely, some cube positions cannot be solved in less than 20 moves.
So I have moved the lower bound up by 1. However, this time I will say that 20 IS a tight lower bound. I would be suprised if there are any positions more than 20 moves out from solved, and extremely suprised if any existed that are more than 21 moves away. The reason is the logarithmic relationship between the number of positions reachable and the number of moves. By removing a large majority of the overcounted positions I was only able to increase the number of moves by 1. I doubt that removing the rest of the overcount will have a bigger effect. But... I can't prove it! So maybe I'm wrong.
I also have an answer for the 3rd question: NO NO NO NO NO NO NO NO NO NO NO NO NO NO I can't come up with a simple algorithm to get the min number of moves. Maybe someone else can, but it's beyond me!
|
| « Last Edit: Oct 28th, 2002, 5:41pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Carl_Cox
Newbie
Gender:
Posts: 23
|
|
Re: Rubik's Cube
« Reply #15 on: Nov 2nd, 2002, 4:23pm » |
Quote Modify
|
I've been looking for a leaflett that I had on this subject since WIlliam posted the question, and today I found it!
It's a book of about 30 pages. The title is "Mastering Rubik's Cube; The Solution to the 20th Century' Most Amazing Puzzle" by Don Taylor. It contains several interesting facts about the Rubik's cube. It also contains the algorithm described by icarus. Apparently, someone knowledgable in this solution can solve the cube in < 3 minutes. The lower boundry for solving the cube in 90 seconds.
I was disappointed. I remember looking into this problem a few years ago and finding an algorithm having to do with solving sub blocks. Most people solve the cube by layer (as in this book and icarus's solutions). However, I the solution which i'm trying to remember (and failing) is to solve by column. The idea is that you start on one corner of the cube, place it correctly (according to the center cube of each face), then place the adjoining edge pieces.
Anyway. Here's a different question (pulled from this handy dandy book.) One can make a number of interesting patterns on the faces of the rubic's cube. How many different patterns are possible?
Incidentally, this book has a value, but not a proof.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Rubik's Cube
« Reply #16 on: Nov 2nd, 2002, 5:53pm » |
Quote Modify
|
There are several approaches to cube solving. The most common by far is the layer approach, but I have also heard of "solve the corners, then the edges" approaches, and columns methods. I have never personally come across a method that fits Kozo's description, but I have no reason to doubt him about it being the choice of speed solvers. (I suspect your 90 seconds time is out of date.)
However none of them are even close to "God's Algorithm", which I still argue takes 20 or 21 moves from the worst case positions.
Quote:One can make a number of interesting patterns on the faces of the rubic's cube. How many different patterns are possible?
|
|
I'm not sure of exactly what you are asking here. There are 210378!12! ~= 4.33x1019 different cube positions, each of which could be considered a different pattern on the faces. Since this number has already been given, I assume you mean something else.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
HammerSandwich
Newbie
Posts: 8
|
|
Re: Rubik's Cube
« Reply #17 on: Nov 20th, 2002, 12:16pm » |
Quote Modify
|
Carl, even layer-by-layer can be quite a bit faster than your book says. I'm hardly the fastest solver out there, and I can usually do it in 90 seconds or less. I've found that the more I play with patterns, the larger my toolbox of solving moves becomes...
A few interesting bits from the book which came with my cube:
- "22.95 seconds! That's how long a high school student from Los Angeles took to unscramble the cube and win the Budapest world championship in 1982."
- "Some people can solve Rubik's Cube in 52 moves from any scrambled position."
- "Theoretically the shortest path to solving Rubik's Cube from any scrambled position is as few as 22 twists. So far no one has succeeded in demonstrating this method."
Close to Icarus' calculation, but looks like we've missed something here...
|
|
IP Logged |
|
|
|
HammerSandwich
Newbie
Posts: 8
|
|
Re: Rubik's Cube
« Reply #18 on: Nov 20th, 2002, 12:21pm » |
Quote Modify
|
Rereading, I'm struck by this:
2) If T is high priority move, it cannot be followed by a corresponding low priority move (i.e. a turn of the opposite face).
Why this restriction? Doesn't this prohibit moving a central layer (e.g. so the bottom center edge moves to top center)? That might get you up to 22 moves, Icarus.
|
|
IP Logged |
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Rubik's Cube
« Reply #19 on: Nov 20th, 2002, 3:41pm » |
Quote Modify
|
Moving a central layer counts as two moves, not one: You do that by turning one face, and then the other (and then maybe rotating the entire cube). The reason for the "priority face" restriction is that turning, say, the top face and then the bottom face, will get you to the same position as turning bottom, then top. So if you want to turn both, then just say that you always turn the bottom one first, so as to cut down on the number of possible moves.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Rubik's Cube
« Reply #20 on: Nov 20th, 2002, 3:51pm » |
Quote Modify
|
Chronos is right about why I put the priority move restriction in. My counting procedure was designed to remove all duplicated positions caused by loops of length 4 or less (ie, a series of 4 or fewer moves that returns you to the same position you started from). Apparently longer loops lead to far more duplicates than I suspected, though I still find it hard to believe. I assume the "22 moves" result came from some of the extensive group theory analysis that has been done on the cube.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Rubik's Cube
« Reply #22 on: Dec 17th, 2002, 6:28pm » |
Quote Modify
|
Either that site is out of date or the 22 move number is also a guess on someone's part. I find it amazing that no one has come up with an upper bound lower than 42 moves though!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
fenomas
Newbie
emoticonoclast
Gender:
Posts: 20
|
|
Re: Rubik's Cube
« Reply #23 on: Dec 17th, 2002, 8:53pm » |
Quote Modify
|
on Nov 2nd, 2002, 5:53pm, Icarus wrote:| ... There are 210378!12! ~= 4.33x1019 different cube positions... |
|
Ic, can you explain where this number comes from? I'm not disputing it, I just don't have any idea! Is finding the number of legal positions for the cube the same as if you took the cube apart and counted the positions it could be reassembled into? Or are there positions that could be made that way that could never be reached through legal twist moves starting from a solved position? (Like, say, the cube solved except for one edge piece that is reversed, or some such nightmare..)
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Rubik's Cube
« Reply #24 on: Dec 18th, 2002, 4:04pm » |
Quote Modify
|
There are 3 "symmetries" that all legal positions must satisfy:
1) The parity of the permutation of the edges is the same as the partity of the permutation of the corners. I.e. you cannot exchange just two edges, or just two corners, but you can exchange two edges and two corners, or exchange 3 edges, or exchange 3 corners.
2) The total rotation of the edge pieces must be the identity. I.e. you cannot flip a single edge, but you can flip pairs of edges.
3) The total rotation of the corner pieces must be the identity. I.e. you cannot rotate a single corner. You can only rotate two corners if you rotate them in opposite directions.
The first and second rules each cut the number of possible positions by 1/2. The third rule cuts it by 1/3. And you can show from the remarks I included about what can be done that these are the only restrictions.
So we start with the number of ways to assemble a cube:
There are 12! arrangements of the 12 edge pieces. Each edge piece can go in two ways, giving 212 variations. There are 8! arrangements of the 8 corner pieces. Each corner can go in 3 ways, giving 38 variations.
This yields a total of 12!8!21238 ways of assembling a cube, and 12!8!21238/(2x2x3) = 12!8!21037 legal positions.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print