Aller au contenu

Algorithmes optimaux de résolution du Rubik's Cube

Un article de Wikipédia, l'encyclopédie libre.

Les algorithmes optimaux de résolution du Rubik's Cube sont un ensemble d'algorithmes dits optimaux (ou sous-optimaux) permettant de résoudre le casse-tête du Rubik's Cube à partir d'un état quelconque du Cube avec un calculateur.

Il a aussi donné lieu à de nombreuses recherches mathématiques et algorithmiques. On précise les représentations mathématiques du groupe des états du Cube et de ses sous-groupes, nécessaires pour la mise en œuvre effective sur calculateur. Pour l'essentiel, il s'agit des représentations par coordonnées introduites par Kociemba[1]. Les algorithmes optimaux sont ceux qui peuvent calculer, pour un état arbitraire du Cube, une formule de taille minimale permettant de revenir à l'état résolu .

Rubik's Cube : représentations de base

[modifier | modifier le code]

Notations et abréviations

[modifier | modifier le code]

On oriente le Cube c'est-à-dire on dit quelle face est le Haut, quelle face est l'Avant , ... ainsi nous avons 6 faces dans cet ordre : (H)aut, (B)as, (A)vant, (P)ostérieure, (G)auche, (D)roite

ces lettres désigne alors des rotations de base ou des rotations standards:

H = 90° dans le sens horaire

H' = -90°

H² = 180°.

Remarque : En notation (anglo-saxonne) c' est . .

Les cubes-arêtes sont notés CA et les cubes-sommets CS. Le terme anglais flip est utilisé pour désigner le basculement d'un cube-arête (valeur binaire 0 ou 1), et twist pour désigner la rotation d'un cube-sommet (valeurs 0, 1, 2 (= -1) en tiers de tours dans le sens des aiguilles d'une montre).

Du point de vue mathématique, désigne l'ensemble des entiers modulo n, et le groupe symétrique des permutations de , dont le cardinal est . La convention est ici de représenter une telle permutation par le vecteur d'entiers images .

Le groupe M des formules, et le groupe G des états

[modifier | modifier le code]

Le groupe des formules du Cube, engendré par les rotations de base est noté .

Une formule est donc une suite finie de rotations de base et leur inverse avec la règle suivante:

HH', BB', AA', PP', GG', DD'  ; interdit

par ex:

C = HB'GDA²H' ⇒ ok

K = ABGDD'PH ⇒ interdit à cause DD'

On pose

HH' = BB' = AA' = PP' = GG' = DD' = I

I = formule neutre (ne rien faire, correspond à la permutation identité id)

On définit sur M une loi de composition '.' concaténation :

1) QT , Q suivi de T ; loi interne

2) QI = IQ = Q  ; élément neutre I

3) Q' = Inverse de Q ; on lit à l'envers prime ↔ non-prime par ex:

C' = HA'²D'G'BH'

QQ' = Q'Q = I

4) Q(TV) = (QT)V ; associative

Ainsi (M,.) forme un groupe, le groupe des formules .

Ces formules Q agissent sur l'état du Cube, qui peut se représenter par une permutation des 48 autocollants (stickers) du Cube (les centres ne bougent pas).

Une formule Q engendre donc un état s on va noter :

 ; lire : Q appliqué sur e donne s, ou s provient de Q

e = état résolu,

On considère que 2 formules donnant le même état sont identiques

Par ex:

AD'A'D = H'DHD'A'HAH'.

Une visualisation d'un état comme une permutation des autocollants se fait donc par un graphique du type suivant.
superflip
État initial → État final : Superflip

Voici la permutation décrite en cycles disjoints : on reconnait les 12 transpositions (2-cycles)=12 arêtes flipés (arêtes basculés).

pQ = {2,36},{5,39},{8,37},{11,34},{13,20}, {14,15}, 16,17},{18,19},{22,44},{25,42},{28,45},{31,47}

Ce SuperFlip = q est produit par la formule Q de taille 20f  :


.


Le nombre de permutations est de cardinal , beaucoup plus vaste que le nombre des états possibles.

Décomposition canonique du Cube

[modifier | modifier le code]

On peut caractériser un état du Cube par ces 12 arêtes et leurs orientations et ces 8 sommets et leurs orientations. On montre que tout état du Cube se décompose de façon unique en un quadruplet (permutation des arêtes, orientation des arêtes, permutation des sommets, orientation des sommets) :

