Le Rubik’s cube ? Un casse-tête inter-planétaire s’il en est ! Casse-tête qui n’en finit pas de passionner amateurs et mathématiciens comme nous le verrons. Présentation du phénomène en quelques lignes.

• Ce casse-tête fut inventé par Ernö Rubik en 1974. Pour la petite histoire (d’après Wikipédia) :

  L’idée initiale d’Ernö Rubik était de construire le cube afin d’amener ses étudiants à deviner quel était son mécanisme interne, comment les petits cubes pouvaient tourner suivant trois axes tout en restant solidaires, et ainsi de les faire s’intéresser à la géométrie à 3 dimensions. Ce n’est qu’ensuite qu’il eut l’idée (sur la suggestion d’un ami) de colorer chaque face d’une couleur différente, constatant alors qu’après mélange, l’ordre initial du cube s’avérait extrêmement difficile à retrouver. Il eut alors l’idée de le commercialiser en tant que « casse-tête » mathématique.

• L’objet est constitué de $26 = 3^3 -1$ petits cubes (le mécanisme étant caché dans le petit cube central).
• Le nombre de positions possibles pour le cube est de $43 \, 252 \, 003 \, 274 \, 489 \, 856 \, 000$. Ça fait beaucoup ! Plus de 43 milliards de milliards [3]. Une multiplication et une division plus loin pour en déduire que si vous explorez une position du cube à chaque seconde, il vous faudra environ 100 fois l’âge de l’univers pour toutes les passer en revue...

Les records de résolution

Le record actuel est détenu depuis le 26 avril 2015 par Collin Burns en 5,25 secondes.

La vidéo suivante montre un aperçu des derniers championnats du monde qui ont eu lieu l’été dernier à São Paulo. Attention, ça va vite !

Pas mal ! Mais peut-on faire plus rapide ? Réponse : oui ! Le record du monde absolu est détenu depuis le 15 mars 2014 par Cubestormer 3 en 3,253 secondes. Le cerveau de ce robot ARM-Powered est un Galaxy Samsung S4 et ses bras sont faits en LEGO. Attention, ça va très vite !

Mais il se pourrait bien que ce record du monde vole rapidement à son tour en éclat si l’on en croit les prouesses que semble réaliser le robot de Jay Flatlandia et Paul Rose.

Peut-on imaginer faire encore plus rapide ?

J’en ai aussitôt parlé à mon copain Nao [4]. On a travaillé dur... mais sans succès !!! Par contre on s’est bien amusé :-).

Nao, c’est donc ce petit robot humanoïde construit par la société Aldebaran Robotics [5]. Comme Nao a des petits doigts, il est difficile d’imaginer qu’il tienne lui-même le cube, encore moins qu’il puisse faire lui-même les mouvements. Par contre, contrairement à ce qu’on pourrait croire en regardant le film, Nao n’est pas aussi dur de la feuille qu’il n’y paraît ! Simplement il faut lui parler bien en face, compte-tenu de la position de ses quatre microphones qui ne sont pas dans les oreilles, mais sur la tête ! En fait Nao parle par les oreilles !

Que fait exactement Nao dans la vidéo ?

1. Il commence par regarder chacune des six faces du cube et, pour chacune d’elles, il détecte les neuf couleurs présentes. Pour cela il commence par repérer les contours noirs entre les neuf facettes de la face qu’il regarde, et ensuite les couleurs des facettes en question [6]. Quand il a détecté les neuf couleurs présentes sur la face, il annonce la couleur de la facette centrale : on peut alors tourner [7] le cube pour lui montrer une autre face [8].
2. Ensuite il fait le calcul qui permet de résoudre le cube [9].
3. Enfin Nao dicte les mouvements à effectuer, il y en six possibles : haut (Up), bas (Down), gauche (Left), droite (Right), devant (Front), derrière (Back). Et pour chacun d’eux, il faut préciser de combien de quarts de tour tourner dans le sens des aiguilles d’une montre (à savoir 1, 2 ou 3) : par exemple, U2 signifie qu’il faut tourner la face du dessus de deux quarts de tour dans le sens horaire, c’est-à-dire d’un demi-tour (dans n’importe quel sens !). Il ne reste alors plus qu’à écouter et exécuter machinalement les consignes données par Nao. Sans réfléchir, comme un vrai robot !

Comment résoudre un Rubik’s cube ?

Tout ce vous avez toujours voulu savoir sur le cube sans jamais oser le demander est contenu dans un livre dont Michèle Audin parlait dans ce billet. Je vous y renvoie donc sans détour !

