wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> hard >> Rubik's Cube
(Message started by: william wu on Oct 14th, 2002, 11:47pm)

Title: Rubik's Cube
Post by william wu on Oct 14th, 2002, 11:47pm
You are given a Rubik's cube in a randomly chosen initial position. Denote a "move" as a 90 degree rotation of a face.

http://www.ocf.berkeley.edu/~wwu/images/riddles/rubikcube.gif


"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

Title: Re: Rubik's Cube
Post by Garzahd on Oct 15th, 2002, 1:08pm
I don't have an answer, but we solved a couple other questions of permutations and rubik's cubes in my college discrete math/problem-solving class in college.

http://www-2.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-s00/2000/Site/Materials/Assignments/assignment10/assignment10.htm

The above assignment asks "how many foo can be enumerated given these constraints" rather than an algorithmic solution to getting to a certain configuration, so it probably won't help with the question, but the material is interesting.

Title: Re: Rubik's Cube
Post by TimMann on Oct 17th, 2002, 2:06am
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.

Title: Re: Rubik's Cube
Post by william wu on Oct 17th, 2002, 6:48am
Well, apparently the Maximum Minimum Hamming Distance problem is known to be an unsolved problem, but that didn't stop anyone :D 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 :)

Title: Re: Rubik's Cube
Post by Chronos on Oct 17th, 2002, 1:57pm
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>

Title: Re: Rubik's Cube
Post by Chronos on Oct 17th, 2002, 6:07pm
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.

Title: Re: Rubik's Cube
Post by TimMann on Oct 17th, 2002, 9:57pm
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).



Title: Re: Rubik's Cube
Post by william wu on Oct 18th, 2002, 1:06pm
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?


Title: Re: Rubik's Cube
Post by Icarus on Oct 18th, 2002, 6:30pm
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.

Title: Re: Rubik's Cube
Post by william wu on Oct 18th, 2002, 7:35pm
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.

Title: Re: Rubik's Cube
Post by Chronos on Oct 21st, 2002, 11:15pm
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 (http://physics.montana.edu/students/bambeck/freestuf.htm).  It's pretty primitive (MS-DOS, no mouse input), but it'll work, and if you get stuck, you can always just type "new" ;)

Title: Re: Rubik's Cube
Post by william wu on Oct 21st, 2002, 11:28pm
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 :D

Title: Re: Rubik's Cube
Post by Kozo Morimoto on Oct 23rd, 2002, 5:47pm
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.

Title: Re: Rubik's Cube
Post by Icarus on Oct 23rd, 2002, 7:13pm
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! ;D

Title: Re: Rubik's Cube
Post by Icarus on Oct 28th, 2002, 5:00pm
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 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! ;)

Title: Re: Rubik's Cube
Post by Carl_Cox on Nov 2nd, 2002, 4:23pm
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.

Title: Re: Rubik's Cube
Post by Icarus on Nov 2nd, 2002, 5:53pm
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.

Title: Re: Rubik's Cube
Post by HammerSandwich on Nov 20th, 2002, 12:16pm
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...

Title: Re: Rubik's Cube
Post by HammerSandwich on Nov 20th, 2002, 12:21pm
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.

Title: Re: Rubik's Cube
Post by Chronos on Nov 20th, 2002, 3:41pm
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.

Title: Re: Rubik's Cube
Post by Icarus on Nov 20th, 2002, 3:51pm
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.

Title: Re: Rubik's Cube
Post by Kozo Morimoto on Dec 5th, 2002, 4:19am
Hey check out interesting math info on the Cube at:
http://mathworld.wolfram.com/RubiksCube.html

Title: Re: Rubik's Cube
Post by Icarus on Dec 17th, 2002, 6:28pm
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!

Title: Re: Rubik's Cube
Post by fenomas on Dec 17th, 2002, 8:53pm

on 11/02/02 at 17:53:24, 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..)

Title: Re: Rubik's Cube
Post by Icarus on Dec 18th, 2002, 4:04pm
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.

Title: Re: Rubik's Cube
Post by Joe Pellino on Jan 9th, 2003, 6:20pm
I dont know exactly how to solve it but i do know that the fastest way takes 29 moves from any random position.

Title: Re: Rubik's Cube
Post by Icarus on Jan 10th, 2003, 2:34pm

