<p>Copy/paste from another (slightly different) <a href="https://cstheory.stackexchange.com/questions/6682/synchronizing-sequences-for-rubiks-cube">cstheory question</a> on Rubik's cube:</p>

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

<p><em>For an arbitrary permutation group with a given generating set, is its Cayley graph Hamiltonian?</em></p>

<p>There are some good info available online, you can download the lecture notes by W.D.Joyner: <em><a href="http://www.permutationpuzzles.org/rubik/webnotes/rubik.pdf" rel="nofollow noreferrer">Mathematics of the Rubik's cube</a></em> (downloadable in pdf format).</p>

<p>Chapter 6 of the lecture notes is devoted to <em>Cayley graphs</em> and <em>God's algorithm</em>.</p>

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

<ul>
<li>let $k$ be the total number of wrong configurations;</li>
<li>for every wrong configuration $W_i, 1 \leq i \leq k$ write down the solving sequence of moves $S_i$;</li>
<li>let $S_i^{-1}$ be the inverse sequence of $S_i$;</li>
<li>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 <em>"look at the cube"</em> to see when to stop (there is no "synchronizing sequence").</li>
</ul>

CC BY-SA 3.0
2012-05-04T14:27:52.810Z
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.
Ankur
CC BY-SA 3.0
2012-05-04T14:32:29.107Z
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?
Ankur
CC BY-SA 3.0
2012-05-04T15:35:11.000Z
@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 :-(
Marzio De Biasi
CC BY-SA 3.0
2012-05-04T16:16:36.097Z
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.
Ankur
CC BY-SA 3.0
2012-05-03T21:31:43.470Z
2012-05-04T07:27:05.417Z
2017-04-13T12:32:28.080Z
Marzio De Biasi
<p>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|}.
$$</p>

CC BY-SA 3.0
2012-05-04T04:39:43.237Z
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.)
Jeffε
CC BY-SA 3.0
2012-05-04T04:12:07.533Z
2012-05-04T04:12:07.533Z
Yuval Filmus
<p>Dear Mods: this may be a non-research question, but I am asking it because from my knowledge, the question appears nontrivial. </p>

<p>This <a href="http://www.youtube.com/watch?v=il5oEPNASmg" rel="nofollow">video</a> claims that a Rubik's cube can be "solved" from <em>any starting position</em> 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?</p>

<p>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?</p>

CC BY-SA 3.0
2012-05-03T19:28:18.960Z
See [Fundamental Algorithms for Permutation Groups](http://www.amazon.com/Fundamental-Algorithms-Permutation-Lecture-Computer/dp/3540549552).  Some key words are [Strong Generating Sets](http://en.wikipedia.org/wiki/Strong_generating_set) and the [Schreirer-Sims algorithm](http://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm).
user834
CC BY-SA 3.0
2012-05-04T00:07:14.583Z
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.
Ankur
CC BY-SA 3.0
2012-05-04T07:30:00.483Z
@Ankur: I updated the answer, see if it matches what you are asking (but perhaps I'm still interpreting it wrongly).
Marzio De Biasi
CC BY-SA 3.0
2012-05-04T13:44:18.870Z
You're looking for a single generator for the entire group?
Peter Taylor
<co.combinatorics><board-games>
Permutations of maximum period: applications to Rubik's cube
Ankur
# Permutations of maximum period: applications to Rubik's cube

(Asked by: username_0 on 2012-05-03)

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

This [video](http://www.youtube.com/watch?v=il5oEPNASmg) 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?

**Tags:** co.combinatorics, board-games
> **Comments:**
> **username_1**: See [Fundamental Algorithms for Permutation Groups](http://www.amazon.com/Fundamental-Algorithms-Permutation-Lecture-Computer/dp/3540549552).  Some key words are [Strong Generating Sets](http://en.wikipedia.org/wiki/Strong_generating_set) and the [Schreirer-Sims algorithm](http://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm).  
> **username_0**: 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.  
> **username_2**: @Ankur: I updated the answer, see if it matches what you are asking (but perhaps I'm still interpreting it wrongly).  
> **username_3**: You're looking for a single generator for the entire group?  

---

## 2 answers

### Answer by username_2 on 2012-05-03. Score: 4 | Accepted answer

Copy/paste from another (slightly different) [cstheory question](https://cstheory.stackexchange.com/questions/6682/synchronizing-sequences-for-rubiks-cube) 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](http://www.permutationpuzzles.org/rubik/webnotes/rubik.pdf)* (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").

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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?  
> **username_2**: @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 :-(  
> **username_0**: 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.  

---

### Answer by username_4 on 2012-05-04. Score: 2

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|}.
$$

> **Comments:**
> **username_5**: 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.)  

---

