Solving Small Rubik’s Cubes as Slowly as Possible

We make use of the fact that $a{(\mathrm{𝖱𝖴})}^{15}=a$. For even $a$, we observe that $a=a{(\mathrm{𝖱𝖴})}^{15}{𝖱}^0$ and for odd $a$, $a=a𝖴{(\mathrm{𝖱𝖴})}^{14}𝖱=a{(\mathrm{𝖱𝖴})}^{15}$. This suffices to show reflexivity.

For symmetry, suppose $a\sim b$. If $a$ is even, then $b=a{(\mathrm{𝖱𝖴})}^k{𝖱}^{\sigma }$ implies

Similarly, if $a$ is odd, then one can check that $b{(𝖱)}^{1-\sigma }{(\mathrm{𝖱𝖴})}^{14-k}=a$. Thus, $b\sim a$.

Now assume $a\sim b$ and $b\sim c$. We observe that the parity of $b$ is dependent on the parity of $a$ and $\sigma$. In particular, $b$ is even if and only if $\sigma =0$ with $a$ even or if $\sigma =1$ with odd $a$. We now prove that $a\sim c$ by cases depending on the parities of $a$ and $b$:

• $\mathrm{■}$

  ($a$ and $b$ are both even) Since $b\sim c$, then

  $$c=b{(\mathrm{𝖱𝖴})}^{\mathrm{\ell }}{𝖱}^{\tau }=a{(\mathrm{𝖱𝖴})}^k{(\mathrm{𝖱𝖴})}^{\mathrm{\ell }}{𝖱}^{\tau }.$$

• $\mathrm{■}$

  ($a$ is even and $b$ is odd)

  $$c=b𝖴{(\mathrm{𝖱𝖴})}^{\mathrm{\ell }}{𝖱}^{\tau }=a{(\mathrm{𝖱𝖴})}^k\mathrm{𝖱𝖴}{(\mathrm{𝖱𝖴})}^{\mathrm{\ell }}{𝖱}^{\tau }=a{(\mathrm{𝖱𝖴})}^{k+\mathrm{\ell }+1}{𝖱}^{\tau }.$$

• $\mathrm{■}$

  ($a$ and $b$ are both odd)

  $$c=b𝖴{(\mathrm{𝖱𝖴})}^{\mathrm{\ell }}{𝖱}^{\tau }=(a𝖴{(\mathrm{𝖱𝖴})}^k𝖱)𝖴{(\mathrm{𝖱𝖴})}^{\mathrm{\ell }}{𝖱}^{\tau }=a𝖴{(\mathrm{𝖱𝖴})}^{k+\mathrm{\ell }+1}{𝖱}^{\tau }$$

• $\mathrm{■}$

  ($a$ is odd and $b$ is even)

  $$c=b{(\mathrm{𝖱𝖴})}^{\mathrm{\ell }}{𝖱}^{\tau }=(a𝖴{(\mathrm{𝖱𝖴})}^k){(\mathrm{𝖱𝖴})}^{\mathrm{\ell }}{𝖱}^{\tau }=a𝖴{(\mathrm{𝖱𝖴})}^{k+\mathrm{\ell }}{𝖱}^{\tau }.$$

In all cases, $a\sim c$, so $\sim$ is transitive. Since $\sim$ is reflexive, symmetric, and transitive, we conclude the proof. $◀$

Intuitively, we can think of $[a]$ as the set of positions reached by repeating the moves $𝖱$ and $𝖴$ in an alternating manner. If $a$ is even, the first move in the alternating sequence is $𝖱$, and if $a$ is odd, the alternating moves begin with $𝖴$.

First suppose $a$ is even. It can be verified computationally that $\mathrm{𝖱𝖴}$ has order 15 (see Appendix A). So ${[a]}_{even}=\{a{(\mathrm{𝖱𝖴})}^k:k\in \mathbb{N}\}$ has size 15. Then ${[a]}_{odd}={[a]}_{even}𝖱$ also has size 15, so

$◀$

Thus we can equivalently define $[a]$ by

We can visualize the equivalence classes with respect to the graph $G_{⟨𝖱,𝖴⟩}$ as 30-cycles, as illustrated in Figure 6.

