La résolution du Rubik's Cube

[Morphocode]

Je pense que tous les Cubeurs se souviennet la 1er fois qu'ils rencontrent le Rubik's Cube. Pour moi c'était en 2007 quand je passais mes grandes vacances à Nice.
Un jour tout à fait par hasard je trouvais cet objet dans un magasin de jouer : Le Rubik's Cube.
Une fois rentré à la maison, bien installé dans un transat sous l'ombre des arbres et avec un mojito je commençais à examiner ce casse-tête.
Par curiosité quelques mouvements .... et hup ... c'est la panique !! car il m'était impossible de revenir à l'état résolu !! plus j'assayais plus le Cube était mélangé !!! et au bout de 20 minutes le Cube était complétement mélangé !!
Je passais pendant des heures des heures à le restaurer , mais quand j'ai fini une face je détruisais la face déjà restaurée !! C'était un vrai cauchemard !!! impossible de resraurer le Cube !
à l'époque il n'y avait pas encore de vidéos tuto de la résolution ... il ne me restait que des livres ... et j'ai acheté un tas de livres...
Finalement, au bout d'un mois et avec beaucoup de livres j'ai pu enfin restaurer le Cube ! Ouufff !!!

A cet époque si quelqu'un on me disait :

" ne t'en fais pas ! je peux t'apprendre à restaurer le Cube avec un principe et seulement 4 formules !!! "

je n'aurais pas cru, car dans les livres on nous donne pleine de formules de méthodes compliquées ... pour réussir .

Le principe en question se nomme le "principe de conjugaison", voyons de quoi s'agit-il.
Prenons la formule propre
K = GADPHP'HD'A'G'P'H'PH'
qui pivote précisément les arêtes (HG) et (HP) et seulement ces deux là, alors comment pivotons-nous les arêtes (HG) et (HD) par exemple ?
il suffit d'amener (HD) à (HP) et appliquer K puis remettre (HD) à sa place, autrement dit pour pivoter (HG) et (HD) on fait:
(DP) K (DP)' = (DP) K (P'D')
on a appliqué la technique de conjugaison à K (XKX' où X est une formule) , ainsi avec la conjugaison on peut pivoter toutes les arêtes avec la formule K.


Quant-à la résolution n'a besoin que 4 formules cela provient de la structure du groupe étendu du Rubik's Cube.
Le groupe étendu du Rubik's Cube, noté G+, est un objet mathématique qui décrit les propriétés du puzzle, peu importe ce que c'est il est de la forme :
G+ = S12 x Z212 x S8 x Z38
On voit bien que G+ a 4 morceaux d'où 4 formules ! on voit aussi pour restaurer le Cube on a 4 étapes (4 morceaux).

L'écriture S12 x Z212 x S8 x Z38 , c'est assez barbare mais rien de compliqué, c'est simplement des abréviations (une sorte de SMS)
- Les deux premier morceaux (S12 x Z212 ) concernent les arêtes
- Les deux dernier morceaux ( S8 x Z38 ) concernent les sommets

S12 :
S=déplacer,placer
12=12 arêtes

Z212 :
Z=pivoter,orienter
2=2 orientations pour une arête
12=12 arêtes

==============

S8 :
S=déplacer,placer
8=8 sommets

Z38 :
Z=pivoter,orienter
3=3 orientations pour un sommet
8=8 sommets



On voit donc 4 étapes de la résolution et à chaqu'étape on n'a besoin qu'une formule d'où finalement 4 formules suffissent pour s'en sortir. Voici ces 4 formules:
1. Placer des arêtes : A[DH]A'H
2. Orienter les arêtes : K
3. Placer les sommets : [DH] .G'[HD]G
4. Orienter les sommets : [DH]² .G'[HD]²G

de façons plus précise, voici notre algorithme "naturel" de résolution :

1. Placer des arêtes : (HG)<->(HP) = A[DH]A'H
2. Orienter les arêtes : (HG)+(HP)+ = K
3. Placer les sommets : (HGP)->(HAG)->(HPD) = [DH] .G'[HD]G
4. Orienter les sommets : (HGP)-(HAG)+ = [DH]² .G'[HD]²G

En résumé : 1) avec la technique de conjugaison et ces 4 formules on peut restaurer le Cube !
2) on peut remplacer K par J² donc avec 3 formules seulement on peut restaurer le Cube.

[Morphocode]

Rappel:
K = GADPHP'HD'A'G'P'H'PH'
J = A[DH]A'H

L'algorithme de résolution:
1. Placer les arêtes : (HG)<->(HP) = J
2. Orienter les arêtes : (HG)+(HP)+ = K
3. Placer les sommets : (HGP)->(HAG)->(HPD) = [DH] .G'[HD]G
4. Orienter les sommets : (HGP)-(HAG)+ = [DH]² .G'[HD]²G

=======

Si on a un esprit critique, en examinant l'algorithme un certain nombre de points doivent être éclairés ...

→ à l'étape (1) , la formule J (avec la conjugaison) permet de placer toutes les arêtes, donc aucun problème à l'étape (1)


