Twenty-two moves suffice for Rubik's Cube\(^{\circledR }\) (Q968801)

The Rubik's cube is, as virtually everyone is aware, a mechanical puzzle with remarkable connections to finite groups. Indeed, its approximately \(4.3\times 10^{19}\) distinct configurations may be put in a natural one-to-one correspondence with the elements of a group \(G\). Denote the faces of our cube puzzle by \(F\), \(B\), \(L\), \(R\), \(U\), \(D\). The group \(G\) is generated by the ``quarter-turn'' moves which rotates a given face of the puzzle by \(90^o\). Abusing notation, we denote these six generators by their corresponding face. The Cayley graph of the group with respect to the generators \({\mathcal{Q}}=\{F,F^{-1},\dots, D, D^{-1}\}\) gives rise to a notion of a distance function \(d_{\mathcal{Q}}\) on \(G\) called the ``quarter-turn metric''. If \(g,h\in G\) then \(d_{\mathcal{Q}}(g,h)\) is the length of the shortest word expressing \(gh^{-1}\) in the generators \({\mathcal{Q}}\). The Cayley graph of the group with respect to the generators \({\mathcal{F}}=\{F,F^2,F^3=F^{-1},\dots, D, D^2, D^3=D^{-1}\}\) gives rise to a notion of an analogous distance function \(d_{\mathcal{F}}\) on \(G\) called the ``face-turn metric''. It is not (yet) known what the values of \[ D_{\mathcal{Q}} = \max_{g,g'\in G} d_{\mathcal{Q}}(g,g'), \quad\text{and}\quad D_{\mathcal{F}} = \max_{g,g'\in G} d_{\mathcal{F}}(g,g'), \] are, at the time of this writing. Sometimes the determination of these is referred to as ``finding God's number,'' the analog of climbing Mt. Everest in computational group theory. Previously (i.e., before Rokicki arrived on the scene), it was known that \[ 26 \leq D_{\mathcal{Q}} \leq 34,\quad \text{ and }\quad 20\leq D_{\mathcal{F}} \leq 26. \] The author of the paper under review, Tomas Rokicki, has, to this date, come closer than anyone else towards ``scaling this peak''. He (thanks to the render farm at Sony Imageworks) has shown, using massive computer computations and his own improvement of algorithms of Herbert Kociemba, that \[ D_{\mathcal{Q}} \leq 29,\quad\text{ and }\quad D_{\mathcal{F}} \leq 22. \]