L’informatique du Rubik’s Cube

Mais ce serait commettre une erreur que de nier l’importance du rôle qu’ont les ordinateurs dans la compréhension du puzzle.

C’est ainsi, que se terminait l’article sur La mathématique du Rubik’s Cube. En effet, la science du traitement de l’information permis la découverte de résultats des plus surprenants et notamment l’existence et les caractéristiques de deux algorithmes révolutionnaires.

Le premier de ceux-ci est humblement nommé Algorithme de Dieu ou God’s Algorithm. Effectuer cet algorithme correspond à résoudre le Rubik’s Cube de manière optimale.
Actuellement, l’algorithme qui s’en rapproche le plus – c’est à dire qu’il est possible qu’il manque la solution optimale – est le Two-Phase-Algorithm. Chacune des six faces est nommée en fonction de son nom anglais, la face de gauche sera appelée L (left). L signifie alors un mouvement dans le sens des aiguilles d’une montre de la face en question, L’ le mouvement inverse et L2 une rotation de 180°.

Face Nom anglais Notation
Gauche Left L
Droite Right R
Haute Up U
Basse Down D
Frontale Front F
Arrière Back B

Une séquence de mouvements telle RU’LFD’ est appelée manipulation. Si vous tournez les faces d’un cube résolu et n’utilisez pas les mouvements R, R ‘, L, L’, F, F ‘, B et B’ vous générerez un sous-ensemble de tous les cubes possibles. Ce sous-ensemble est désigné par G1 = {U; D; R2; L2; F2; B2} et se caractérise par la propriété suivante: l’orientation des arêtes et des coins ne peut être modifiée et les arêtes entre les faces haute et basse restent isolées.
La première des deux phases de cet algorithme consiste à chercher une manipulation transformant le cube mélangé en un cube faisant partie de G1.
Dans le cas du cube, l’algorithme parcourt toutes les manipulations de longueur croissante. La fonction h1 dite heuristique estime pour chaque état de cube le nombre de mouvements qui sont nécessaires pour atteindre l’état souhaité. L’heuristique permet l’élagage tout en générant les mouvements, ce qui est indispensable pour une durée des calculs raisonnable. h1 est basée sur des tables de consultation et permet ainsi cet élagage jusqu’à 12 coups à l’avance.
La seconde phase de l’algorithme restaure le cube appartenant désormais à G1 en utilisant uniquement des mouvements de ce sous-groupe. Il restaure ainsi l’emplacement des 8 coins, des 8 arêtes des faces haute et basse et les 4 arêtes de la tranche intermédiaire.
La fonction heuristique h2 ne fait qu’estimer le nombre de mouvements nécessaires pour résoudre le cube, en effet le nombre d’éléments dans G1 est beaucoup trop vaste.
Cependant, l’algorithme ne s’arrête pas quand une première solution est trouvée, mais continue à chercher des solutions plus courtes. Par exemple, si la fonction trouve une solution à 10 mouvements dans la phase 1 suivie par 12 mouvements dans la phase 2 , la deuxième solution pourrait avoir 11 mouvements dans la phase 1 et à seulement 5 dans la phase 2. La longueur de la manipulation de la phase 1 augmente et la longueur de la manipulation de la phase 2 diminue. Si la longueur de la phase 2 atteint zéro, la solution est optimale et l’algorithme se termine.

En juillet 2010, il a été démontré que tout Rubik’s Cube pouvait être résolu en maximum vingt mouvements, c’est « Le nombre de Dieu« . En fait démontrer n’est pas le terme exacte. La procédure fut sensiblement la suivante.

Comment avons-nous fait

Comment avons-nous résolu l’ensemble des 43,252,003,274,489,856,000 positions du Cube?

  • Nous avons séparé les positions en 2,217,093,120 ensembles de 19,508,428,800 positions chacune.
  • Nous avons réduit le nombre d’ensembles dont nous avions besoin pour à 55.882.296 en éliminant les positions présentant une symétrie.
  • Nous n’avons pas trouvé des solutions optimales à chaque position, mais au lieu de cela, des solutions de longueur 20 ou moins.
  • Nous avons écrit un programme qui a résolu un seul ensemble en 20 secondes environ.

http://cube20.org

La décomposition en problèmes plus simples a permis de faire tenir chacun de ces sous-problèmes dans la mémoire d’un PC moderne.
Un million de cubes aléatoires ont été résolus en janvier 2010 par Tomas Rokicki, voici la distribution qu’il obtint:

opt1000000.gif

Le site www.cube20.org propose une approximation de la répartition de la totalité des comparaisons, le graphe correspondant est présenté ci-dessous:

Graphe png.png

Nous pouvons enfin savoir que si nous mettons plus de vingt mouvements pour résoudre le Rubik’s Cube, notre incroyablement génial mais limité cerveau ne nous a pas donné la meilleure solution.

