• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Solving the cube without any decision making

Tronman

Member
Joined
Jan 8, 2010
Messages
5
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!
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
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

Member
Joined
Jan 8, 2010
Messages
5
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.
 
Joined
Apr 17, 2008
Messages
735
Location
Massachusetts, USA
WCA
2009JOHN07
YouTube
Visit Channel
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)
 

Tronman

Member
Joined
Jan 8, 2010
Messages
5
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!
 
Last edited:

adimare

Member
Joined
Oct 29, 2009
Messages
381
Location
Costa Rica
WCA
2011MARE02
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 :)
 

MichaelP.

Member
Joined
Jun 20, 2009
Messages
755
Location
Texas
WCA
2009PERK02
YouTube
Visit Channel
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

Premium Member
Joined
Oct 12, 2009
Messages
2,757
Location
~100km W of Melbourne, Australia
WCA
2010CARN01
YouTube
Visit Channel
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

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
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. :p)
 

MichaelP.

Member
Joined
Jun 20, 2009
Messages
755
Location
Texas
WCA
2009PERK02
YouTube
Visit Channel
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. :p)

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