Le Rubik’s cube, sur le plan mathématique, c’est un superbe chapitre de théorie des groupes [10]. J’imagine cependant que la plupart des gens qui savent résoudre le cube ne pensent pas nécessairement le problème en termes de groupes, sous-groupes distingués et groupes-quotients mais sait-on jamais... Quoi qu’il en soit, l’algorithme que Nao exécute sur la vidéo précédente et que nous allons maintenant décrire dans les grandes lignes est dû à Morwen Thistlethwaite.

L’algorithme de Thistlethwaite donc est apparu au début des années 80 : il est remarquable en ce sens qu’il permet de résoudre n’importe quel cube en moins de 52 mouvements. À l’époque, ce fut une petite révolution. La mauvaise nouvelle par contre, c’est qu’il est essentiellement impossible pour un humain de l’exécuter car il engendre beaucoup trop de calculs [11]. Mais pour un ordinateur standard, ce n’est vraiment pas un problème.

Morwen Thistlethwaite

Sur le plan théorique, l’algorithme de Thistlethwaite est vraiment un bel objet qui est resté pendant longtemps la méthode de résolution nécessitant le moins de mouvements possibles (52 donc). Les algorithmes de résolution du Rubik’s cube [12] les plus simples procèdent bien souvent en opérant sur chacun des trois étages du cube, étage par étage [13], ou alors opèrent en plaçant d’abord les coins. Ici la stratégie est bien différente et contrairement aux algorithmes les plus standards, il est difficile de se convaincre qu’on est bien en train de résoudre le cube presque jusqu’à la fin ! L’algorithme de Thistlethwaite se décompose en quatre étapes : le sel de l’affaire, c’est de restreindre progressivement les mouvements que l’on s’autorise ! Curieuse idée a priori...

1. Tous les mouvements U, D, L, R, F, B sont autorisés.
2. Seuls les mouvements U, D, L, R, F2, B2 sont autorisés. Autrement dit, on ne peut plus tourner les faces devant et derrière que par des demi-tours.
3. Les mouvements autorisés sont U, D, L2, R2, F2, B2. C’est au tour des faces gauche et droite de ne plus être manipulables que par des demi-tours.
4. On ne s’autorise plus que des demi-tours sur toutes les faces (mouvements possibles : U2, D2, L2, R2, F2, B2).

À la fin de la quatrième étape, le cube est résolu [14].

On trouve sur le web de nombreux sites et vidéos qui donnent tous les détails et permettent de bien comprendre comment fonctionne précisément l’algorithme, jusqu’à pouvoir l’implémenter dans son langage de programmation préféré. On trouve même des vidéos décortiquant la version humaine de l’algorithme, comme par exemple celle-ci.

Par ailleurs, le Rubik’s cube a des grands frères mais aussi un petit frère, le Pocket Cube, que l’on peut facilement tenir dans sa poche et qui est beaucoup plus facile à résoudre bien sûr. Cependant, c’est déjà un challenge passionnant que d’écrire un programme de résolution comme le propose Laurent Théry dans cet article publié sur Interstices.

Penser en terme de groupes comme dans le bloc dépliant ci-dessus quand on cherche des méthodes pour résoudre un problème comme le Rubik’s cube est une idée tout à fait précieuse, avec tout un arsenal de méthodes géométriques et algébriques alors à disposition. C’est infiniment plus efficace comme on s’en doute que de chercher des combinaisons et des astuces un peu au hasard... [15] [16]

Ceci étant, en réfléchissant un peu sur des mouvements très simples, il est tout à fait possible d’inventer son propre algorithme de résolution dès l’âge de 11 ans, comme l’explique Burkard Poster (Mathologer) dans cette vidéo remarquablement claire.

Sur cette page (en anglais), on peut lire une lettre écrite par Thistlethwaite et datée du 13 juillet 1981 où il décrit son algorithme. Il est amusant de lire dans les premiers paragraphes :

« I should perhaps point out that this strategy isn’t easy to perform (even John Conway finds it quite hard !), for two reasons [...] » [17]

Nous sommes donc avertis que ce n’est pas évident de comprendre tous les rouages de cet algorithme. Car John Conway, ses collègues mathématiciens le savent bien, c’est plutôt un garçon malin dont il était d’ailleurs question dans l’article récent Des jeux aux nombres surréels de Lisa Rougetet.

Le nombre de Dieu est 26

