L'information vient de tomber. Et quand je dis "vient de tomber", je pense en fait "est tombé en juillet, mais j'ai pris mon temps pour réagir" : le nombre de Dieu est... 20 ! (Et non 42, ce qui est quelque peu décevant)

RC_Superflip
La position du "superflip", qui nécessite au moins 20 mouvements pour être résolu

Comment fait Dieu lorsqu'il doit résoudre un puzzle combinatoire (du genre taquin, tours de Hanoï, Rubik's cube ou problèmes du loup, de la chèvre et du chou) ? Puisqu'il est omniscient et qu'il n'a pas que ça à faire, il va au plus vite : il utilise l'algorithme de Dieu. L'algorithme de Dieu d'un puzzle combinatoire donné est la marche à suivre pour sortir au plus vite de n'importe quelle position du jeu. Le nombre de coup demandé pour se sortir de la pire position du jeu est appelé "nombre de Dieu". Quand on ne donne pas plus de précisions sur le puzzle considéré, c'est qu'il s'agit du Rubik's Cube.

Pour rappel, le Rubik's cube est un très chouette casse-tête, inventé dans les années 70 par Ernő Rubik, professeur d'architecture hongrois, pour amener ses étudiants à réfléchir en 3D. A l'époque, il voulait simplement leur faire deviner comment fonctionnait le mécanisme interne. C'est sur la suggestion d'un ami qu'il colore les faces (blanc/jaune, rouge/orange, bleu/vert : on obtient la face opposée en ajoutant ou enlevant le jaune), et vend son invention comme un casse-tête. Depuis, le jeu s'est décliné sous forme de Rubik's revenge (4x4x4), de Rubik's Professor (5x5x5), de Rubik's domino (3x3x2) ou de Rubik's barrel (Un Rubik's cube tronqué, présenté sous la forme d'un prisme droit à base décagonale...).
Le Cube de Rubik a également servi à toute une flopée de professeurs d'algèbre comme support ludique pour appréhender la théorie des groupes. Même si le jeu est bien compris dans toute sa dimension théorique, ce n'est qu'en juillet dernier que l'équipe de Tomas Rokicki a prouvé, à l'aide d'un stock de bons ordinateurs, que le nombre de Dieu est 20 : n'importe quelle position du cube peut être résolue en  20 mouvements au plus (et il existe des positions nécessitant au moins 20 mouvements).
Corollaire : après avoir mélangé 20 fois un cube de Rubik, on augmente plus vraiment sa difficulté de résolution.

La nouvelle tombe deux ans après la dernière actu du Cube : Tomas Rokicki et John Welborn avaient alors montré que le nombre de Dieu était 20, 21 ou 22.

Découverte du nombre de Dieu
Pour découvrir l'identité du nombre de Dieu, l'idée la plus simple est de tester une par une les 43 252 003 274 489 856 000 positions, en cherchant à chaque fois le nombre minimal de mouvements nécessaires pour la résoudre. Même à raison de un centième de seconde pour chaque position, il faudrait plusieurs millions de millénaires de calculs. Mauvaise méthode, donc.

