L'algorithme minimal

7 Avr

La question ... Il y a bien longtemps que je me pose la question suivante:
"Quel est le nombre minimum de formules doit-on mémoriser pour pouvoir restaurer le Cube ?" .

Il est clair que l'algorithme utilisant ces formules n'est pas fait pour le speedcubing, mais la question est intéressante du point de vu théorique, par ex on stocke ces formules dans la mémoire d'un ROBOT et c'est lui qui se débrouille pour restaurer le Cube.

Précisons un peu :
Soit F un ensemble de formules, à chaqu 'étape de la résolution :
1. On peut tenir le Cube comme on veut
2. On peut utiliser : Q, Q' , Qn ,Q'n , la conjugaison XQX' , où Q∈F et X=une formule

BUT : Trouver F ayant le moindre formules possibles.


Le groupe étendu G+ du Rubik's Cube est
G+ = (S12 x Z212) x (S8 x Z38)

ceci montre que G+ comporte 4 composants (4 morceaux) divisant en deux clans: le clan des arêtes (S12 x Z212) et le clan des sommets (S8 x Z38) , chaque clan comporte 2 morceaux: permutations présenté par S, orientations présenté par Z.

Ceci suggère qu'on a 4 étapes de résolution :

1. Placer les arêts
2. Orienter les arêts
3. Placer les sommets
4. Orienter les sommets

Si les arêtes sont dans l'état pair (sig(u)=1), un simple 3-cycle-arêtes permet (avec la technique de conjugaison) de placer toutes les arêtes. En effet un état-arête s pair signifie s∈A12 et comme le proupe alterné A12 est engendré par les 3-cycles, donc un 3-cycle (avec la conjugaison) permet de placer toutes les arêtes.

Si les arêtes sont dans l'état impair (sig(u)=-1) , la rotation H rend les arêtes en état pair.

Les 4 formules propres


L'idée c'est d' avoir 4 formules indépendantes (propres) pour les 4 étapes de la résolutions. Avec le programme Cube Explorer (Cube.exe) on trouve les 4 formules suivantes, qui permettent de restaurer le Cube quand les arêtes sont en état pair . Si les arêtes sont en état impair (sig(u)=-1) on fait un H pour passer à l'état pair.
L'ensemble F contient donc 5 formules

Alg0
0. Si (sig(u) = -1) alors H
1. (HA)->(HP)->(HD) = D² H P' A D² P A' H D²
2. (HA)°(HG)° = A D P G H G' H P' D' A' G' H' G H'
3. (HAG)->(HPD)->(HGP) = D H P' B' P H P' B P H² D'
4. (HAG)-(HGP)+ = G' H D' H' P' D' P G P' D P H D H'

Quand on arrive à l'étape (1), les arêtes sont en état pair, donc on peut placer toutes les arêtes avec le 3-cycle
F1 = D² H P' A D² P A' H D²
à l'étape (3) , toutes les arêtes sont bien placées, les sommets sont alors en état pair (loi de parité) on peut donc placer tous les sommets avec le 3-cycle
F2 = D H P' B' P H P' B P H² D'

On a donc un algorithme à 5 formules