→ à l'étape (2) , la formule K pivote deux arêtes, donc si jamais il nous reste une seule arête à pivoter , alors comment faire avec K ? ne vous en faites pas, il y a un théorème qui va nous sauver, le théorème des flips : quand on pivote les arêtes on pivote toujours deux arêtes . Donc le cas où il reste une seule arête à pivoter ne peut pas se produire !
K pivote 2 arêtes et comme on a 12 arêtes, on peut donc pivoter toutes les arêtes par K.
Quand on arrive à la fin de l'étape (2) toutes les arêtes sont bien rangées, on pourrait appeler cet algorithme : " l'algorithme des 6 Croix X "


→ à l'étape (3) , la formule Q = [DH] .G'[HD]G déplace 3 sommets, donc s'il nous reste deux sommets à permuter , alors comment s'en sortir avec Q ? ne vous en faites pas il y a un théorème qui va nous sauver, le théorème de parité : quand on permute 2 arêtes on permute aussi deux sommets et inversement . à l'étape (3) toutes les arêtes sont bien placées donc d'après le théorème aucun couple de sommets à permuter autrement dit le cas où il reste un couple de sommets à permuter ne peut pas se produire !
Q déplace 3 sommets , on peut donc placer toutes les sommets par Q.


→ à l'étape (4) , la formule T = [DH]² .G'[HD]²G pivote deux sommets (dans le sens opposé), donc s'il nous reste un seul sommet à pivoter à 120° ou 240°, alors comment faire avec T ? ne vous en faites pas il y a un théorème qui va nous sauver .
le théorème des twists :
Quand on pivote les sommets :
-Soit on pivote 2 sommets de sens opposé.
-Soit on pivote 3 sommets dans le même sens.

Donc le cas où il reste un sommet à pivoter à 120° ou 240° ne peut pas se produire !
Ainsi avec T , on peut donc pivoter tous les sommets.
Il faut noter que l'algorithme marche grâce aux trois théorèmes ci-dessus, sans ces théorèmes l'algorithme ne marchera pas.

[Morphocode]

Je pense que c'est terminé , je sais résoudre le Rubik's Cube avec seulement 4 formules , facile à retenir , mais j'ai fais une découverte étonnante :

On peut résoudre le Rubik's Cube avec une seule formule !!!

On pose T = A[DH]A'H
Voici l'algorithme (minimal) :
1. Placer les arêtes : (HG)<->(HP) = T
3. Placer les sommets : (HGP)<->(HDA) = T
2. Orienter les arêtes : (HG)+(HP)+ = T²
4. Orienter les sommets : (HGP)+(HAG)+(HDA)+ = T4

En 2007 si je savais cette formule et cet algorithme , je n' achèterais aucun livre de résolution ...

Remarque importante : On peut utiliser l'algorithme minimal astucieusement pour avoir un algorithme de résolution en un temps raisonnable (5-10 minutes), en effet:

Algorithme naturel:
1. Ranger les arêtes Bas , c'est intuitif (ou avec T )
2. Ranger les arêtes équateur , avec T

3. Placer les sommets Bas avec T , ça se fait en plusieurs étapes:
-amener un sommet Bas en (HGP) par T (ou avec la conjugaison : BD T D'B' )
-amener son emplacement en (HDA) par T (ou avec la conjugaison BD T D'B' )
-puis placer le sommet avec T
-remettre le sommet à son emplacement

4. placer les arêtes Haut avec T
5. placer les sommets Haut avec T (ou avec la conjugaison ATA' ou DTD' , sans toucher (HG) et (HP))
6. pivoter les arêtes avec T²
7. pivoter les sommets avec T4


Si vous ne voulez pas T4 (longueur=28) pour pivoter les sommets alors vous pouvez utiliser une autre formule par exemple:
W = [DH]² .G'[HD]²G = (HGP)-(HAG)+ (longueur=18)
ou
C=(D'BD ABA') H' (AB'A' D'B'D) H = (HAG)-(HDA)+ (technique du cobaye, longueur=14)
dans ce cas on doit mémoriser 2 formules au lieu d'une.



Une Remarque :
à l'étape (5) : placer des sommets Haut, j'ai remarqué qu'on tombe souvent sur un 3-cycle (a,b,c) à placer qu' un double pairs (a,b)(c,d) à placer, ça s'explique de la façon suivante:
-Quand on arrive à l'étape (5) toutes les arêtes sont bien placées, donc les déplacements des sommets se font par les permutations paires (loi de parité) or on a 4 sommets à placer donc tout se passe dans A4 or dans A4 on a:
A4 = {id,
(1,2,3), (1,3,2), (1,2,4), (1,4,2),
(1,3,4), (1,4,3), (2,3,4), (2,4,3),
(1,2)(3,4), (1,3)(2,4), (1,4)(2,3) }
On voit qu' il y a 8 3-cycle et 3 double pairs.
d'où les 3-cycle apparaissent plus souvent.