Let $Q$ be the graph whose vertex set is $\{[a]:a\in ⟨𝖱,𝖴⟩\}$ and where two vertices $A,B\in V(Q)$ are adjacent if and only if there exists an $a\in A$ and $b\in B$ such that either $a=b𝖴$ or $a=b{𝖴}^{\prime }$. Given two cycle-classes $A=[a]$ and $B=[b]$ that are adjacent in this sense, we are interested in the appearance of $G_{⟨𝖱,𝖴⟩}[A\cup B]$. The following few lemmas explore how a cycle-class interacts with its neighbors.

To check that $f$ is indeed a graph automorphism, let $c,d\in V(G_{⟨𝖱,𝖴⟩})$, and note that $f{(c)}^{-1}f(d)={(b{a}^{-1}c)}^{-1}(b{a}^{-1}d)=c^{-1}d,$ from where

To verify the first condition, we have $f(a)=b{a}^{-1}a=b$. To verify the second condition, let $c,d\in V(G_{⟨𝖱,𝖴⟩})$, and note that $f(cd)=b{a}^{-1}cd=f(c)d.$

For the third condition, suppose without loss of generality that $c\in V(G_{⟨𝖱,𝖴⟩})$ is even (the odd case is almost identical) and observe that

Thus $f$ satisfies the conditions required by the lemma. $◀$

It suffices to show that for all $A,B\in V(Q)$, there exists an automorphism $f$ such that $f(A)=B$. Let $A,B\in V(Q)$, and choose $a\in A$ and $b\in B$ both even. Apply Lemma 10 on $a$ and $b$ to obtain $f$. By Lemma 10, $f$ maps $Q$ to itself, and since $f(a)=b$, we have that $f(A)=B$. $◀$

This can be verified computationally for $a=1_{ℛ}$ (see Appendix A). Thus, we have that $k$ is a multiple of $5$ if and only if $[1_{ℛ}{𝖴}^{\prime }{𝖴}^{\prime }]=[1_{ℛ}{({𝖴}^{\prime }{𝖱}^{\prime })}^k{𝖴}^{\prime }{𝖴}^{\prime }],$ and since $1_{ℛ}$ is the group identity, we have

For an even vertex $a$ where $a\ne 1_{ℛ}$, let $f$ be the automorphism given by Lemma 10 with $f(1_{ℛ})=a$. Then, combining Equation 1 with the properties of $f$ given by Lemma 10, we obtain

$◀$

It can be checked that the vertex $[1_{ℛ}]$ has degree 5, so by vertex-transitivity (Lemma 11), $Q$ is 5-regular. Let $A\in V(Q)$ and pick any even $a\in A$. By Lemma 12, no two elements in the set are in the same equivalence class, so has size 5. It remains to show that each of these elements is adjacent to $A$ in $Q$. Indeed, for any , $b=a{({𝖴}^{\prime }{𝖱}^{\prime })}^k{𝖴}^{\prime }$ is odd and, solving for $a$ we have $a=b𝖴{(\mathrm{𝖱𝖴})}^k$, so $[b]=[a]=A$. As $a{({𝖴}^{\prime }{𝖱}^{\prime })}^k{𝖴}^{\prime }{𝖴}^{\prime }=b{𝖴}^{\prime }$ is adjacent to $b\in A$, we have that $[a{({𝖴}^{\prime }{𝖱}^{\prime })}^k{𝖴}^{\prime }{𝖴}^{\prime }]$ is adjacent to $A$. $◀$ A visualization of the results of Lemma 12 and Lemma 13 (In particular, the $5$-regularity of $Q$) is shown by Figure 7.

Let ${\pi }_Q=S_1{S}_2\mathrm{\dots }{S}_m$ be a shortest path in $Q$ from $[1_{ℛ}]$ to $[a]$.

By Lemma 13, for all $i$ such that , given an even vertex $a_i\in S_i$, there exists a unique $k_i$ (based on $a_i$ and $S_{i+1}$) such that $10\le k_i\le 14$ and $a_i{({𝖴}^{\prime }{𝖱}^{\prime })}^{k_i}{𝖴}^{\prime }{𝖴}^{\prime }\in S_{i+1}$.

