# Solving the cube without any decision making



## Tronman (Jan 8, 2010)

Hi there,

I've been interested in the Rubik's cube for a couple of years now and have successful solved it a few times now with some help from various algorithms.

I have a friend who swears that, a few decades ago, she knew a fixed sequence of moves (i.e. turns) that would solve the cube regardless of it's starting configuration. It has been somewhat of an on going debate since she cannot remember the precise sequence of moves, and I do not think that such a sequence of moves is possible, nor have I been able to find any evidence that such a sequence can exist.

To be clear, such a sequence of turns would have to be able to:
1) Solve the cube from any configuration, including a solved cube, or any step along with way if you decided to start over
2) Not require any decisions on the part of the solver, i.e. once you know the moves, it always works.

In addition, I recently chatted with the man who she remembers teaching her the move sequence who confirmed everything she said about teaching her a fixed sequence of moves to solve the cube, but also not remember the sequence himself.

If you know of any such sequence of moves, or could explain why such a sequence could not exist (not just say it can't), I would be most interested.

Thanks!


----------



## joey (Jan 8, 2010)

I lol'd.

No, it's not really possible. (I mean.. technically it is, but not really)


----------



## Tronman (Jan 9, 2010)

joey said:


> I lol'd.
> 
> No, it's not really possible. (I mean.. technically it is, but not really)



Could you elaborate? Thanks.


----------



## 4Chan (Jan 9, 2010)

Yes, it is called the Devil's algorithm.

http://anttila.ca/michael/devilsalgorithm/

It's so long, that for all practical purposes, it's impossible.


----------



## MichaelErskine (Jan 9, 2010)

A sequence that goes through all 43 quintillion permutations? Give me a minute to jot that down


----------



## Lucas Garron (Jan 9, 2010)

It's trivial and impractical.


----------



## qqwref (Jan 9, 2010)

There are some 4 * 10^19 different positions on the cube, so clearly there is no one sequence that will always solve the cube (since a given sequence always has the same effect). However:
- there does exist a single algorithm that you can use, over and over with only cube rotations in between, to solve any position. The R permutation is one example of an algorithm like this. However, decision-making is still required.
- there does exist an algorithm (the Devil's algorithm) that you can execute starting from any position, such that the cube will *at some point in the algorithm* be solved. However, this algorithm has as many moves as there are positions in the cube, so it isn't possible to memorize (or even write down, with current computers).
- if you have scrambled the cube specially by doing something over and over, you can just reverse it to solve it. For instance doing (R y) over and over will lead to a cube that looks scrambled but is trivial to solve if you know how. It is likely that your friend was shown something like this.


----------



## Tronman (Jan 9, 2010)

qqwref said:


> There are some 4 * 10^19 different positions on the cube, so clearly there is no one sequence that will always solve the cube (since a given sequence always has the same effect). However:
> - there does exist a single algorithm that you can use, over and over with only cube rotations in between, to solve any position. The R permutation is one example of an algorithm like this. However, decision-making is still required.
> - there does exist an algorithm (the Devil's algorithm) that you can execute starting from any position, such that the cube will *at some point in the algorithm* be solved. However, this algorithm has as many moves as there are positions in the cube, so it isn't possible to memorize (or even write down, with current computers).
> - if you have scrambled the cube specially by doing something over and over, you can just reverse it to solve it. For instance doing (R y) over and over will lead to a cube that looks scrambled but is trivial to solve if you know how. It is likely that your friend was shown something like this.



Thank you for your responses, I found the devil's algorithm particular interesting. 

As for your last point, she said that she remembers her method worked, even if someone else had scrambled it and she had no knowledge of its scramble. Obviously she wasn't using the Devil's algorithm, as there were less then 30 turns. And the idea that there was no decision making rules out R permutation.

None of those resolve the debate, but the most promising thing you said is that a given sequence of moves always has the same effect. That is what I would need to demonstrate.


----------



## rjohnson_8ball (Jan 9, 2010)

Maybe the person miscommunicated. If you are allowed to decide how to orient the cube between each sequence then it is possible. For example, T-perms can be done at carefully chosen cube orientations to solve corners, then (U L)*3 (U' L')*2 U2 at various cube orientations can permute and flip edges until solved.

(EDIT)qqwref mentioned R-perm.(/EDIT)


----------



## nlCuber22 (Jan 9, 2010)

Your friend lied.


----------



## Tronman (Jan 9, 2010)

nlCuber22 said:


> Your friend lied.



I don't think it's a lie so much as a mis-communication (like rjohnson_8ball said, but not of the same nature), i.e. some decision making that she doesn't remember.

I came here almost hoping to be proven wrong, but it doesn't look like that's the case.

The best argument I can come up with is based off of qqwref's argument that a given number of turns always has the same effect on any configuration.

1. In order for an always-solving-sequence to work, you'd have to be able to take some configuration (A), make a set of moves to some configuration (A'), then go back to A, make the same set of moves, and end up on a different configuration then A', which is impossible.

2. Let's say we had two configurations, A and B, and a sequence of 30 moves.

We run those 30 moves on A, and end up in A':

A -> 30 Moves -> A'

Now lets run those same sequence of moves on B:

B -> 30 Moves -> B'

If A did not equal B to begin with then A' cannot equal B'. Let's imagine that A' did equal B' with A not equalling B. Then what happens if we started with A'/B' and reversed the 30 moves? We can only get either one of A or B, not both.

3. Let's imagine the always-solve sequence did exist. Likewise, if we started with a solved cube, and reversed the sequence, we'll end up in a specific configuration. Thus, the sequence of moves will only solve the cube starting from that configuration. If the always-solve sequence worked, then when we reversed the steps, we'd get difference configurations every time, which can't happen.


Does that reasoning seem sound, or is there a flaw in my logic somewhere?

Thanks!


----------



## adimare (Jan 9, 2010)

Imagine the cube's solved state as a city. From this city there are 12 different paths you can take to another 12 cities. Each of those represents a different state the cube can be in, the paths represent the different turns you can apply to the cube (examples of a turn would be turning the upper face of the cube 90 degrees clockwise, or turning the right face of the cube 90 degrees counter-clockwise). Now, from each of those 12 cities, there are another 12 paths you can take that will take you to 12 new cities (well, 11, as one of those paths will take you back to solved state city).

With a 3x3x3 rubik's cube, theres's over 43 quintillion cities to visit. Looking at it this way, it should be fairly obvious that there is no such thing as a short set path that you can take from any city that will always take you to the solved state city. That'd be like claiming that you know a particular set of left and right directions that will always get you to Rome, Italy, no matter where in the world you start (get out from whetever you are, take a right in the first street you see, then take a left, then keep going for a mile, then take a left, and BAM, you're in Rome).

Long story short, your friend lied


----------



## Zane_C (Jan 9, 2010)

Even with this sequence known as the devils algorithm, the chances are you wouldn't solve it till a very very long time.


----------



## MichaelP. (Jan 9, 2010)

For the purpose of this explanation, lets say their were an algorithm and the first move in said algorithm was to turn the top face to the right (U in notation), and let's also say we have a scrambled cube, we'll if the algorithm could solve the cube from any state, then the first move should be rendered useless if you scramble the cube one more move, the top face to the left (U' in notation) and the cube should still be solved by the algorithm, but the first U is now useless, so if the algorithm can solve from any state, then the first U is unnecessary, if you continued to undo moves in the sequence, then it shows that each move is unnecessary. Eventually you will have no moves at all. Did what I said make sense to anyone else?


----------



## Zane_C (Jan 9, 2010)

MichaelP. said:


> For the purpose of this explanation, lets say their were an algorithm and the first move in said algorithm was to turn the top face to the right (U in notation), and let's also say we have a scrambled cube, we'll if the algorithm could solve the cube from any state, then the first move should be rendered useless if you scramble the cube one more move, the top face to the left (U' in notation) and the cube should still be solved by the algorithm, but the first U is now useless, so if the algorithm can solve from any state, then the first U is unnecessary, if you continued to undo moves in the sequence, then it shows that each move is unnecessary. Eventually you will have no moves at all. Did what I said make sense to anyone else?



Yes


----------



## Lucas Garron (Jan 9, 2010)

adimare said:


> That'd be like claiming that you know a particular set of left and right directions that will always get you to Rome, Italy, no matter where in the world you start (get out from whetever you are, take a right in the first street you see, then take a left, then keep going for a mile, then take a left, and BAM, you're in Rome).
> 
> Long story short, your friend lied


Be careful, synchronizing instructions have surprising results (saw a Mathcamp lecture on them once).

The analogy might be a bit better if the exits out of each city were numbered, so that algs are clearly deterministic and act like cube algs.

Anyhow, I'm not sure why people keep coming up with arguments. The only important fact is that there's more than a single state to the Rubik's Cube.

And why hasn't anyone mentioned what happens when you're allowed to repeat the alg as often as needed? (Not even conjugacy classes help there. )


----------



## MichaelP. (Jan 9, 2010)

Lucas Garron said:


> Be careful, synchronizing instructions have surprising results (saw a Mathcamp lecture on them once).
> 
> The analogy might be a bit better if the exits out of each city were numbered, so that algs are clearly deterministic and act like cube algs.
> 
> ...





Tronman said:


> I came here almost hoping to be proven wrong, but it doesn't look like that's the case.


----------



## Hiero (Jan 9, 2010)

Your friend lied basically. Isn't this one of the "Darndest things noncubers say"?


----------



## cincyaviation (Jan 9, 2010)

(sarcasm) i just love how cubers on forums come up with complex theories and arguements over things that can be answered in 3 simple words(sarcasm)


----------



## anythingtwisty (Jan 9, 2010)

4Chan said:


> Yes, it is called the Devil's algorithm.
> 
> http://anttila.ca/michael/devilsalgorithm/
> 
> It's so long, that for all practical purposes, it's impossible.


That was quite an interesting read.


----------



## Tronman (Jan 9, 2010)

Please do not make this into an attack on the integrity of my friend. I do not believe for a minute that she is lying (that is, deliberately saying it knowing its not true), simply mis-remembering something. That's not what my question is about.

Let me try a different approach: might there be a simple solution algorithm where once a person learned it, it might "feel" like simple memorization, that is the decisions to make are almost subconscious or automatic?


----------



## joey (Jan 9, 2010)

Tronman said:


> Let me try a different approach: might there be a simple solution algorithm where once a person learned it, it might "feel" like simple memorization, that is the decisions to make are almost subconscious or automatic?


Fridrich? ^_^


----------



## FatBoyXPC (Jan 9, 2010)

To shorten up the Devil's Algorithm read (well I haven't really read this but I do understand already this works), and to reiterate what one poster already said: Yes, there does exist an algorithm, that at some point in the algorithm (beginning, somewhere in the middle, or end) the cube will end up solved. This algorithm basically just needs to hit every orientation for every "location" (often called permutations here) on the cube, and also move cubes around. Eventually if you repeat this algorithm enough times, the cube will come out solved (somewhere in this said algorithm). The theory works, but proving it is practically useless.

What probably happened is your friend probably misunderstood what she read or was told. Many people have said this to me, and even when I explain algorithms to people I get the common "do you just do something over and over until it works?" sort of thing. I think they say that because that's what they want to believe, so they can then think they can do it too. Now, if they learned, they could do it very easily. They just don't want to have to think about it. It'd take incredibly longer to even run though this algorithm once, than it would most cubers to even just solve (not to mention record holders).


----------



## meichenl (Jan 10, 2010)

Suppose you have a fixed sequence of 30 moves. If you do that sequence, you'll presumably go through 30 different states of the cube (possibly not if the sequence cancels itself out, but let's be optimistic and suppose it does not).