Cependant, n’existerait il pas une méthode plus simple qui ne nécessiterait ni intuition, ni logique, ni apprentissage? À vrai dire si. Les cubeurs appellent ça l’algorithme du Diable (ou Devil’s Algorithm). C’est un algorithme qui à partir de n’importe quelle configuration permettrait par simple itération de celui-ci de résoudre le casse-tête. Il est évident que ce dernier devra parcourir toutes les configurations du cube et un être humain pourrait mettre plusieurs milliards d’années à effectuer l’algorithme avant qu’il ne parvienne en effet à résoudre le puzzle. Mais l’avantage de cette méthode c’est qu’elle n’est pas limitée aux êtres intelligents et au sens où je l’entend tous les humains sont des êtres intelligents. On pourrait se dire qu’une suite aléatoire de mouvement suffit pour constituer l’algorithme du Diable mais non. Car tous les algorithmes sont périodiques. C’est une des conséquences du fait que l’ensemble des permutations forme un groupe.
La période d’un algorithme est le nombre d’itérations nécessaires à ce qu’il s’annule lui même. Par exemple l’algorithme RUR’U’ répété six fois s’annule. Nous cherchons donc un algorithme dont la période est de 43 trillions. Ainsi toutes les configuration seraient passées en revue et à un moment nous arriverons à la position de départ. Maintes et maintes fois des cubeurs ont cru enfin le maîtriser mais l’expérience eu raison de leurs algorithmes.

Enfin, le problème de circuit hamiltonien pour le Rubik’s Cube a une solution!

http://bruce.cubing.net/ham333/rubikhamiltonexplanation.html

Néanmoins, le problème semble enfin avoir été résolu. Dans le cadre de ce projet, l’ensemble des postions est vu comme un graphe1 où chaque point correspond à une configuration. Un circuit Hamiltonien étant un circuit passant par tous les sommets du graphe une fois et une seule. De plus aucune rotation d’un demi-tour n’est effectuée.
Ce circuit a été construit de manière hiérarchique en utilisant les sous-groupes imbriqués suivants:
{UR}
{U; R}
{U; R; D}
{U; R; D; L}
{U; R; D; L; F}
Le dernier de ces sous-groupes correspond en fait à celui du cube. Le circuit est donc constitué de rotations de seulement 5 des 6 faces du cubes; aucune rotation de la face arrière n’est utilisée.
Le groupe cyclique {UR} est composé de 105 éléments. Le circuit de Hamilton pour ce groupe est tout simplement la séquence de deux mouvement UR répétée 105 fois. Ainsi, le nombre de positions atteintes dans un tel cycle est de 2*105 = 210. Ce sous-groupe peut être séparé en 73483200/210 = 349920 parties, chaque partie étant un cycle similaire de 210 mouvements. Il est de former des cycles plus grands en connectant ces cycles. Ainsi, trouver un circuit hamiltonien pour le sous-groupe {U; R} a été relativement facile à réaliser de cette manière.
La procédure a été réitérée pour parvenir à trouver des circuits hamiltoniens pour des groupes de plus en plus complexes jusqu’à l’exploit.

Le fichier texte mis à disposition par l’auteur pèse 200 millions d’octets et de très nombreuses informations sont encodées, ainsi t(150,540) renvoie à une séquence de 390 mouvements. L’algorithme du diable dépasse ainsi le milliard de mouvements, le pire scénario possible est le suivant: vous vous trouvez dans la configuration suivant directement l’état résolu dans le circuit Hamiltonien. Supposons que vous connaissez l’algorithme sur le bon des doigts et que vous réalisez 10 mouvements chaque seconde, il vous faudra environ quatre ans pour l’exécuter au rythme de 20 heures chaque jour. Et pour résoudre le cube ? Il vous faudra 1.6446879e+20 années, 12 billions de fois l’âge de l’univers… mais aucune intelligence.

rubik202x220ouv

Rubik’s Cube 2x2x2

Il est également intéressant de noter que quelques temps auparavant, ce même cubeur parvint à trouver un circuit hamiltonien pour le cube de côté 2 traversant toutes les 3 674 160 positions en utilisant exclusivement des rotations des faces haute, droite et frontale. 3 725 189 mouvements le composent, et le pire scénario nous amènerai à 43 371 années pour la résolution mais une fois de plus aucune intelligence. En comparaison, le record du monde de résolution d’un tel cube est de 0,49s et 40 personnes différentes ont officiellement résolus ce cube en moins d’une seconde en compétition… dont 1 français.

Cependant, ici le plus intéressant demeure le fait que ce n’est pas expérimentalement qu’il a été mis au point mais bien à l’aide d’une démonstration. Preuve ultime – si elle est nécessaire – de la déraisonnable efficacité de la mathématique.

Sources

Pour aller plus loin

 


  1. Pour plus d’informations sur les graphes: Théorie des graphes 
Publicités

Une réflexion sur “L’informatique du Rubik’s Cube

  1. Pingback: La mathématique du Rubik’s Cube | Abstraction mathématique

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s