4
$\begingroup$

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

$\endgroup$
12
$\begingroup$

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

Rubik's cube

EDIT: 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).

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Jukka Suomela May 21 '11 at 11:32
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito May 21 '11 at 21:26
  • 2
    $\begingroup$ does the configuration graph of the cube have a Hamiltonian path? $\endgroup$ – Kaveh May 24 '11 at 3:17
  • 2
    $\begingroup$ @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 (permutationpuzzles.org/rubik/webnotes/rubik.pdf), ... $\endgroup$ – Marzio De Biasi May 24 '11 at 19:27
  • 1
    $\begingroup$ @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. $\endgroup$ – Steven Stadnicki May 24 '11 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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