Do the same sequence again. You'll go through 30 more states, for 60 total. Do it again and you'll have gone through 90 total, etc. Because there are 43 quintillion possible states of the cube, in some cases you'd have to do the sequence of 30 moves 43 quintillion/30 = about 1.4 quintillion times before solving the cube.

So if you had a sequence of 30 moves that you could do over and over about 10^18 times without going back to where you started, you might be able to do what the original poster wanted.

However, it is not possible to have a sequence of any length that you do one quintillion times without repeating. The reason is simple. Once you do the sequence, you've done a permutation of the edges, and a permutation of the corners, and maybe also changed some of their orientations. For example, the sequence might take three edges and send them around in a cycle (edge 1 goes to edge 2, edge 2 to edge 3, and edge 3 to edge 1), and also move five corners around in a cycle (corner 1 to corner 2, ... until corner 5 goes back to corner 1). If that was what your series of moves did, and you repeated it three times, the edges would all be back where they started. The first time would send edge 1 to edge 2's spot. The second time would send it to edge 3's spot. The third time would send it home. Then, if you repeated the sequence two more times, for five total, the edges would be messed up again, but the corners would be in place. If you did the entire sequence 15 times, the edges and corners would all be back in their starting places.

Those edges and corners might also be flipped or rotated, but if so, by doing the sequence 90 times (15 * 3 *2, three for the corner orientations to be fixed and two for the edges), all the pieces would have to be oriented correctly, and the cube would be solved. This sequence of moves would be said to have "order 90".

