Twenty-two moves suffice for Rubik's Cube\(^{\circledR }\)
type: Item
instance of: scholarly article
title: Twenty-two moves suffice for Rubik's Cube\(^{\circledR }\)
zbMATH Open document ID: 1192.00010
author: Tomas Rokicki
published in: The Mathematical Intelligencer
publication date: 2010-05-10T00:00:00Z
review text: 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}} …
Mathematics Subject Classification ID: 00A08
Mathematics Subject Classification ID: 00A35
Mathematics Subject Classification ID: 97A80
Mathematics Subject Classification ID: 05C90
Mathematics Subject Classification ID: 20B40
zbMATH DE Number: 5706109
describes a project that uses: OEIS
reviewed by: David Joyner
MaRDI profile type: Publication
full work available at URL: s00283-009-9105-3
OpenAlex ID: W2011989328
Wikidata QID: Q60691922
cites work: Q3589864
cites work: Q5301676
DOI: 10.1007/S00283-009-9105-3
description: scientific article; zbMATH DE number 5706109