16
$\begingroup$

Is there a sequence of moves that can be repeated over and over again which can solve any legal position the Rubik's Cube? If so what is it, and if there's more than one, what's the shortest? If not, prove that it's impossible.

The sequence can be of any length but cannot be broken up into multiple pieces to be executed depending on Rubik's cube patterns; it must, when repeated from start to finish, end in a perfectly solved Rubik's cube.

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ Can you just do all possible (<20 move sequence> followed by <undoing previous sequence>) as a possible solution? (might not be shortest but it'll show one exists) You'll solve the cube at some point. $\endgroup$
    – Sp3000
    Nov 17, 2014 at 0:50
  • $\begingroup$ @Sp3000 That's pretty long, the question asks for the shortest if one exists so. $\endgroup$
    – warspyking
    Nov 17, 2014 at 0:56
  • 3
    $\begingroup$ Mew, was that edit some kind of joke -_- $\endgroup$
    – warspyking
    Nov 17, 2014 at 0:56
  • 3
    $\begingroup$ @warspyking, indeed I hope you liked it :) $\endgroup$
    – Kenshin
    Nov 17, 2014 at 1:07
  • 1
    $\begingroup$ Another potentially interesting question, if anyone cared to solve it, would be the shortest primitive-recursive way of writing such a sequence, if one could define sub-sequences and then unconditionally invoke each sub-sequence in its entirety simply by including its name, so [spaces added for clarity] "1 tr 2 f 1b1 3 22r12" would define "1" as "tr", "2" as "f tr b tr", and "3" as "ftrbtr ftrbtr r tr ftrbtr". $\endgroup$
    – supercat
    Nov 17, 2014 at 18:38

4 Answers 4

Reset to default
17
$\begingroup$

The only way you can have a solve-all sequence is if you have a sequence of moves that goes through all 43 quintillion configurations of the Rubik's Cube. In order to do this, you need to draw a transition graph between all the states of the Rubik's Cube and find a Hamiltonian cycle through them.

This sequence of moves doesn't necessarily have to be 43 quintillion moves long - a simple sequence of 4 moves can produce a cycle of 1,260 configurations as seen in mdc32's answer, and in general a sequence of symbols in the group will produce a cycle of configurations much longer than the cycle itself. However, the sequence will still be very long, simply because 43 quintillion moves is still a lot.

Micah provided a link to a page that did construct such a Hamiltonian cycle in a comment. I haven't been able to make head or tail of its notation (or to figure out how to count the number of moves from the descriptions of the cosets), but it looks like the sequence of moves that is required is billions of moves long, which is still definitely outside of the realm of plausibility for memorization.