It is possible to find things with order higher than 90, but not much higher. The highest order you could achieve is 1260, which would come about if you put the corners in a three cycle and a five cycle, and the edges in a seven cycle and two two cycles, and then made sure that some corner and edge orientations got messed up. There are some technical reasons why you cannot build cycles that would have even higher order - this is the best you can actually achieve. All of what I've said above is sure-fire (unless I made a mistake counting the cycles that make the highest-possible order element of the cube group), and can be made mathematically precise if it's not convincing.

So if the sequence has 30 moves, somewhere in the first 1260 times you do it the cube will go back to solved, and you've only covered 30*1260, or about 40,000 positions. So you could only solve 40,000 positions that way. The shortest thing you could possibly remember that would go through every position would be 4.3*10^19/1260, or 3.4*10^16 moves long. Your computer's hard drive could not store this sequence.

This doesn't mean a sequence this short exists that does the job, only that any sequence that goes through all the positions must be at least this long.

Reading through the link some people provided earlier in the thread, I see the author of the page on the Devil's Algorithm did the same thing with a 2x2 cube to give a minimum length of the sequence you'd need there.

So, I'm not sure whether you'd have to remember a sequence of length 43 quintillion or just 34 quadrillion (or possibly longer than 43 quadrillion, since the "Devil's Number" is unknown) to solve the cube with no decision making (other than knowing when to stop), but either way it is not likely to happen.