avec de plus les contraintes suivantes :

  • flip total ,
  • twist total .
  • signatures ,


Les permutations sont représentées par les vecteurs des images : , et de même .

La définition des orientations des vecteurs u, v dépend d'un choix de marquage sur les facettes du Cube, par ex le marquage ci-contre :

Marquage standard
Marquage standard

Quel que soit ce choix, on définit la loi de composition de deux états par :

avec

p(u) = permutation des composantes de u

r(v) = permutation des composantes de v

On en déduit le cardinal du groupe .

Pour les démonstrations mathématiques détaillées, on se reportera à la référence[2], et au livre complet de théorie des groupes[3], de W.D. Joyner ici [1].

Coordonnées d'un état du cube

[modifier | modifier le code]

Pour effectuer des calculs rapides sur ces états, Kociemba[1] a introduit une représentation par coordonnées entières, définies ainsi. On associe à une permutation l'entier , son rang dans l'ordre lexicographique de classement de toutes les permutations. Il faut construire les fonctions calculant le rang, et leurs inverses calculant la permutation associée à un entier donné.

Compte tenu du total nul, le flip est représenté par l'entier , et le twist est représenté par l'entier (bases 2 et 3). Donc le vecteur de coordonnées du mouvement est . Les tailles maximales de ces entiers sont les constantes

Rubik's cube : algorithmes optimaux, sous-groupes

[modifier | modifier le code]

La recherche d'algorithmes de reconstruction optimaux (minimum de mouvements) a été entamée par le mathématicien anglais Thistlethwaite en 1981. Il utilise une démarche de décomposition du groupe en quatre sous-groupes , en se limitant successivement à des carrés (demi-tours) sur les paires de faces opposées .

Par exploration successive des classes à droite de ces sous-groupes , il construit des tables de calcul permettant la résolution complète par une manœuvre de longueur maximale 52f (face-rotation, A² compte 1). Il bornait ainsi le diamètre du groupe de Rubik, c'était le début de la course pour déterminer ce diamètre et obtenir l' Algorithme de Dieu[4] permettant, pour tout état du cube, de calculer le mouvement minimal de reconstruction. La description de cet algorithme est donnée ici[5].

L'algorithme à deux phases de Kociemba

[modifier | modifier le code]

Cet algorithme[1] a été élaboré en 1992. Il utilise la sous-suite de Thistlethwaite ,avec le sous-groupe .

Kociemba utilise la caractérisation du groupe intermédiaire  : il n'y a ni flip ni twist, et les CA de la tranche du milieu y restent, on la notera . Donc

La phase 1 consiste à ramener un état quelconque , par un mouvement , à un état . On a , on travaille donc dans l'ensemble des classes à droite (right cosets en anglais) modulo  : ensemble noté .

Une classe est déterminée par un triplet et les coordonnées associées avec

  • Tranche UD : , images de . Il y en a 412, la coordonnée est le rang dans la liste
  • Flip , coordonnée ,
  • Twist , coordonnée .

La taille de est donc .

La phase 2 résout le groupe . Un état est représenté par un triplet et les coordonnées associées avec

  • Permutation CS : , coordonnée
  • Permutation CA de  : , coordonnée ,
  • Permutation CA hors  : , coordonnée .

avec la contrainte de Signature totale=1. La taille de G2 est donc .

L'algorithme Cube Explorer[6] réalise ces deux phases, soit de façon rapide sous-optimale, soit de façon exhaustive optimale et plus lente. Il retourne, pour tout état du cube, une manœuvre de résolution en général de longueur inférieure à 20f. La version initiale de 1992 était sous-optimale et donnait en général des manœuvres de taille inférieure à 23f (mais pas de borne effective prouvée).

L'algorithme optimal (à deux phases) de Reid

[modifier | modifier le code]

La grande étape suivante, vers l'algorithme de Dieu, a été franchie par Michael Reid[7] en 1997. Il implémente l'algorithme à deux phases de Kociemba, en utilisant une réduction de l'espace de recherche par utilisation de classes d'équivalence (des états ou classes à droite) par les 16 symétries du cube respectant l'axe H-B.

Reid optimal, phase 1

[modifier | modifier le code]

Pour ce faire, il utilise dans la phase 1, une fusion des deux coordonnées , en une coordonnée unique , représentant les classes de symétrie des couples (permHB,flip).

Un élément de est donc représenté par les coordonnées de symétrie (classe FLIPUD, twist)=. La taille de l'espace à explorer est donc réduite à