Improve this answer
$\endgroup$
14
  • $\begingroup$ It wouldn't necessarily have to be 43 quintillion moves. Mine is only a four move sequence, technically, yet it cycles through 1260 states as you pointed out. $\endgroup$
    – mdc32
    Nov 17, 2014 at 2:11
  • 1
    $\begingroup$ Really? That's really the ONLY way to do this? Wow... Are you sure there isn't like a 4 move sequence that can loop through them all or something? Even if it repeats a position but on a separate move? $\endgroup$
    – warspyking
    Nov 17, 2014 at 2:11
  • $\begingroup$ @mdc32 You're right. For example, in $\mathbb Z_2 \times \mathbb Z_2$, the sequence $(1, 0), (0, 1)$ does result in the whole group being traversed, so the length of the solve-all cycle doesn't necessarily have to be equal to the order of the group. And, as you pointed out, a sequence of 4 moves can generate a 1,260-state cycle. But I don't see there being a solution that's shorter than 10,000 or maybe 10,000,000 moves long. $\endgroup$
    – user88
    Nov 17, 2014 at 2:26
  • 3
    $\begingroup$ It exists. $\endgroup$
    – Micah
    Nov 17, 2014 at 4:31
  • 2
    $\begingroup$ Any sequence loops after at most 1260 repetitions. (src: Wikipedia, Rubik's Cube Group) Therefore, a lower bound on the length of warspyking's sequence is 43 quintillion divided by 1260. $\endgroup$
    – Lopsy
    Dec 16, 2014 at 23:38
5
$\begingroup$

EDIT: This only works in a certain set of configurations, as the loop only goes through 1260 states before returning to the original position. My mistake, this is incorrect, but still useful.

Great solution found here. Basically, if you rotate the right, back, left, and front faces all clockwise and in order, then it will always solve the cube - eventually. The core part of it is in one simple explanation - doing this cannot enter an inescapable loop.

If you move the front face clockwise, then counter-clockwise, nothing happens to the cube. The faces are not moved with respect to each other, and you are in the same position. In order for a loop to happen, two different layouts must lead to the same configuration with the same move. But wait - if you reverse this move, then what position does it go to? The simple answer is this will never happen. Here is a great diagram in the article itself. enter image description here

As you can see, reversing this loop would not work, as there are two possible options. This is a proof that loops will never happen.

Moving these four faces is the shortest possible configuration of moves that affects each and every cube, save for the center ones which are irrelevant anyway. This means it is the shortest possible solution that you could repeat to solve the Cube.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Nice! Good find! $\endgroup$
    – warspyking
    Nov 17, 2014 at 1:46
  • 4
    $\begingroup$ This doesn't work for any configuration - only starting from a solved cube and the 1260 configurations you get while performing that sequence of moves. $\endgroup$
    – user88
    Nov 17, 2014 at 1:46
  • $\begingroup$ @Joe Doesn't this mean it will eventually lead back to a solved cube, assuming the cube can be solved? You can't enter loops, so it should eventually lead back to the solved position. $\endgroup$
    – mdc32
    Nov 17, 2014 at 1:46
  • 6
    $\begingroup$ No; as soon as you perform a move that's outside of the fixed sequence, performing that fixed sequence will never get you back to a solved cube; you'll just get another cycle of 1,260 configurations. $\endgroup$
    – user88
    Nov 17, 2014 at 1:47
  • 3
    $\begingroup$ Note, in general, that any sequence of moves, if repeated enough times, will eventually get back to the original configuration. This is a property of groups. $\endgroup$
    – user88
    Nov 17, 2014 at 2:27
3
$\begingroup$
  • Let's assume there is a sequence $A$, such that for any starting configuration $x$ there exists a number $n(x)$, such that applying $A^{n(x)}$ will solve the cube.
  • It follows that given two configurations $x$ and $y$, we can move from $x$ to $y$ with $A^{n(X) - n(Y)}$. In other words, any sequence can be replaced by repeating A (or its inverse $A^{-1}$) for a specified number of times.
  • From here it follows that given any two sequences: $B$ and $C$, the order of their application does not matter ($BC=CB$), since they are both composed of repeated applications of $A$ and $A^{-1}$.
  • However, this is plainly wrong. It's easy to see that applying the same sequences in a different order can result in a different configuration.
  • Therefore, our assumption was false, and there is no sequence such that its repeated application can solve the cube from any starting configuration.

QED

In mathematical language, the existence of such a sequence will make the Rubik's cube group a cyclic group (a group with 1 generator), and therefore an abelian group (a group with a commutative operation), which we know is wrong. The Rubik's cube group is normally formulated with 6 generators (see here), and can even be formulated with 2 generators (see lemma 7.6 here, h/t comment by Jaap Scherphuis) , but no less.

Why I think some of the other answers here are incorrect:
Finding a Hamiltonian cycle does not satisfy the requirements posed in the question, since we will have to stop your traversal of the cycle when the cube reaches the solved state, whereas the requirement is: "[the sequence] cannot be broken up into multiple pieces to be executed depending on Rubik's cube patterns; it must, when repeated from start to finish, end in a perfectly solved Rubik's cube".

Improve this answer
$\endgroup$
3
  • $\begingroup$ Interesting proof! $\endgroup$
    – justhalf
    May 7, 2021 at 8:44
  • 1
    $\begingroup$ You mention that the Rubik's Cube group has 6 generators. While that is the obvious formulation, where each generator is a basic move, it does not mean that the group cannot be generated by fewer than 6 elements. For example, the two elements represented by the move sequences R2FLD'R' and UBLUL'U'B' generate the whole group (see lemma 7.6 here ). As you say, the group certainly cannot be generated by just one generator, but just two generators are sufficient. $\endgroup$
    – Jaap Scherphuis
    Jun 23, 2021 at 7:50
  • $\begingroup$ @JaapScherphuis - great point, thanks! I incorporated your comment in the answer. $\endgroup$
    – Joe
    Jun 23, 2021 at 8:03
-3
$\begingroup$

single move (sexy move) RUR'U' method youtube video

or 3 moves method (Peter Renzland's method)

These all very humanly intuitive that requires minimal memorization of extra algorithms, but human reasoning.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ I think you misread the question. The question was: "Is there an algorithm you can use from any scrambled configuration and position to solve the 3x3x3 Cube?" The answer is basically Devil's Algorithm. $\endgroup$
    – Kevin Cruijssen
    May 9, 2016 at 8:52

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