on 01/09/03 at 18:20:37, Joe Pellino wrote:
I dont know exactly how to solve it but i do know that the fastest way takes 29 moves from any random position.


Joe, can you tell us where this number comes from? Kozo's website mentions an upper bound of 29 moves, but it was counting half-turns as one move, whereas the rules Wu has set for us count half-turns as two moves. The quarter-turn only result on that website was 42.

I still seriously doubt that there are any positions more than 20-22 moves away from solved.

Title: Re: Rubik's Cube
Post by biwema on Mar 6th, 2003, 3:20pm
Hi,

Normally a 180 degree turn is also considered as one move. In that case Kociemba's 'Cube Explorer' might be quite interesting:

http://home.t-online.de/home/kociemba/cube.htm

This tool should normally find a solution with less than 21 moves within a few seconds. If you want to prove its optimality, it needs some minutes for 17 moves or several hours for 20 moves.
There are starting positions that need 20 moves (including 180 degree moves) to solve. I don't know if there is a situation which need's more.
Nevertheless it is a funny tool to play with.

According to Mathworld, 29 moves are proven, but the real maximum might be lower.

biwema

Title: Re: Rubik's Cube
Post by Icarus on Mar 6th, 2003, 5:05pm
"Normally" depends on who you are talking to and how they are viewing the problem. In terms of "ease of maneuver", a half-turn is barely any harder than a quarter-turn. But viewed from the point of view of "change of relative positions", clearly they are not equivalent. This latter approach is more intrinsic, while the former is geared towards a particular application.

The big problem is mixing numbers computed according to one definition with those computed by another.

Since William established this puzzle using the quarter-turn only definition, and since most of the numbers were computed using it, I strongly recommend sticking to it.

Using this definition, the best results here demonstrated or referenced in a reliable fashion are:

The maximum number of moves required by "God's Algorithm" is at least 20 (from my 3rd post) and at most 42 (the MathWorld result, expressed in quarter turns).

Title: Re: Rubik's Cube
Post by commando on May 8th, 2003, 11:39pm
Pivotal for determining the minimum number of moves required is a special move called "The Superflip".
Jerry Bryan proved in 1995 that a minimum of 24 quarter turns (front, left, back, upper, right, bottom) are required to arrive at the superflip.
Mike Reid showed proved in 1998 that performing the superflip and then permuting the center faces (superflip + 4-spot) requires an additional two moves, bringing our minimum to 26.  This could be the "longest" move.  

Some interesting places to look:

The superflip (with java cube!):
http://www.randelshofer.ch/rubik/patterns/U080.01.html

Michael Reid's homepage:
http://hedgehog.math.arizona.edu/~reid/Rubik/

More results (including the answer: God's algorithm is bounded between 26 and 42 moves, according to wu's rules):
http://www.geocities.com/jaapsch/puzzles/theory.htm

Title: Re: Rubik's Cube
Post by Patrick Hines on May 22nd, 2003, 10:10am
Hey, I'm 14 and i can do the rubiks cube no problem, but i just can't figure out what this riddle even means, i've been working on figuring out how to do the Rubiks Cube in the least amount of moves, than i found this. But this makes no sense to me ???. If you have time to email me back that would be great, in the mean time i'll just work more on trying to figure this out. See ya!

Title: Re: Rubik's Cube
Post by Patrick Hines on Jun 29th, 2003, 8:04pm
Hey, i was replying to Joe, the Rubiks Cube can be done in less than 29 moves, i don't know the guys name but he did all the math behind it and the least amount of moves you can do it in is 15, i have no clue how thats possible, but it is true, noone has ever done it in 15 moves, or at least not recorded.