Consider the sequence $a_1,\mathrm{\dots },a_m$ defined by $a_1:=1_{ℛ}$ and $a_{i+1}:=a_i{({𝖴}^{\prime }{𝖱}^{\prime })}^{k_i}{𝖴}^{\prime }{𝖴}^{\prime }$ for $1\le i\le m-1$. Intuitively, this is the same as constructing our path greedily; we construct our ${\pi }_1$ such that ${\pi }_1$ covers as much of each $S_i$ as possible whilst traversing $S_1{S}_2\mathrm{\dots }{S}_m$.

For , let ${\pi }_{1_i}$ be the path that starts at $a_i$ and records the positions visited by the sequence of moves ${({𝖴}^{\prime }{𝖱}^{\prime })}^{k_i}{𝖴}^{\prime }$, ending on $a_i{({𝖴}^{\prime }{𝖱}^{\prime })}^{k_i}{𝖴}^{\prime }$. Note $a_m$ is even and $a_m\in S_m=[a]$. As $a$ is odd, $a𝖴{(\mathrm{𝖱𝖴})}^{k_m}=a_m$ for some $k_m$ such that $0\le k_m\le 14$. Then $a_m{({𝖴}^{\prime }{𝖱}^{\prime })}^{k_m}{𝖴}^{\prime }=a$. Let ${\pi }_{1_m}$ be the path that starts at $a_m$ and records the positions visited by performing the sequence of moves ${({𝖴}^{\prime }{𝖱}^{\prime })}^{k_m}{𝖴}^{\prime }$, ending on $a$.

Then ${\pi }_1={\pi }_{1_1}{\pi }_{1_2}\mathrm{\dots }{\pi }_{1_m}$ is a path in $G_{⟨𝖱,𝖴⟩}$ that starts on $1_{ℛ}$ and ends on $a$. It remains to show that ${\pi }_1$ satisfies the desired properties.

Note that any even position $a$ in ${\pi }_1$ is followed immediately by $a{𝖴}^{\prime }$, so condition 4 is satisfied. As ${\pi }_1$ visits an equal number of even and odd positions, condition 1 is satisfied as well.

To prove condition 2, suppose for the sake of contradiction that there is an even $b\in {\bigcup }_{[c]\in C}[c]$ such that $b\notin {\pi }_1$, $b𝖴\notin {\pi }_1$, and $[b𝖴]\in C$. Since $[b]\in C$ and ${\pi }_1$ is contained in ${\bigcup }_{j=1}^m{S}_j$, we have that $[b]\in {\pi }_Q$ and $[b𝖴]\in {\pi }_Q$. Suppose $[b]=S_i$.

Since $b\notin {\pi }_1$, it follows that $b=a_i{({𝖴}^{\prime }{𝖱}^{\prime })}^k$ for some . Note $a_i{𝖴}^{\prime }{𝖴}^{\prime }\in S_{i-1}$ (if it exists) and $a_i{({𝖴}^{\prime }{𝖱}^{\prime })}^{k_i}{𝖴}^{\prime }{𝖴}^{\prime }\in S_{i+1}$ (if it exists).

Since $[b𝖴]$ is odd, $[b𝖴]=[b\mathrm{𝖴𝖴}]$, and by Lemma 12, $[b{𝖴}^{\prime }{𝖴}^{\prime }]=[a_i{({𝖴}^{\prime }{𝖱}^{\prime })}^k{𝖴}^{\prime }{𝖴}^{\prime }]$. Because $\mathrm{𝖴𝖴}={𝖴}^{\prime }{𝖴}^{\prime }$, we have that $[b𝖴]=[a_i{({𝖴}^{\prime }{𝖱}^{\prime })}^k{𝖴}^{\prime }{𝖴}^{\prime }]$. Now we note that since , $k$ is neither a multiple of $5$ nor does it differ from $k_i$ by a multiple of $5$, so $[a_i{({𝖴}^{\prime }{𝖱}^{\prime })}^k{𝖴}^{\prime }{𝖴}^{\prime }]$ is neither $S_{i-1}$ nor $S_{i+1}$. Thus, while $[b𝖴]$ and $[b]=S_i$ are both in ${\pi }_Q$, ${\pi }_Q$ does not visit these two vertices consecutively. Since $[b𝖴]$ and $[b]$ are adjacent in $Q$, this contradicts the fact that ${\pi }_Q$ is a shortest path.

