I was wondering if it's possible to solve a Rubik's cube just iterating a single algorithm. It doesn't matter how complex the algorithm is (as long as it is less than 1 million moves), nor the time required to solve the cube; I just want to know if there exists a "periodic" sequence of moves that allows to turn any valid scrambled configuration to the solved configuration. Once you start executing the algorithm, you can't stop it (unless you finish, of course), rotate the cube and start it on another face.
If the question is still unclear, let's make an example. You have to find a sequence like this one, to be repeated an unlimited number of times, that lets you solve any configuration:
Example: U D R' U' F L' U F' R' U' L D' R to be repeated 12412183213 times!
Note: The above sequence is just an example, 99,999% it's not working!
I just ask you to prove whether such sequence exists or not. If it exists, I would appreciate you to post it, unless it consists of more than 1000 moves.
Answer
Does an algorithm exist?
Yes. Consider every valid state of the Rubik's cube. It can be brought to the solved state in 20 moves or less. For each state, apply the sequence of moves followed by its inverse. This giant algorithm is guaranteed to solve any cube.
Now, does a reasonable-length algorithm exist?
No. I will show that any such algorithm should have length at least 34326986725785600.
Proof
An algorithm of length L, even if applied an infinite number of times, will only go though 1260L states at most. Applying the algorithm once takes it to at most L states. The important thing is that every element in the Rubik's cube group has order 1260 or less. As a result, even if you apply the algorithm any number of times, you will not be able to reach more than 1260L states.
Now, there are 43252003274489856000 valid states of the Rubik's cube. This means that any algorithm which passes through all these states should have length at least 43252003274489856000/1260=34326986725785600
No comments:
Post a Comment