2
$\begingroup$

Dear Mods: this may be a non-research question, but I am asking it because from my knowledge, the question appears nontrivial.

This video claims that a Rubik's cube can be "solved" from any starting position with the repeated application of two fixed moves. The method is easily seen as wrong because the specific moves he suggests actually leave the bottom right $2\times 2 \times 3$ block unaffected. My question is more general: does there exist a finite set of moves which if applied repeatedly from any starting position, yield a solved Rubik's cube?

Moves can be thought of as permutations on the set configurations of a Rubik's cube. A solved Rubik's cube is a specific configuration of interest. If these moves get you from any configuration to a solved configuration, then (by symmetry) these moves must get you from any configuration to any other configuration. This means these moves constitute a permutation of maximum period. Does such a permutation even exist? What is known about the existence of such a permutation?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ See Fundamental Algorithms for Permutation Groups. Some key words are Strong Generating Sets and the Schreirer-Sims algorithm. $\endgroup$
    – user834
    May 3, 2012 at 19:28
  • $\begingroup$ Thanks. I'd appreciate if someone can help me with an answer to "Does such a permutation even exist?" and possibly mention sufficient conditions for existence of such permutations. $\endgroup$
    – Ankur
    May 4, 2012 at 0:07
  • $\begingroup$ @Ankur: I updated the answer, see if it matches what you are asking (but perhaps I'm still interpreting it wrongly). $\endgroup$
    – Marzio De Biasi
    May 4, 2012 at 7:30
  • $\begingroup$ You're looking for a single generator for the entire group? $\endgroup$
    – Peter Taylor
    May 4, 2012 at 13:44

2 Answers 2

Reset to default
4
$\begingroup$

Copy/paste from another (slightly different) cstheory question on Rubik's cube:

"What is the shortest sequence that scans all cube's configurations", or "does the configuration graph of the cube have a Hamiltonian path?" is a special case of a more general unsolved problem:

For an arbitrary permutation group with a given generating set, is its Cayley graph Hamiltonian?

There are some good info available online, you can download the lecture notes by W.D.Joyner: Mathematics of the Rubik's cube (downloadable in pdf format).

Chapter 6 of the lecture notes is devoted to Cayley graphs and God's algorithm.

EDIT: If I correctly interpret the question "Does such a permutation even exist?", the answer is yes (the Cayley graph of a finite group is connected); a trivial argument:

  • let $k$ be the total number of wrong configurations;
  • for every wrong configuration $W_i, 1 \leq i \leq k$ write down the solving sequence of moves $S_i$;
  • let $S_i^{-1}$ be the inverse sequence of $S_i$;
  • obviously the (long) sequence $S_1 \cdot S_1^{-1} \cdot S_2 \cdot S_2^{-1} ... \cdot S_{k-1}^{-1} \cdot S_{k-1}^{-1} \cdot S_k$ will lead you to the solved configuration from any wrong starting configuration, but you must "look at the cube" to see when to stop (there is no "synchronizing sequence").
Improve this answer
$\endgroup$
4
  • $\begingroup$ You are right. Now that I think about it, one can do a brute force application of all combinations of solving sequences to and get from one configuration to another "eventually". For application to practically solving Rubik's cube, we would have to put restrictions on what can be called a "move" (in particular, on how many elementary moves it can involve) and ask for that move to have maximum period. But if one allows an arbitrary finite sequence of elementary moves, by your construction a suitable permutation would exist. $\endgroup$
    – Ankur
    May 4, 2012 at 14:27
  • $\begingroup$ Mods: is there a way to mark two answers as correct or do I have to choose one? Is there a canonical rule by which one is to be picked? $\endgroup$
    – Ankur
    May 4, 2012 at 14:32
  • $\begingroup$ @Ankur: or accept Yuval's one (more formal), I edited mine after reading your comment, but before reading Yuval's answer, and found that it's the same only after saving it :-( $\endgroup$
    – Marzio De Biasi
    May 4, 2012 at 15:35
  • $\begingroup$ I agree with Yuval. Marzio's answer also has other information and is perhaps a better one to keep at the top of the list. It is also chronologically first. I'll accept it. $\endgroup$
    – Ankur
    May 4, 2012 at 16:16
2
$\begingroup$

You asked whether there exists a finite set of moves which if applied repeatedly from any starting position, yield a solved Rubik's cube. Then you asked a harder question. The former question has a simple solution. Enumerate the group of permutations of the Rubik cube: $G = \{g_1,\ldots,g_{|G|}\}$. Every $g_i$ can be realized as some sequence of moves which we will identify with $g_i$. The following sequence answers your question: $$ g_1, g_1^{-1}, g_2, g_2^{-1}, \ldots, g_{|G|}. $$

Improve this answer
$\endgroup$
1
  • $\begingroup$ In light of the video, I think he meant something else by "applied repeatedly" in his first question. (My first reaction was also "Sure, five is enough: a quarter turn of each face but one." but then I watched the video.) $\endgroup$
    – Jeffε
    May 4, 2012 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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