To prove condition 3, let $A=S_i$ where . By Lemma 13, $B=[a_i{({𝖴}^{\prime }{𝖱}^{\prime })}^k{𝖴}^{\prime }{𝖴}^{\prime }]$ for some $0\le k\le 4$. Then $d=a_i{({𝖴}^{\prime }{𝖱}^{\prime })}^k$ is in both ${\pi }_1$ and $A$, and

Thus ${\pi }_1$ satisfies all four conditions, as desired. $◀$

By Lemma 11 and Lemma 13, $Q$ is a vertex-transitive graph with valency $5$. Then by Theorem 15, $Q$ has connectivity at least $\frac{2}{3}(5+1)=4$. Thus $Q$ is 4-connected, meaning it is also 2-connected. $◀$

We will now argue that we can extend ${\pi }_1$ to visit more cycles while preserving its properties. Intuitively, we take our original path, find a neighboring cycle, deviate from our original path for a moment and fully fill out an untouched neighboring cycle, and finally pick up where we left off with the original path. An example of such a modification can be seen in the difference between Figure 9(a) and Figure 9(b).

We will case on whether $|C|>1$.

• $\mathrm{■}$

  Case 1. If $|C|=1$, then as $1_{ℛ}\in {\pi }_1$, it follows that $C=\{[1_{ℛ}]\}$, so all vertices in ${\pi }_1$ are in $[1_{ℛ}]$. Then as $𝖴\notin [1_{ℛ}]$, it follows that ${\pi }_1=v_1{v}_2{\pi }_a$ for some path ${\pi }_a$ where $v_1=1_{ℛ}$ and $v_2={𝖴}^{\prime }$.

  Let ${\pi }_b$ be the path that begins on $1_{ℛ}$ and records the positions visited by performing the sequence of moves ${\mathrm{𝖴𝖱}}^{\prime }{({𝖴}^{\prime }{𝖱}^{\prime })}^{14}𝖴$. Then ${\pi }_b$ ends on the position ${\mathrm{𝖴𝖱}}^{\prime }{({𝖴}^{\prime }{𝖱}^{\prime })}^{14}𝖴=\mathrm{𝖴𝖴𝖴}={𝖴}^{\prime }$. A visualization thereof is shown with Figure 9(a) and Figure 9(b). Let ${\pi }_1^{\prime }={\pi }_b{\pi }_a$, so $C^{\prime }=\{[1_{ℛ}],[𝖴]\}$, so $C⊊C^{\prime }$. Since the set of vertices visited by ${\pi }_1^{\prime }$ is exactly the union of the set of vertices visited by ${\pi }_1$ and $[𝖴]$, condition 1 of Lemma 14 is satisfied.

  For condition 2, suppose $b\in \bigcup C^{\prime }$ and $b\notin {\pi }_1^{\prime }$. Then since all vertices in $[𝖴]$ are in ${\pi }_1^{\prime }$, it follows that $b\in \bigcup C$. Then either $b𝖴\in {\pi }_1$, in which case $b𝖴\in {\pi }_1^{\prime }$, or $[b𝖴]\notin C$. In the latter case, either $[b𝖴]=[𝖴]$, which implies $b𝖴\in {\pi }_1^{\prime }$, or $[b𝖴]\ne [𝖴]$, which implies $[b𝖴]\notin C^{\prime }$.

  For condition 3, we only need to check $A=[𝖴]$. Note that all vertices in $A$ are in ${\pi }_1^{\prime }$. By Lemma 13, for any neighboring $B$, there exists an even $d\in A$ such that $B=[d{𝖴}^{\prime }{𝖴}^{\prime }]$. Since $d{𝖴}^{\prime }{𝖴}^{\prime }\in B$ is even, $d{𝖴}^{\prime }{𝖴}^{\prime }{𝖴}^{\prime }=d𝖴\in B$. As all vertices in $A=[𝖴]$ are also in ${\pi }_1^{\prime }$, we have that $d\in {\pi }_1^{\prime }$, and we are done.

  Condition 4 is satisfied because ${\pi }_1^{\prime }={\pi }_b{\pi }_a$, where vertices ${\pi }_a$ satisfy the condition because ${\pi }_a$ is a subpath of ${\pi }_1$ and vertices in ${\pi }_b$ satisfy the condition because ${\pi }_b$ begins on $1_{ℛ}$, an even vertex, and is constructed by the move sequence ${\mathrm{𝖴𝖱}}^{\prime }{({𝖴}^{\prime }{𝖱}^{\prime })}^{14}𝖴$.