Quand on joue à un jeu comme le Rubik’s cube et qu’on finit par résoudre le cube, une question qui vient assez naturellement à l’esprit, c’est : « aurais-je pu le résoudre en moins de coups ? ». Dit autrement, s’il m’a fallu 60 mouvements pour résoudre le cube, pouvait-on le résoudre plus efficacement, disons en 30 coups ?

Petite précision : il faut maintenant dire ce qu’on entend exactement par un mouvement. En fait, il y a deux écoles... l’une est née sur la côte ouest des États-Unis avec les mathématiciens de Stanford [18] et l’autre sur la côte est avec les mathématiciens du MIT [19] :

• l’école du demi-tour : les rotations d’un quart de tour ou d’un demi-tour (ou de trois-quarts de tour) sont considérées comme un seul mouvement ;
• l’école du quart de tour : seules les rotations d’un quart de tour (dans un sens ou l’autre) sont considérées comme un mouvement. Une rotation d’un demi-tour correspond donc à deux mouvements.

Cette petite subtilité étant éclairée, décidons pour la suite de cet article qu’on se rallie à l’école du quart de tour : notre question initiale est désormais bien posée.

Pour les amateurs de théorie des groupes, on peut reformuler cette question à l’aide d’un graphe, c’est-à-dire d’un ensemble de sommets et d’arêtes :

• les sommets de ce graphe sont les 43 milliards de milliards de configurations possibles pour le cube. Le cube résolu correspond à l’un des sommets et nous imaginerons que ce sommet est colorié en vert ;
• deux sommets sont reliés par une arête si on peut passer d’une configuration à l’autre par un seul mouvement.

C’est donc un graphe gigantesque ! Je suis sûr que Poincaré n’aurait pas hésité à écrire...

« On sera frappé de la complexité de cette figure, que je ne cherche même pas à tracer. »

Le graphe que nous avons ainsi décrit porte un nom ; c’est le graphe de Cayley du groupe $G_0$ (engendré par les six mouvements U, D, L, R, F, B) [20]. Ce graphe est naturellement équipé d’une distance [21] sur les sommets : il suffit de compter le nombre d’arêtes minimal reliant les deux sommets en question. On peut alors changer légèrement notre question initiale pour la reformuler ainsi :

Quelle est la distance la plus grande possible au sommet vert ? [22] Autrement dit, quels sont les cubes « les plus mélangés » et à quelle distance sont-ils ?

En août 1998, Michael Reid a démontré que la configuration du cube ci-contre, connue sous le nom de « superflip plus fourspot », est à distance 26. Depuis lors on savait que la réponse à la question précédente était un entier plus grand que 26 [23]. Par ailleurs, puisqu’il n’y a qu’un nombre fini de configurations (43 milliards de milliards), une stratégie évidente consiste alors à considérer chaque configuration du cube et à essayer de la résoudre en moins de 26 coups. Simple sur le plan théorique... mais en pratique la remarque faite en début d’article sur « 100 fois l’âge de l’univers » est toujours d’actualité...

Malgré tout, c’est bien par la voie calculatoire que la réponse est arrivée tout récemment (août 2014) grâce aux efforts et à l’ingéniosité de Tomas Rokicki (programmeur à Palo Alto) et Morley Davidson (mathématicien à Kent State University).

Le tableau ci-dessous est extrait de

la page web de Davidson et Rokicki concernant le théorème précédent. Elle contient d’ailleurs un historique sur les progrès accomplis autour de cette question au fil des années, de l’algorithme de Thistlethwaite (qui assurait une résolution de tout cube en moins de $104 = 2 \times 52$ mouvements dans la métrique du quart de tour) à leur théorème qui assure donc que 26 coups sont toujours suffisants.

Remarquons que la plupart des configurations du cube sont entre 19 et 22 coups. Par ailleurs, il n’y a semble-t-il qu’une seule configuration (et deux autres symétriques) à distance 26 exactement, et deux configurations à distance 25 (et leurs symétriques). Le nombre exact n’est pas encore complètement connu.

Quid de toute cette histoire dans la métrique californienne du demi-tour ? Eh bien, dans ce cas, le nombre de Dieu est de 20 [25]. C’est un théorème à peine plus vieux (juillet 2010) dû à Tomas Rokicki, Herbert Kociemba, Morley Davidson et John Dethridge. À l’époque c’est Google qui avait prêté ses gros bras pour calculer en temps raisonnable l’équivalent de 35 ans de CPU. Dans la vidéo (en anglais) ci-dessous, Morley Davidson raconte l’aventure de cette quête du nombre de Dieu ; quant à la page web du projet c’est par ici.