<p><strong>Synchronizing sequence</strong> over a finite state machine: a sequence of state transitions that leads the machine to a known unique final state independently of the (unknown) initial state.</p>

<p>In the Rubik's cube there are obviously no "self stopping" configurations: every move leads to a new configuration, so you are forced to look at the current configuration in order to decide the next move. This implies that a <em>synchronizing sequence</em> (as usually defined) cannot exist.</p>

<p>A trivial demonstration: suppose that $SSEQ = m_1 m_2 m_3 ... m_n$ is a synchronizing sequence of moves that leads to a solved Rubik's cube independently of the initial configuration. Now pick a wrong configuration and apply the reverse sequence $m^{-1}_n m_{n-1}^{-1} ... m_1^{-1}$ where $m_i^{-1}$ is the inverse of move $m_i$ (and is well defined because if you apply the same move to two different cube configurations you cannot obtain the same configuration). This reverse sequence leads to a unique configuration $c_0$. If you apply sequence $SSEQ$ to $c_0$ you obviously don't end to a solved Rubik's cube.</p>

<p>What you can do is to allow to stop every <em>subsequence</em> looking at the content of a particular cube's coordinate. For example run subsequence 1 until corner at (0,0,0) contains the red+yellow+blue block, then proceed to subsequence 2 (which will correctly position another block, and so on. In this case you can reach a known final configuration running a fixed sequence of moves made of <em>subsequences</em> that can stop looking at the content of a fixed sequence of blocks. This is very similar to what is usually called an <strong>homing sequence</strong>.</p>

<p>Perhaps another nice question is "What is the shortest sequence of moves and monitored coordinates that leads to a known final configuration in this <strong>modified homing version</strong>?". </p>

<p>For example to put a known block at monitored coordinate (0,0,0) (asterisk * in the figure), the length of the first trivial subsequence must be 28</p>

<pre><code>F1.rotate, F1.rotate, F1.rotate 
R4.shiftL, R6.shiftL, F1.rotate, F1.rotate, F1.rotate
R4.shiftL, R6.shiftL, F1.rotate, F1.rotate, F1.rotate
R4.shiftL, R6.shiftL, F1.rotate, F1.rotate, F1.rotate
C4.shiftDown, C6.shiftDown, F1.rotate, F1.rotate, F1.rotate
C4.shiftDown, C6.shiftDown, F1.rotate, F1.rotate, F1.rotate
</code></pre>

<p><img src="https://i.sstatic.net/LzMGx.jpg" alt="Rubik&#39;s cube"></p>

<p><strong>EDIT:</strong>
Another interesting question (suggested by Tsuyoshi and Kaveh in the comments) arise if we consider the case in which the sequence of moves automatically stops when the cube is solved: if no information is gathered/stored during the moves then we must scan all cube's configurations (similar configurations obtained rotating the whole cube should be grouped in equivalence classes).</p>

<p>But what is the shortest sequence that scans all cube's configurations, or better <strong>does the configuration graph of the cube have a Hamiltonian path?</strong>.</p>

<blockquote>
This 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?
</blockquote>

<p>There are some good info available online, I cite the book: <em><a href="http://rads.stackoverflow.com/amzn/click/0801869471" rel="nofollow noreferrer">Adventures in Group Theory: Rubik's Cube, Merlin's Machine, and Other Mathematical Toys</a></em> and 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>

