6
$\begingroup$

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.

|improve this question
$\endgroup$
  • $\begingroup$ Do you require the cube to be completed at the end of the sequence, or is completion mid-sequence acceptable? $\endgroup$ – Ian MacDonald Apr 9 '15 at 20:05
  • $\begingroup$ The algorithm stops when you reach the final configuration, even if you haven't completed the sequence yet! $\endgroup$ – leoll2 Apr 9 '15 at 20:06
  • $\begingroup$ Well it's easy to prove existence of a sequence of moves that goes through every possible position. However, I am not sure if this answers your question, as it is only repeated once and thus not periodic per se. EDIT: Also, am I only allowed to do moves from the face I am looking at? $\endgroup$ – Ben Frankel Apr 9 '15 at 20:21
  • $\begingroup$ I said the number of moves in the sequence doesn't matter, actually I'd like it to be less than 1 Million (reasonably big?). No, you can move all the faces, but you can't break the algorithm and restart it on another face! $\endgroup$ – leoll2 Apr 9 '15 at 20:26
  • $\begingroup$ Such a sequence obviously exists. There are a finite number of cube configurations, meaning there are a finite number of solutions. Construct a sequence of moves with each solution followed by its inverse. It's not optimal, but it certainly provides a sequence that fits your criteria. $\endgroup$ – Ian MacDonald Apr 9 '15 at 20:29
12
$\begingroup$

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

|improve this answer
$\endgroup$
  • $\begingroup$ How do you prove the 1260 thing? $\endgroup$ – leoll2 Apr 10 '15 at 19:30
  • 2
    $\begingroup$ Every algorithm on the Rubik's cube does four things : permute the 8 corner cubes, rotate the corner cubes, permute the 12 edge cubes, flip the edge cubes. The best you can get in terms of permutations are cycles of lengths 7,5,3,2. In addition, you get a factor of 3 from rotation of the corner cubes and a factor of 2 from the flip of edge cubes. Overall the highest order achievable is 1260. This is quite simplified, the proofs usually use group theory. Here is one treatment if you are interested : people.kth.se/~boij/kandexjobbVT11/Material/rubikscube.pdf $\endgroup$ – Raziman T V Apr 10 '15 at 19:43
  • $\begingroup$ I think that you forgot to consider the intermediate configurations of an algorithm! As an example, the algorithm U U U U returns only 1 configuration if fully executed, but it passes through 4 different configurations! $\endgroup$ – leoll2 Apr 11 '15 at 11:14
  • 1
    $\begingroup$ @leoll2 no, that is where the factor of L comes from. $\endgroup$ – Raziman T V Apr 11 '15 at 11:19
9
$\begingroup$

The answer is no for "iterating"/repeating a single algorithm because the maximum order (of a permutation) of an algorithm is 1260, which is not 43 quintillion. In other words, no one move sequence can be repeated more than 1260 times before the cube is restored to the original state it was in before iterating that algorithm.

However, the answer is yes for "executing" a single algorithm. That is, Bruce Norskog constructed a 43 quintillion face quarter turn move algorithm which will go through every single 3x3x3 position exactly once upon completion of execution. http://bruce.cubing.net/ham333/rubikhamiltonexplanation.html

In addition, one can use a J-Perm such as B' U F' U2 B U' B' U2 F B U' to construct the move U, for example, by inserting cube rotations.

For example,

U =

B' U F' U2 B U' B' U2 F B U'

y

B' U F' U2 B U' B' U2 F B U'

y

B' U F' U2 B U' B' U2 F B U'

y2

Animation

And thus it follows that if we allow only cube rotations in between this one move sequences, we can create any of the other (6)(3) = 18 different face turn moves to be able to express any move sequence (any solution) in terms of a single J-perm algorithm and cube rotations.

|improve this answer
$\endgroup$
  • $\begingroup$ But he wanted something less than a million moves $\endgroup$ – JLee Apr 9 '15 at 21:14
  • $\begingroup$ @JLee As this answer points out, that isn't possible. $\endgroup$ – Kevin Apr 9 '15 at 21:23
  • $\begingroup$ @Kevin It says " the answer is yes for "executing" a single algorithm." but the answer is no, since that algorithm is 43 quintillion moves long. $\endgroup$ – JLee Apr 9 '15 at 21:27
  • $\begingroup$ "the maximum order (of a permutation) of an algorithm is 1260" Source? Proven? I think you copied this sentence from another thread, where the algorithm that only allowed 1260 permutations was based on just 4 moves! $\endgroup$ – leoll2 Apr 10 '15 at 19:29
1
$\begingroup$

So, you want a general solution (if it exists), meaning a solution that is independent of the current state of the cube.

Common strategies for solving the cube depend heavily on the current state of the cube. There are around 43 quintillion possible states. Each move brings into view 1 more state, so it seems impossible that a general solution could exist with less than 1 million moves, because you could never even see 1 million states, let alone 43 quintillion.

|improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.