Ces formules sont propres, elles permettent de restaurer le Cube dans l'ordre comme on veut:
arêtes puis sommets (ou l'inverse)
Pour les arêtes: placer puis pivoter (ou l'inverse)
Pour les sommets: placer puis pivoter (ou l'inverse)

Ces formules sont minimales mais n'ont aucune structure !! on ne comprend rien ce que fait la formule !!!

Première réduction
On peut réduire F, en utilisant K

K = DAD'P'D'PD'A'H'DHD'H'D² = (HA,HG)(HAG,HPD)

On place les arêtes par K, puis on utilise ce même K pour placer les sommets, ce qui est possible parce qu'une fois les arêtes sont bien placées , on aura un nombre pair de couples de sommets à placer (loi de parité) donc on ne dérange pas les arêtes qui sont déjà bien placées.

Alg1
1. (HA)↔(HG) = K
2. (HAG)↔(HPD) = K
3. (HA)°(HG)° = A D P G H G' H P' D' A' G' H' G H'
4. (HAG)-(HGP)+ = G' H D' H' P' D' P G P' D P H D H'

Algorithme à 3 formules .

Deuxième réduction
On voit que les deux dernières lignes pivotent les pièces, on se demande si on peut les remplacer par une seule formule ? a réponse est affirmative, en effet on pivote 2 fois une arête on revient à son état initial, par contre il faut pivoter 3 fois un sommet pour revenir à son état initial, donc si on trouve une formule qui pivote 2 arêtes et 2 sommets on aura gagné, en voici une :

Q = GP'D'PH'AHP'A'DPD'HG'H'D
= (HA)°(HG)°(HAG)-(HPD)+

Alg2
1. (HG)↔(HP) = K
2. (HAG)↔(HDA) = K
3. (HA)°(HG)° = Q
4. (HAG)+(HPD)- = Q²

Algorithme à 2 formules !! C'est vraiment pas mal mais on se demande si on peut faire mieux ? et puis si on peut rendre les formules plus compréhensives ? plus structurées ?? la réponse est "oui" .

Le crochet [HD]

Le problème de ces algorithmes c'est qu'ils utilisent des formules qui n'ont aucune structure, on ne voit rien ce que fait la formule.

On voudrait avoir des formules qui soient plus structurées pour comprendre ce qui se passe, ce que fait la formule...
Si on sait restaurer le Cube quand il est en localement pair, alors on peut restaurer le Cube à partir de n'importe quel état (en ajoutant H).
Les états localement pairs sont gérés par les 3-cycles et comme les commutateurs produisent des 3-cycles c'est pourquoi on va examiner le comutateur [HD]

Observons bien ce que fait ce commutateur. [HD] agit sur le Cube comme une sorte de 'Z' et nous le notons ζ = [HD]

[HD]
[HD] agit sur le Cube:
Arêtes: (HD)->(AD)->(HP) = (HD,AD,HP) notation moins lourde !
Sommets: (HDA)<->(BAD).(HPD)<->(HGP) = (HDA,BAD)(HPD,HGP)
[HD] = (HD)->(AD)->(HP) . (HDA)<->(BAD).(HPD)<->(HGP)
[HD] = (HD,AD,HP)(HDA,BAD)(HPD,HGP)

Nous allons construire un algorithme autour du commutateur [HD]. c'est-à-dire chaque ligne de l'algorithme doit apparaitre le crochet [HD].
L'idée c'est d'avoir 4 formules qui correspondent aux 4 étapes de la résolution :
Et voilà, si on observe bien on a tout ce qui faut!!!

A partir de [HD] si on veut que tout se passe sur la face Haut il suffit de faire A[HD]A' c'est plus clair et plus propre. A[HD]A' déplace donc 3 arêtes de face Haut

(HA)->(HP)->(HD) = A[HD]A'


Pour orienter les arêtes il suffit de bien observer U=A[HD]A', U laisse une seule bonne arête, on ramène la 2ème bonne arête par H', car on veut seulement avoir 2 mauvaises arêtes c'est-à-dire on prend A[HD]A'.H' = θ .
Cette formule permute 2 arêtes a, b de façon suivante: θ(a,b) = (b°,a) ; a,b permutés et b pivoté donc il suffit de faire θ² et on aura ce qu'il faut :
θ(a,b) = (b°,a) => θ²(a,b) = θ(b°,a) = (a°,b°) a et b sont donc pivotés
On va prendre θ = (A[HD]A'.H') pour placer les arêtes et θ² pivote bien 2 arêtes.

θ = A[HD]A'.H' (HA)°(HG)° = (A[HD]A'.H')²

NOTE: La formule θ permute 2 arêtes et 2 sommets θ = (HG,HA)(HAG,HPD)

Voyons maintenant pour les sommets

[HD] permute deux pair de sommets: (HAD,BAD)(HPD,HPG) on peut donc fabriquer un 3-cycle comme ceci:
(HAG)->(HPD)->(HGP) = [HD].G'[DH]G
V = [HD].G'[DH]G

Pour orienter les sommets , obsevons [HD]²:

[HD]²

[HD]² pivote (HPG) mais perturbe le Cube, il suffit de placer le sommet (HAG) en (HGP) et appliquer l'inverse de ([HD]²)'=[DH]² donc W=[HD]².G'[DH]²G

On a donc F = {θ, V, W}
Et l'algorithme Alg3 associé:

1. (HA)↔(HG) = θ
2. (HA)°(HG)° = θ²
3. (HAG)->(HPD)->(HGP) = V
4. (HAG)-(HGP)+ = W

(3) c'est possible car les arêtes sont bien placeés donc les états des sommets est pair, donc on peut tous les placer par un 3-cycle.
Les formules sont beaucoups plus claires et structurées donc facile à mémoriser et on voit ce que fait une formule et elles sont construites autour de [HD]

(HA)->(HP)->(HD) = A[HD]A' (HA)°(HG)° = (A[HD]A'.H')²

(HAG)->(HPD)->(HGP) = [HD] .G'[DH]G (HAG)-(HGP)+ = [HD]² .G'[DH]²G


Remarque : A partir de U, θ, V, W on peut adapter pour avoir un algorithme de résolution tout à fait raisonnable, c'est ce que j'ai fait:
  1. Placer les arêtes
    * Bas: (HA)->(BA) = A²
    * Equateur: (HD)->(AD) = [HD]
    * Haut: (HA)->(HP)->(HD) = A[HD]A'
  2. Pivoter les arêtes: (HA)°(HG)° = (A[HD]A'.H')²
  3. Placer les sommets: (HAG)->(HPD)->(HGP) = [HD].G'[DH]G
  4. Pivoter les sommets: (HAG)-(HGP)+ = [HD]² .G'[DH]²G

Quatre équations de la résolution


(HA)↔(HG) = θ
(HA)°(HG)° = θ²
(HAG)->(HPD)->(HGP) = V
(HAG)-(HGP)+ = W

On dira aussi les 4 équations de la restauration.
Voilà, on remonte le Cube avec un algorithme construit autour du commutateur [HD], chaque ligne on voit apparaitre [HD]:
¤ Un principe simple à comprendre: On place les arêtes puis les oriente. On place des sommets puis les oriente.
¤ 3 formules
¤ Les formules sont structurées donc facile à comprendre


L'algorithme minimal

On a trouvé un algorithme structuré à 3 formules, récemment j'ai apperçu qu'on peut encore aller plus loin...
La formule θ = A[HD]A'H' est vraiment intéressante, on effet :

  1. θ permute 2 arêtes et 2 sommets
  2. θ2 (ou θ6) pivote 2 arêtes
  3. θ4 pivote 3 sommets

θ permute 2 arêtes et 2 sommets, on se demande si on peut l'utiliser pour placer les pièces ?
à priori non, en effet θ permute 2 arêtes et 2 sommets donc soit on l'utilise pour placer les arêtes, soit on l'utilise pour placer les sommets. Une fois utilisé θ pour placer les arêtes par ex, si on utilise θ une deuxième fois pour placer les sommets on pertubera les arêtes !!!

Mais le Rubik's Cube possède une loi qui va nous sauver la vie! la loi des phases. La loi des phases dit "les sommets et les arêtes sont en phases" c'est-à-dire sig(u)=sig(v) . Autrement dit quand toutes les arêtes sont bien placées, on aura un nombre pair de couples de sommets à placer donc on ne berturbe pas les arêtes.

* On commence par placer toutes les arêtes par θ
* Après avoir placer toutes les arêtes, on place alors les sommets grâce à θ aussi ! on place (HAG)->(HPD) (avec la conjugaison) en veillant de ne pas toucher les arêtes (HA) et (HG) c'est-à-dire ne pas utiliser les rotations H, G et A, c'est possible parce que les sommets sont maintenant en état pair (sig(u)=1=sig(v)).
* On pivote les arêtes par θ2 (ou θ6),
* on pivote les sommets par θ4

Alléluia !! une seule formule pour restaurer le Cube !!! ...

F = {θ = A[HD]A'.H'}
Et l'algorithme Alg4 associé:
  • (HG)<->(HA) = θ = A[HD]A'.H'
  • (HAG)<->(HPD) = θ = A[HD]A'.H'
  • (HA)°(HG)° = θ² = (A[HD]A'.H')2 (ou θ6)
  • (HAG)-(HDA)-(HPD)- = θ4 = (A[HD]A'.H')4

(HG)<->(HA) = A[HD]A'.H' (HAG)<->(HPD) = A[HD]A'.H'
(HA)°(HG)° = (A[HD]A'.H')2 (HAG)-(HDA)-(HPD)- = (A[HD]A'.H')4

Et voilà, il est vraiment extraordinaire qu'on puisse restaurer le Cube avec seulement une formule construite autour d'un seul commutateur [HD] !! C'est incroyable n'est ce pas ?

Cet algorithme n'est peut-être pas fait pour le speedcubing mais il a le mérite d'être cité pour la beauté des choses ...

REMARQUE : θ4 et θ6 sont propres donc indépendants (l'ordre d'exécution n'intervient pas)

Donc l'algorithme minimal est:
  • Permuter 2 arêtes
  • Permuter 2 sommets
  • Pivoter 2 arêtes
  • Pivoter les sommets

Finalement on a 4 équations pour restaurer le Cube , ces équations n'utilise qu'une seule formule θ
  • (HA)↔(HG) = θ
  • (HAG)↔(HPD) = θ
  • (HA)°(HG)° = θ²
  • (HAG)-(HDA)-(HPD)- = θ4

Il est vraiment frappant qu'il y a une analogie avec les 4 équations de Maxwell en électromagnétique
  • div(B) = 0
  • rot(E) = - ∂B/∂t
  • div(E) = p/ε
  • rot(B) = µj + εµ∂E/∂t
NOTE : On pourrait dire que θ et ζ , 2 constances de la structures M, et elles sont reliés par
θ = ζA H'


1 2 [3] 4 5 6

Accueil

DMJ: 15/01/2019







Facile

Moyen

Difficile

Les Crazy

Les Bandageds

Les Stars

Divers

Mathematiques des Twists

Quiz (Master Cube)