----------



## meichenl (Jan 10, 2010)

Also, I should point out that when I said "your computer's hard drive could not store this sequence", I meant that it could not be stored uncompressed.

Such a sequence actually contains very little information, and one could write a very short program to generate it.


----------



## Hiero (Jan 10, 2010)

This reminds me. I used to know the cure for AIDS but I forgot it. I thought I remembered curing a few people, but I don't remember how I did it. Some person taught me how to do it, but they also forgot.

Oh about the cube thing. Yeah there is a really easy algorithm less than 30 moves that solves the cube, but that's the easy way. We like memorizing a ton of algorithms and doing it that way for the fun of it.


Oh and make sure you edit your old post instead of adding a new one or the guys here get really mad.


----------



## HALLU (Jan 10, 2010)

The algorithm would have to be so long that it would go through ALL of the possible positions the cube could be in. Possible if you let a computer calculate it, but a person would not be able to solve it like this, simply because the algorithm would be waaaay to long...


----------



## cuBerBruce (Jan 10, 2010)

meichenl said:


> It is possible to find things with order higher than 90, but not much higher. The highest order you could achieve is 1260, which would come about if you put the corners in a three cycle and a five cycle, and the edges in a seven cycle and two two cycles, and then made sure that some corner and edge orientations got messed up.