avec NUDSLICE=64430 (*---Nombres de classes de symétrie de FLIP-UDslice--*).

Reid optimal, phase 2

[modifier | modifier le code]

Dans cette phase d'exploration complète du groupe G2, on calcule les classes d'équivalence de symétries et inversions des permutations de CS. Il reste 1672 classes. Les classes de symétrie de G2 sont représentées par un triplet de coordonnées avec

  • Classe de permutation des CS :
  • Permutation des CA hors
  • Permutation signée des CA de

La taille de l'espace des classes à explorer est donc :

Diamètre du cube et algorithme de Dieu

[modifier | modifier le code]

Puisque le groupe G est fini, il existe pour tout état g une manœuvre de taille minimale (nombre de mouvements élémentaires) qui le ramène à l'état résolu . Cette taille minimale est appelée la distance . Le diamètre du groupe G est .

Le diamètre est inférieur ou égal à 29f

[modifier | modifier le code]

Par exploration exhaustive des deux espaces réduits de l'algorithme optimal défini ci-dessus, Mike Reid a établi en 1995[8] que toutes les classes sont résolues par un mouvement de taille maximale 29f.

Le superflip est à distance 20f !

[modifier | modifier le code]

En recherchant de façon exhaustive des solutions dans l'algorithme optimal à deux phases, Reid démontre le premier, le [9], que le superflip (l' état où tous les sommets sont bien placés et bien orientés, tous les arêtes sont bien placés mais flipés) est à distance minimale 20f du l'état résolu. Il prouve ainsi que le diamètre du groupe G est supérieur ou égal à 20f. Il n'y a pas de mouvement plus court que celui donné au début de l'article, pour réaliser le superflip.

Le diamètre est 20f

[modifier | modifier le code]

La recherche de l'algorithme de Dieu et du diamètre effectif du groupe G s'est poursuivie de façon continue après 1995, alliant l'augmentation de puissance et taille mémoire des ordinateurs, l'amélioration de l'analyse mathématique du groupe et des algorithmes de recherche. Elle s'est conclue en , par la démonstration du résultat fondamental[10] :

Le diamètre du groupe de Rubik est 20f

Ce résultat a été obtenu par un travail conjoint de Tomas Rokicki, Herbert Kociemba, Morley Davidson et John Dethridge. Il a nécessité un temps de calcul de 35 années-CPU, réparti sur un vaste réseau de machines. Il ne donne pas cependant l'algorithme de Dieu, car le programme a cherché pour tous les états (répartis en 2 217 093 120 ensembles de 19 508 428 800 positions chacun) une solution de taille inférieure ou égale à 20f, et non une solution optimale.

Ainsi, le meilleur calcul des mouvements de taille minimale pour résoudre une position est donné par l'algorithme Cube Explorer[6] , ou l'algorithme de Reid[11] qui en est une variante antérieure. Ils sont sous-optimaux dans G, car ils utilisent une optimisation séparée en deux phases liées au sous-groupe G2 (mais aussi à ses variantes obtenues par les tranches GD et AP).

Bibliographie

[modifier | modifier le code]

Notes et références

[modifier | modifier le code]
  1. a b et c « Kociemba's Homepage », sur kociemba.org (consulté le )
  2. « Théorie des groupes - Rubik's cube », sur trucsmaths.free.fr (consulté le )
  3. (en) David Joyner, Adventures in Group Theory : Rubik's Cube, Merlin's Machine, and Other Mathematical Toys, Johns Hopkins University Press, , 262 p. (ISBN 978-0-8018-6947-1)
  4. rubikscube, « L'algorithme de dieu - Les Rubiks cube », sur Les Rubiks cube (consulté le )
  5. « Thistlethwaite's 52-move algorithm », sur www.jaapsch.net (consulté le )
  6. a et b « Cube Explorer Download », sur kociemba.org (consulté le )
  7. « Michael Reid's Rubik's cube page », sur www.cflmath.com (consulté le )
  8. « Cube Lovers: new upper bounds », sur www.math.rwth-aachen.de (consulté le )
  9. « Cube Lovers: superflip requires 20 face turns », sur www.math.rwth-aachen.de (consulté le )
  10. « God's Number is 20 », sur www.cube20.org (consulté le )
  11. « Optimal Rubik's cube solver », sur www.cflmath.com (consulté le )

Lien externe

[modifier | modifier le code]
  • « Fan2Cube », sur fan2cube.fr (consulté le )