• $\mathrm{■}$

  Case 2. If $|C|>1$, then $C\setminus \{[a]\}$ is nonempty. By Lemma 16, the graph of $Q$ with the vertex $[a]$ removed is connected, so there exists a $B\notin C_i$ that is adjacent to some $A\in C_i\setminus \{[a]\}$. By the third clause of Lemma 14, there exists an even $d\in A$ such that $d\in {\pi }_1$ and $d𝖴\in B$. Since $B\notin C$, $d𝖴\notin {\pi }_1$, so the vertex immediately following $d$ in ${\pi }_1$ must be $d{𝖴}^{\prime }$. Note that

  $$d{𝖴}^{\prime }=d\mathrm{𝖴𝖴𝖴}=d{\mathrm{𝖴𝖱}}^{\prime }{({𝖴}^{\prime }{𝖱}^{\prime })}^{14}𝖴.$$

  Let ${\pi }_a$ be the prefix of ${\pi }_1$ that ends at $d$, exclusive. Let ${\pi }_b$ be the path that starts at $d$ and records the positions visited by performing the move sequence ${\mathrm{𝖴𝖱}}^{\prime }{({𝖴}^{\prime }{𝖱}^{\prime })}^{14}𝖴$, ending on the position $d{𝖴}^{\prime }$. Let ${\pi }_c$ be a suffix of ${\pi }_1$ that begins immediately after $d{𝖴}^{\prime }$. Let ${\pi }_1^{\prime }={\pi }_a{\pi }_b{\pi }_c$. Then $C^{\prime }=C\cup \{B\}$, so $C⊊C^{\prime }$. It remains to prove that ${\pi }_1^{\prime }$ satisfies the properties given by Lemma 14. Since ${\pi }_1^{\prime }$ traverses exactly the union of $B$ and the set of points traversed by ${\pi }_1$, condition 1 remains true.

  For condition 2, we have that $C^{\prime }=\{[c]:c\in {\pi }_1^{\prime }\}$. Suppose $b\in \bigcup C^{\prime }$ and $b\notin {\pi }_1^{\prime }$. Then $b\notin {\pi }_1$. Since all points in $B$ are also in ${\pi }_1^{\prime }$, we also have that $b\in \bigcup C$. As ${\pi }_1$ satisfies property 2 from Lemma 14, it follows that either $b𝖴\in {\pi }_1$ or $[b𝖴]\notin C$. If $b𝖴\in {\pi }_1$, then $b𝖴\in {\pi }_1^{\prime }$. Otherwise, $[b𝖴]\notin C$, so either $[b𝖴]=B$, in which case $b𝖴\in {\pi }_1^{\prime }$, or $[b𝖴]\notin C^{\prime }$.

  For condition 3, suppose $A\in C^{\prime }\setminus \{[a]\}$ and $B^{\prime }$ is a neighbor of $A$ with respect to $Q$. We will case on whether $A\in C\setminus \{[a]\}$. If $A\in C\setminus \{[a]\}$, then because ${\pi }_1$ satisfies condition 3, there exists an even $d\in A$ such that $d𝖴\in B^{\prime }$ and $d\in {\pi }_1$, which means $d\in {\pi }_1^{\prime }$ as well. If $A\notin C\setminus \{[a]\}$, then $A=B$. Then there exists a $d\in B$ such that either $d𝖴\in B^{\prime }$ or $d{𝖴}^{\prime }\in B^{\prime }$. If $d𝖴\in B^{\prime }$, then $d$ must be even, since if $d$ is odd, then $d𝖴\in B\ne B$, so we are done. Otherwise, if $d{𝖴}^{\prime }=d{(\mathrm{𝖱𝖴})}^k𝖱\in B^{\prime }$, then $d$ must be odd, so $d𝖴\in A$ is even and $d{𝖴}^{\prime }\in B^{\prime }$ is even. Then $d\mathrm{𝖴𝖴}=d{𝖴}^{\prime }{𝖴}^{\prime }\in B$.

  To show condition 4 is true for ${\pi }_1^{\prime }={\pi }_a{\pi }_b{\pi }_c$, since ${\pi }_a$ and ${\pi }_c$ are both subpaths of ${\pi }_1$ that start on even positions (and ${\pi }_1$ satisfies condition 4), it suffices to show that ${\pi }_b$ satisfies condition 4. This can be verified by observing that ${\pi }_b$ starts on $d$ – which is an even position – and is formed by the move sequence ${\mathrm{𝖴𝖱}}^{\prime }{({𝖴}^{\prime }{𝖱}^{\prime })}^{14}𝖴$.