La méthode utilisée par Tomas Rokicki (programmeur Californien), Herbert Kociemba (professeur de maths allemand), Morley Davidson (mathématicien de l'Ohio) et John Dethridge (ingénieur américain chez Google) procède suivant 5 idées majeures :
- La première a été de découper le problème initial en 2 217 093 120 sous-problèmes : chaque sous-problème consiste en un ensemble de 19 508 428 800 positions à résoudre (pour être précis : ces ensembles s'obtiennent comme classes suivant le sous-groupe engendré par les positions {U,F2,R2,D,B2,L2} ). Cette partition permet entre autre de rentrer dans la mémoire d'un PC (mais aussi, permet aux algorithmes inventé par l'équipe de Tomas de fonctionner au mieux)
- Deuxième idée : supprimer les redondances, les "symétries". Si vous prenez votre Rubik's cube mélangé et que vous le posez à l'envers, il ne demandera pas plus de mouvements pour être résolu... Puisqu'il y a 24 façons d'orienter un cube dans l'espace (48 avec un miroir), on peut diminuer fortement le nombre de cas à traiter en éliminant les sous-problèmes qui s'obtiennent par symétrie à partir d'un autre. On passe alors à 55 882 296 sous-ensembles de 19 508 428 800 positions à traiter.
- Troisième idée : ne pas chercher les solutions optimales. Depuis janvier 1995, on sait qu'il existe au moins une position du cube qui demande au minimum 20 déplacements pour être résolu : c'est la position du "superflip", découverte par Michael Reid. Pour chaque position du cube, on cherche jusqu'à découvrir une séquence de moins de 20 mouvements, pas la peine de chercher à savoir si on peut faire moins (seule la borne supérieur nous intéresse pour le moment). Rien que ça, ça permet de diviser par 10000 les temps de calculs...
- Quatrième idée : programmer intelligemment. Ce qui permet tout de même de traiter chaque ensemble de 19 508 428 800 positions en moins de 20 secondes.
- Cinquième idée : travailler chez Google. En utilisant la puissance de calcul partagé du géant américain, le problème a été résolu en seulement quelques secondes...

Autre fait intéressant de leur étude : les positions demandant au moins 20 mouvements sont plutôt rares. En mélangeant au hasard le cube, on a qu'une chance sur 144 000 000 000 ("144 milliards") de tomber sur une position demandant autant de mouvements. Une position prise au hasard demandera en moyenne 17,7 mouvements pour être résolue.

Le groupe de Rubik
Sur un Rubik's cube, il existe 18 mouvements élémentaires possibles : ce sont les rotations de l'une des 6 faces de 90°, -90° ou 180°. On utilise les lettres F, B, U, D, L et R pour désigner les rotations d'un quart de tour dans le sens des aiguilles d'une montre des faces avant (front), arrière (back),  haute (up), basse (down), gauche (left) et droite (right). Pour parler de la rotation dans le sens contraire, on ajoute le symbole ', et on ajoute "2" pour le demi-tour d'une face. Ainsi, l'expression U2F' désigne la manœuvre du cube consistant à tourner d'un demi-tour la face haute, et d'un quart de tour dans le sens inverse des aiguilles d'une montre la face avant.

On appelle manœuvre une succession de mouvements élémentaires :
- Une manœuvre suivie d'une manœuvre est encore une manœuvre
- L'opération "suivie de" (notée *) est transitive : si A, B et C désignent des manœuvres, les manœuvres A*(B*C) et (A*B)*C sont les mêmes
- La manœuvre qui consiste à ne pas toucher le cube est une manœuvre (appelée manœuvre identité)
- Une manœuvre est toujours réversible

Pour toutes ces raisons, l'ensemble G des manœuvres du Rubik's Cube forment un groupe, au sens mathématique du terme. Quand on parle de "manœuvre", on ne tient pas compte de sa décomposition en mouvements de base, on considère simplement la permutation des petits cubes : ainsi, les manœuvres UDRR et DUR2 sont les mêmes. Il y a autant de manœuvres que le cube a de positions (et le problème du nombre de Dieu consiste à décrire chaque manœuvre comme suite de mouvements élémentaires).

La théorie des groupes nous permet de dire tout un tas de choses intéressantes sur le Rubik's cube. Notamment, puisqu'il n'existe qu'un nombre fini de positions du cube, le groupe G des manœuvres est fini, et donc, tout élément est d'ordre fini. Traduction : quand on part d'un cube non mélangé et que l'on exécute tout le temps la même séquence de mouvements, on retombera forcément un moment ou un autre sur la position initiale.
Par exemple, la manœuvre R'U2BL'FU'BDFUD'LD2F'RB'DF'U'B'UD' (le "superflip", qui inverse chaque arrête) est une manœuvre d'ordre 2 (en l'exécutant deux fois de suite, on retombe sur sa position de départ). La manœuvre U, quant à elle, est une manœuvre d'ordre 4. Au maximum, un élément peut être d'ordre 1260 (comme par exemple UR'UF'D2), et il n'existe que 73 ordres possibles.

Autre fait d'arme important de la théorie des groupes appliquée au Rubik's Cube : en démontant son cube et en le remontant au hasard, il n'y a qu'une chance sur 12 pour qu'il soit à nouveau soluble. C'est par ce moyen que l'on trouve qu'il y a environ 43 trillions de configurations possibles sur un Rubik's Cube. Et si en plus, on s'amuse à mettre des photos sur les différentes faces, on passe à 88 580 102 706 155 225 088 000 configurations possibles ! (Quand on ajoute des photos, l'orientation des centres des faces devient important !)

Il y aurait encore beaucoup de choses à dire, notamment sur la caractérisation des mouvements licites, sur le dévissage du groupe de Rubik, sur son groupe dérivé, son centre, ses sous-groupes ou sur ses générateurs !...


Sources :
Cube20.org : La page officielle du théorème
Théorie des groupes - Rubik's cube : le site parfait pour tous les gens qui se trouvent à l'intersection exacte de l'ensemble des fans du Rubik's Cube et celui des fans de la théorie des groupes
Francocube : pour les débutants qui voudraient une bonne fois pour toute remonter leur cube