Title: Re: Rubik's Cube
Post by Icarus on Jul 5th, 2003, 7:10pm
Actually, T&B, in this post (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1034664469;start=0#14), I proved that the minimum number of quarter-turns has to be at least 20. According to the information provided by commando (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1034664469;start=25#29) the minimum is at least 26.

Patrick - The last link commando provided counts the number of moves required to solve the "superflip" as 20 when you count half-turns as 1 move, so even by that method your 15 moves number is clearly too low.

Title: Solving Example
Post by NetJay Says HI! on Jan 12th, 2005, 3:15pm
http://www.mbsnet.dk/?loc=articles&show=26

Title: Re: Rubik's Cube
Post by Icarus on Jan 12th, 2005, 4:06pm
Okay, towr, what does it say? ;) (I'm very grateful that not everyone is as language-impaired as I am!)

Title: Re: Rubik's Cube
Post by THUDandBLUNDER on Jan 12th, 2005, 10:15pm

on 01/12/05 at 16:06:46, Icarus wrote:
Okay, towr, what does it say?  

It's probably double-Danish to him, too!

Title: Re: Rubik's Cube
Post by towr on Jan 13th, 2005, 12:28am
Yeah, Dutch isn't exactly Danish.. Europe just isn't as uniform as the USA; we can't understand everyone just because they're in the same part of the continent :P

Title: Re: Rubik's Cube
Post by Icarus on Jan 13th, 2005, 2:54pm
Well, obviously some of you can at least recognize what language it is.  :-[

Title: Re: Rubik's Cube
Post by towr on Jan 13th, 2005, 11:39pm
[quote author=Icarus link=board=riddles_hard;num=1034664469;start=25#37 date=01/13/05 at 14:54:13]Well, obviously some of you can at least recognize what language it is.  :-[/quote]
Or we recognize what 'dk' in the domainname stands for, Denmark.
If the exact same page had been in the domain
www.mbsnet.se, I'd have called it Swedish instead. :P

Title: Re: Rubik's Cube
Post by THUDandBLUNDER on Jan 14th, 2005, 11:51pm

on 01/13/05 at 23:39:47, towr wrote:
Or we recognize what 'dk' in the domainname stands for, Denmark.
If the exact same page had been in the domain
www.mbsnet.se, I'd have called it Swedish instead. :P

I also checked a couple of words with an online translator.
When correcting Icarus it's always a good idea to be sure of one's facts! :D

In fact, it can be translated into something resembling English using the translator at the bottom of this (http://translation.langenberg.com/) page.


Title: Re: Rubik's Cube
Post by Icarus on Jan 15th, 2005, 7:20am
Well, then, if I am translating the translation correctly, it appears that this site is merely giving instructions on solving the cube. There appears to be no particular reason to believe that this solution is anything close to minimal, so now I wonder at Net Jay's purpose in posting it? Did he totally fail to understand the point of this thread?

Title: Re: Rubik's Cube
Post by rmsgrey on Jan 15th, 2005, 8:39am

on 01/15/05 at 07:20:09, Icarus wrote:
Did he totally fail to understand the point of this thread?

Since he didn't suggest that each prisoner unscrew it by 1% on their first visit, I'd say he didn't totally fail to understand the point of this thread - if nothing else, the provision of a general solution to Rubik's Cube indirectly provides an upper bound to "God's Algorithm"

Title: Re: Rubik's Cube
Post by MorbidJoe on Jul 24th, 2006, 2:38pm
Surely the answer to 1) is 0 moves. All faces correct is a perfectley random position, just as random as any other position in fact. If I am incorrect, and the question means what is the maximum & minimum amount of moves from the same position, then the maximum is infinite.  :-/

Title: Re: Rubik's Cube
Post by Icarus on Jul 24th, 2006, 6:40pm
No. "All faces correct" is a specifically selected position, not a random one. A random position is one in which you don't get to say what it looks like, as long as it is valid.

A better way of stating the question is "what the maximum distance of any position from solved?", where distance between positions is the minimum number of moves needed to get from one to the other.

Title: Re: Rubik's Cube
Post by dudiobugtron on May 22nd, 2014, 1:36pm
This has now finally been solved. (Despite the dire prediction in the 'unsolved puzzles' thread.)

Go to "cube 20 dot org" for information about the researchers and how they proved it. (Apologies, I'm not allowed to post links yet!)

The upper bound is now known to be 20.

Title: Re: Rubik's Cube
Post by Hippo on Mar 11th, 2016, 10:06am
Oh I have missed this thread, But seems Tomas Rokicky (and co.) didn't missed the problem.

Yes there are positions requiring 20 turns in face metric.
And there is no position requiring 21. For a random position probability it requires exactly 18 turns is close to 1 (I don't remember how close, but I think its about 99% or even 99.9%).

In half turn metric there are at least 3 positions, but probably just 3 positions requiring 26 turns and no position requiring 27 turns. (I am not much sure I remember well the half turn metric results).

Now you can easily google these results.



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board