$◀$ By applying Lemma 17 iteratively, we obtain a path with the properties of ${\pi }_1$ that also visits every cycle, upon which new properties emerge.

Let ${\pi }_{1,1}$ be a path given by Lemma 14, and define $C_i=\{[c]:c\in {\pi }_{1,i}\}$. Given ${\pi }_{1,i}$ satisfying the properties given by Lemma 14, suppose $C_i⊊Q$. Then by Lemma 17, there exists a ${\pi }_{1,i+1}$ such that $C_i⊊C_{i+1}$. By repeating this argument (no more than $|Q|$ times), there is a ${\pi }_{1,n}$ such that $C_n=Q$ and ${\pi }_{1,n}$ satisfies the properties of Lemma 14. Let ${\pi }_2={\pi }_{1,n}$. Note ${\pi }_2$ satisfies properties 1 and 3 by properties 1 and 4 from Lemma 14. Furthermore, $\{[c]:c\in {\pi }_2\}=C_n=Q$ and ${\bigcup }_{[c]\in C_n}{C}_n=G_{⟨𝖱,𝖴⟩}$, so property 2 follows from the property 2 from Lemma 14. $◀$

We will now argue that a path ${\pi }_2$ as described in Lemma 18 can be extended into a Hamiltonian path. We make use of the fact that ${𝖴}^{\prime }=\mathrm{𝖴𝖴𝖴}$. If we have $b\mathrm{𝖴𝖴}$ and $b𝖴$ as consecutive vertices in ${\pi }_2$, and $b$ and $b{𝖴}^{\prime }$ are not in ${\pi }_2$, then we can extend ${\pi }_2$ to include $b$ and $b{𝖴}^{\prime }$ by performing $\mathrm{𝖴𝖴𝖴}$ in place of ${𝖴}^{\prime }$ on $b\mathrm{𝖴𝖴}$.

Since $G_{⟨𝖱,𝖴⟩}$ is vertex-transitive, it suffices to show that for an arbitrary odd $a\in V(G_{⟨𝖱,𝖴⟩})$, there exists a path from $1_{ℛ}$ to $a$ that is Hamiltonian for $G_{⟨𝖱,𝖴⟩}$. Fix $a$. Let ${\pi }_2^{(1)}={\pi }_2$ be a path from $1_{ℛ}$ to $a$ as given by Lemma 18. If ${\pi }_2^{(1)}$ is Hamiltonian, we are done. Otherwise, we claim that there exists a path ${\pi }_2^{(2)}$ from $1_{ℛ}$ to $a$ that satisfies the conditions for ${\pi }_2$ from Lemma 18 and is strictly longer than ${\pi }_2^{(1)}$. If the claim holds, then by repeating this argument (no more than $|G_{⟨𝖱,𝖴⟩}|-1$ times) we must end with a Hamiltonian path.