Actually, the highest order being 1260 is only correct if you only consider move sequences that only contain face-layer turns. If you allow double-layer turns or inner-layer turns, then it's possible to have sequences that could be repeated 2520 times before you return to the starting state.


----------



## meichenl (Jan 10, 2010)

Hi Bruce,

Could you explain that some more, please? How are double-layer turns or inner-layer turns any different than face-layer turns? As far as the Rubik's cube group is concerned r = L, for example, and M = R L', so I don't understand how adding in these new moves could make a difference.

I notice the number you quoted is double mine. Are you referring to a redefinition of the Rubik's cube group where the location of the centers in physical space matters? If so, why is the figure doubled rather than quadrupled?


----------



## cuBerBruce (Jan 10, 2010)

meichenl said:


> Hi Bruce,
> 
> Could you explain that some more, please? How are double-layer turns or inner-layer turns any different than face-layer turns? As far as the Rubik's cube group is concerned r = L, for example, and M = R L', so I don't understand how adding in these new moves could make a difference.
> 
> I notice the number you quoted is double mine. Are you referring to a redefinition of the Rubik's cube group where the location of the centers in physical space matters? If so, why is the figure doubled rather than quadrupled?



In terms of move sequences, you can't consider r = L. For instance r U does not put the cube in the same state as L U. Because a sequence containing inner layer turns or double-layer turns can change how the centers are placed with respect to "up," "down," "left," etc., you have to consider how a sequence leaves centers permuted as well as corners and edges. That's why you can get higher orders.


----------



## meichenl (Jan 10, 2010)

cuBerBruce said:


> In terms of move sequences, you can't consider r = L. For instance r U does not put the cube in the same state as L U.



That is a trivial objection (r U = L F), but I see your point. This way of thinking about the order of the group elements was not relevant to the problem I was originally considering because the cube is considered solved regardless of its orientation in physical space. 

I also don't see how this increases the maximum possible order of an element to 2520. 2520 = 2^3 * 3^2 * 5 * 7

The centers cannot be in an 8-cycle, 9-cycle, 5-cycle (since this would mean exactly one center is in the correct place), or 7-cycle, so how does adding in permutations of the center help us reach an order 2520?


----------



## SebCube (Jan 10, 2010)

Yes it is called Gods Algorithm but from what I have been told there is one algorithm for each scramble and the figure of moves is at 25


----------



## qqwref (Jan 10, 2010)

meichenl said:


> That is a trivial objection (r U = L F)



No, not at all. r U and L F are not the same when you are talking about doing move sequences over and over again: doing r U r U ... will have a much different effect than doing L F L F .... That is why doing double layer turns is not quite the same as doing single layer turns, because when you do the sequence again you do it without reorienting the cube, so the orientation matters a lot.


----------



## meichenl (Jan 10, 2010)

qqwref said:


> No, not at all. r U and L F are not the same when you are talking about doing move sequences over and over again: doing r U r U ... will have a much different effect than doing L F L F .... That is why doing double layer turns is not quite the same as doing single layer turns, because when you do the sequence again you do it without reorienting the cube, so the orientation matters a lot.



I didn't say r U r U = L F L F. I said r U = L F. r U r U = L F L D. You can similarly change any sequence with double layer turns into an equivalent sequence of single layer turns. Double layer turns do not add anything.