CC BY-SA 3.0
2011-05-21T11:32:00.250Z
Some nitpicking: "every move leads to a new configuration" does *not* imply that there is no synchronizing sequence. For example, it is easy to construct a state machine $M$ with 3 states such that (1) for any state and any input $M$ changes its state, and (2) "01" is a synchronising sequence that always leads to state 1, no matter where you start.
Jukka Suomela
CC BY-SA 3.0
2011-05-21T11:46:19.327Z
@Jukka: you're right, I tried to formalize it.
Marzio De Biasi
CC BY-SA 3.0
2011-05-21T21:26:57.277Z
I do not know the asker’s intent, but it might be that the machine automatically terminates if the cube the goal configuration (every face consists of a single color).  Otherwise, as you stated, it is trivial that a synchronizing sequence cannot exist, because every move is a permutation on the set of possible configurations and no move can take two different configurations to the same configuration.
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-21T23:05:16.943Z
@Tsuyoshi : I didn't think of that interpretation! However, if the machine automatically terminates when the cube is solved but no information can be gathered/stored during the moves, I think that the only "synchronizing sequence" that works is the sequence that scans all possible cube's configurations. Another nice question is "What is the shortest length of the sequence that scans all cube's configurations?"
Marzio De Biasi
CC BY-SA 3.0
2011-05-24T03:17:28.273Z
does the configuration graph of the cube have a Hamiltonian path?
Kaveh
CC BY-SA 3.0
2011-05-24T19:27:12.180Z
@Kaveh: It seems that Rubik's cube 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? I found some info on Google: book *Adventures in group theory: Rubik's Cube, Merlin's machine, ...*, *Mathematics of the Rubik's cube* (http://www.permutationpuzzles.org/rubik/webnotes/rubik.pdf), ...
Marzio De Biasi
CC BY-SA 3.0
2011-05-24T19:33:15.197Z
@Vor: There may be some subtle issue here.  If the machine automatically halts whenever the cube is solved, then there are several halting configurations (all of which are obtained by rotating the whole cube from one solved configuration) and therefore I do not think that the sequence necessarily scans all the configurations.  It may be possible to avoid this issue by considering the equivalence classes of configuration under rotations of the whole cube, but I am not sure.
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-24T21:07:06.667Z
@Tsuyoshi: Because the standard 'moves' don't move the center squares on each face, you can fix a particular configuration of those before you start, and then your halting configuration is unique again; this is in fact the canonical approach for the cube.
Steven Stadnicki
CC BY-SA 3.0
2011-05-24T21:19:20.263Z
@Steven: I did not know that.  Thanks!
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-21T10:05:23.830Z
2011-05-24T20:02:36.690Z
2011-05-24T20:02:36.690Z
Marzio De Biasi
<p>Are there any results on the existence of synchronizing sequences for a standard 3x3 rubik's cube? Like a proof that there are none? My google-skills failed me... </p>

<co.combinatorics><automata-theory><puzzles>
Synchronizing sequences for rubik's cube?
Mike
# Synchronizing sequences for rubik's cube?

(Asked by: username_0 on 2011-05-21)

Are there any results on the existence of synchronizing sequences for a standard 3x3 rubik's cube? Like a proof that there are none? My google-skills failed me...

**Tags:** co.combinatorics, automata-theory, puzzles


---

## 1 answers

### Answer by username_1 on 2011-05-21. Score: 12

Synchronizing sequence over a finite state machine: a sequence of state transitions that leads the machine to a known unique final state independently of the (unknown) initial state.
In the Rubik's cube there are obviously no "self stopping" configurations: every move leads to a new configuration, so you are forced to look at the current configuration in order to decide the next move. This implies that a synchronizing sequence (as usually defined) cannot exist.
A trivial demonstration: suppose that $SSEQ = m_1 m_2 m_3 ... m_n$ is a synchronizing sequence of moves that leads to a solved Rubik's cube independently of the initial configuration. Now pick a wrong configuration and apply the reverse sequence $m^{-1}_n m_{n-1}^{-1} ... m_1^{-1}$ where $m_i^{-1}$ is the inverse of move $m_i$ (and is well defined because if you apply the same move to two different cube configurations you cannot obtain the same configuration). This reverse sequence leads to a unique configuration $c_0$. If you apply sequence $SSEQ$ to $c_0$ you obviously don't end to a solved Rubik's cube.
What you can do is to allow to stop every subsequence looking at the content of a particular cube's coordinate. For example run subsequence 1 until corner at (0,0,0) contains the red+yellow+blue block, then proceed to subsequence 2 (which will correctly position another block, and so on. In this case you can reach a known final configuration running a fixed sequence of moves made of subsequences that can stop looking at the content of a fixed sequence of blocks. This is very similar to what is usually called an homing sequence.
Perhaps another nice question is "What is the shortest sequence of moves and monitored coordinates that leads to a known final configuration in this modified homing version?". 
For example to put a known block at monitored coordinate (0,0,0) (asterisk * in the figure), the length of the first trivial subsequence must be 28
F1.rotate, F1.rotate, F1.rotate 
R4.shiftL, R6.shiftL, F1.rotate, F1.rotate, F1.rotate
R4.shiftL, R6.shiftL, F1.rotate, F1.rotate, F1.rotate
R4.shiftL, R6.shiftL, F1.rotate, F1.rotate, F1.rotate
C4.shiftDown, C6.shiftDown, F1.rotate, F1.rotate, F1.rotate
C4.shiftDown, C6.shiftDown, F1.rotate, F1.rotate, F1.rotate


EDIT:
Another interesting question (suggested by Tsuyoshi and username_4 in the comments) arise if we consider the case in which the sequence of moves automatically stops when the cube is solved: if no information is gathered/stored during the moves then we must scan all cube's configurations (similar configurations obtained rotating the whole cube should be grouped in equivalence classes).
But what is the shortest sequence that scans all cube's configurations, or better does the configuration graph of the cube have a Hamiltonian path?.

This 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, I cite the book: Adventures in Group Theory: Rubik's Cube, Merlin's Machine, and Other Mathematical Toys and 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.

> **Comments:**
> **username_2**: Some nitpicking: "every move leads to a new configuration" does *not* imply that there is no synchronizing sequence. For example, it is easy to construct a state machine $M$ with 3 states such that (1) for any state and any input $M$ changes its state, and (2) "01" is a synchronising sequence that always leads to state 1, no matter where you start.  
> **username_1**: @Jukka: you're right, I tried to formalize it.  
> **username_3**: I do not know the asker’s intent, but it might be that the machine automatically terminates if the cube the goal configuration (every face consists of a single color).  Otherwise, as you stated, it is trivial that a synchronizing sequence cannot exist, because every move is a permutation on the set of possible configurations and no move can take two different configurations to the same configuration.  
> **username_1**: @Tsuyoshi : I didn't think of that interpretation! However, if the machine automatically terminates when the cube is solved but no information can be gathered/stored during the moves, I think that the only "synchronizing sequence" that works is the sequence that scans all possible cube's configurations. Another nice question is "What is the shortest length of the sequence that scans all cube's configurations?"  
> **username_4**: does the configuration graph of the cube have a Hamiltonian path?  
> **username_1**: @username_4: It seems that Rubik's cube 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? I found some info on Google: book *Adventures in group theory: Rubik's Cube, Merlin's machine, ...*, *Mathematics of the Rubik's cube* (http://www.permutationpuzzles.org/rubik/webnotes/rubik.pdf), ...  
> **username_3**: @Vor: There may be some subtle issue here.  If the machine automatically halts whenever the cube is solved, then there are several halting configurations (all of which are obtained by rotating the whole cube from one solved configuration) and therefore I do not think that the sequence necessarily scans all the configurations.  It may be possible to avoid this issue by considering the equivalence classes of configuration under rotations of the whole cube, but I am not sure.  
> **username_5**: @Tsuyoshi: Because the standard 'moves' don't move the center squares on each face, you can fix a particular configuration of those before you start, and then your halting configuration is unique again; this is in fact the canonical approach for the cube.  
> **username_3**: @Steven: I did not know that.  Thanks!  

---

