L'algorithme minimal

7 Avr

La question ... Il y a bien longtemps que je me pose la question suivante:
"Existe-t-il un algorithme "minimal" permettant de restaurer le Cube en un temps fini ? " .

Le terme minimal signifie qu'on utilise le moindre de formules possibles. Il est clair que cet algorithme n'est pas fait pour le speedcubing, mais la question est intéressante du point de vu théorique.
Précisons un peu
Soit F un ensemble de formules et Alg son algorithme associé.
A chaqu'étape de la résolution (l'exécution de l'algirithme) on peut utiliser l'inverse, la puissance, et la conjugaison
Condition:

  1. Chaque ligne on a une seule action: déplacer ou pivoter
  2. Chaque ligne n'utilise que des formules dans F
BUT : Trouver F ayant le moindre formules possibles.

L'étude théorique du Rubik's Cube, montre que:
  1. Le groupe du Rubik's Cube comporte 4 composants (4 morceaux) divisant en deux clans: le clan des arêtes et le clan des sommets .
  2. sig(u) = sig(v) u=permutation arêtes, v=permutation sommets
  3. Si on trouve une formule qui déplace 3 arêtes (un 3-cycle): u=(a,b,c), et qu'on est dans un état localement(°) pair alors, avec les conjugués de u on est capable de reconstituer tout le clan d'arêtes !!! (même chose pour le clan des sommets)
(°)NOTE : état localement paire sig(u)=sig(v)=1
état paire sig(p)=1 ; p=permutation total , p=uv

(1) Nous montre qu'on a 4 étapes de résolution
(2) Nous montre qu'il suffit d'occuper les états localement pair (sig(u) = sig(v) = 1). Pour passer de l'état localement impair (sig(u) = sig(v) = -1) en état localement pair on fait un H
(3) Quand on est en état localement pair, il suffit de trouver un 3-cycle-arête (resp. sommets) pour placer toutes les arêtes (resp. sommets),

Voyons de plus près ......



Quatre formules propres

L'idée c'est d' avoir 4 formules 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 il est en état localement pair. On passe de l'état localement impair en état localement pair par H. L'ensemble F contient donc 5 formules

Alg1
  1. Si ( sig(u) = -1) alors H
  2. Sinon (HG)->(HD)->(HP) = P²H'G'D.P²GD'H'.P² (longeur=9f)
  3. (HA)°(HD)° = AH²A² .B' [H' G' ]B. A²H' A' H' (longeur=13f)
  4. (HAD)->(HPD)->(HPG) = D² .P²DAD'. P²DA' D (longeur=9f)
  5. (HAG)°(HAD)° = HAB'A²H .G²H'G². AH'A²BA² (longeur=13f)

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 (et propres) mais n'ont aucune structure !! on ne comprend rien ce que fait la formule !!!
On a donc un algorithme de longeur 5

Le crochet [HD]

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]. L'idée c'est d'avoir 4 formules qui correspondent aux 4 étape 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 S=A[HD]A', S 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') et θ² pivote bien 2 arêtes.

θ = A[HD]A'.H' (HG)°(HA)° = (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:
(HGP)->(HAG)->(HPD) = [HD].G'[DH]G qui nous permet de placer tous les sommets c'est-à-dire
Q = [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 = {H, S, θ, Q, W}
Et l'algorithme Alg2 associé:
  • Si (sig(u) = -1) alors H
  • Sinon (HA)->(HP)->(HD) = S = A[HD]A'
  • (HG)°(HA)° = θ² = (A[HD]A'.H')²
  • (HGP)->(HAG)->(HPD) = Q = [HD].G'[DH]G
  • (HGP)°(HAG)° = W = [HD]².G'[DH]²G
L'Alg2 a le même style, même longeur que Alg1 mais c'est beaucoups plus clair car les formules sont structurées donc facile à mémoriser et on voit ce que fait une formule

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

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


Remarque : A partir de S, θ, Q, W on peut adapter pour avoir un algorithme de résolution tout à fait raisonnable, c'est ce que j'ai fait: l'algorithme "des 6+" .
  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: (HG)°(HA)° = (A[HD]A'.H')²
  3. Placer les sommets: (HGP)->(HAG)->(HPD) = [HD].G'[DH]G
  4. Pivoter les sommets: (HGP)°(HAG)° = [HD]² .G'[DH]²G

Quatre équations de la résolution

On se demande s'il est possible de débarrasser le H, pour avoir seulement 4 formules ?
Voyons... les formules de placement que nous avons utilisées sont toutes localement paires (sig(u)=sig(v)=1) pour débarrasser le H il faut trouver une formule de placement localement impaire (sig(u)=sig(v)=-1) et on trouve
K = [DH]D'A.D²H'.[D'H']D'A' = (HG,HD)(HDA,HPD)
Avec K on peut débarrasser H, en effet on peut placer toutes les arêtes par K, et une fois les arêtes sont bien placées les sommets sont en état pair donc on peut les placer par les 3-cycles

On a donc F={K, θ, Q, W}
Et l'algorithme Alg3 associé:
  • (HG)<->(HD) = K = [DH]D'A.D²H'.[D'H']D'A'
  • (HG)°(HA)° = θ² = (A[HD]A'.H')²
  • (HGP)->(HAG)->(HPD) = Q = [HD].G'[DH]G
  • (HGP)°(HAG)° = W = [HD]².G'[DH]²G

On dira aussi les 4 équations de la restauration.

Voilà, on remonte le Cube avec un algorithme construit autour d'un seul commutateur [HD]:
1. Un principe simple à comprendre: On place les arêtes puis les oriente. On place des sommets puis les oriente.
2. 4 formules
3. Les formules sont structurées donc facile à comprendre

Encore une réduction

On a trouvé un algorithme de longeur 4, 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

(A[HD]A'.H' )4

Comme θ permute 2 sommets on peut donc placer tous les sommets grâce à θ, et θ4 pivote 3 sommets ce qui permet d'orienter tous les sommets. et on connait déjà θ2 (ou θ6) qui pivote 2 arêtes, une seule formule pour ces 3 acts vraiment merveilleur ... Il nous reste maintenant une seule chose à faire: déplacer les arêtes.

Pour déplacer les arêtes on utilise ζ = [HD] qui déplace bien les arêtes, on prend donc:

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

(HAG)<->(HPD) = A[HD]A'.H' (HP)->(AD)->(HD) = [HD]²

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

Et voilà, nous avons maintenant un algorithme ayant 2 formules θ et ζ construites autour d'un seul commutateur et de plus ces formules sont reliées par:

θ = ζA H' !! C'est incroyable non ?

L'algorithme minimal

  1. θ permute 2 arêtes et 2 sommets
  2. θ2 (ou θ6) pivote 2 arêtes
  3. θ4 pivote 3 sommets
Dans Alg4 , θ tout seul peut faire 3 actions, on se demande si on peut supprimer ζ et utiliser seulement θ pour placer les pièces ?
à priori ce n'est pas possible, 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 l'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.

* 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 (HG) et (HA) c'est-à-dire ne pas utiliser les rotations 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 Alg5 associé:
  • (HG)<->(HA) = θ = A[HD]A'.H'
  • (HAG)<->(HPD) = θ = A[HD]A'.H'
  • (HG)°(HA)° = θ² = (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'
(HG)°(HA)° = (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 θ
  • (HG)↔(HA) = θ
  • (HAG)↔(HPD) = θ
  • (HG)°(HA)° = θ²
  • (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: 07/03/2017







Facile

Moyen

Difficile

Les Crazy

Les Stars

Divers

Théorie des Twists

Quiz (Master Cube)