Edit: Okay, I think I see your point. Doing r U over and over isn't the same as doing L F over and over. That makes sense. It threw me off because this is not the order of a group element in the standard Rubik's cube group any more - two cubes that are related to each other solely by cube rotations have to be considered different scrambles in order for this definition to form a group. That seems a strange way of thinking about the cube. Also, I could use an example of something with order 2520, because for the reason I raised before I don't see how including center permutations allows for group elements with higher order.


----------



## cuBerBruce (Jan 11, 2010)

meichenl said:


> Also, I could use an example of something with order 2520, because for the reason I raised before I don't see how including center permutations allows for group elements with higher order.



I mentioned a way to get an order-2520 position in a thread over two years ago ([post=20826]link[/post]).

An order-2520 position can be obtained with misoriented corner cycles of 3 and 5, misoriented edge cycles of 4 and 7, and a 4-cycle of centers. Note that when the centers are in an odd permutation (such as a 4-cycle), the cubie permutation parity for the edges and corners must be opposite, rather than the same. In the above, the centers don't really increase the order. The center permutation merely permits corners and edges to have opposite parity instead of the same parity, allowing a combination that gives an order of 2520 which is not possible when corner parity must match edge parity.


----------



## Lucas Garron (Jan 11, 2010)

meichenl said:


> Also, I should point out that when I said "your computer's hard drive could not store this sequence", I meant that it could not be stored uncompressed.
> 
> Such a sequence actually contains very little information, and one could write a very short program to generate it.


Interesting exercise: Prove that it's easy to come up with a "reasonable" algorithm (on the order of about 10^19 moves) that goes through each state, such that its _n_th move can be computed almost instantly.
You can't really write down the whole algorithm, but you could write down any portion on demand.


----------



## meichenl (Jan 11, 2010)

cuBerBruce said:


> \ The center permutation merely permits corners and edges to have opposite parity instead of the same parity, allowing a combination that gives an order of 2520 which is not possible when corner parity must match edge parity.



Ahh, interesting. Thanks.


----------



## meichenl (Jan 11, 2010)

Lucas Garron said:


> Interesting exercise: Prove that it's easy to come up with a "reasonable" algorithm (on the order of about 10^19 moves) that goes through each state



Maybe you break the Rubik's cube group down into cosets, for example the cosets of <U2, D2, F2, B2, R, L>, then find a mini Devil's algorithm (Beelzebub's Algorithm?) that takes you through each member of the coset. Then you just need a short algorithm that takes you from coset to coset at the completion of each Beelzebub's Algorithm.

If the Beelzebub's Algorithm is too long, you might iterate the process.

Is this the right track at all?


----------



## Lucas Garron (Jan 11, 2010)

meichenl said:


> Lucas Garron said:
> 
> 
> > Interesting exercise: Prove that it's easy to come up with a "reasonable" algorithm (on the order of about 10^19 moves) that goes through each state
> ...


I'm not sure if that works, although it's nice when it does (Floppy?).

I was thinking of something much more straightforward and brainless, since you're allowed to revisit states.


----------



## qqwref (Jan 11, 2010)

What do you mean by "on the order of 10^19 moves", Lucas? There are already 4 times that many states, so I'm not sure how much more leeway you're giving us.

I know an easy way to get an alg that has an upper-bounded length of roughly 8.6 * 10^20, but that's as good as I can prove without a cleverer idea.


----------



## Tim Major (Jan 11, 2010)

Maybe, the person who showed your friend this lied. Maybe he was scrambling say, R U' x50, then gave it to your friend, who continued it. But R U' does not look very scrambled, so maybe the first person, did something that appears to scramble it, but then you're friend just had to keep doing the same thing. One thing that might have already been mentioned, is any sequence of moves must come back to the first state, as long as you keep repeating them. For example, R L U2 F' will eventually solve. However, don't try this, as it could take a very, very long time to come back to the start. R U R' U' x 6 is an example, of a relatively short one.

Edit: Sorry, I didn't realise this was no longer the topic


----------

