L'algorithme minimal

07 Avr 2020

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 le moindre formule n'est pas fait pour le speedcubing, en speedcubing pour allez plus vite on mémorise le maximum de formules possible ! mais ici la question n'est pas d'économiser le temps mais plutôt d'espace, la mémoire ... par ex on stocke ces formules dans la mémoire d'un ROBOT et c'est lui qui restaure le Cube .

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

On dit que le Cube est résolu par F

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

à chaqu'étape de résolution (1),(2),... on n'utilise que des formules dans F et leurs conjugaisons.

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.
L'ensemble F contient donc 4 formules

Alg0(5)
1. (HG)<->(HP) = GH'P H'G'H' GHP' H²G'H' (minimale)
2. (HG)°(HP)° = PH'P'D'A'G'HP' HPG ADH' (minimale)
3. (HGP)->(HAG)->(HPD) = GAD'A'G'ADA' (minimale)
4. (HGP)- (HAG)+ = AHG AG'PGA' G'H'A'HP'H' (minimale)

En (1) Comme c'est un 2-cycle d'arêtes on peut placer toutes les arêtes.
La loi des flips dit on pivote toujours 2 arêtes donc En (2) on peut pivoter toutes les arêtes
à 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
La loi des twists dit on pivote toujours 2 sommets opposés, ou 3 sommets dans le même sens, donc En (4) on peut pivoter tous les sommets

On a donc un algorithme à 4 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 !!! et il est difficile de se souvenir .

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(3)
1. (HA)↔(HG) = K
2. (HAG)↔(HPD) = K
3. (HG)°(HP)° = PH'P'D'A'G'HP' HPG ADH' (minimale)
4. (HGP)- (HAG)+ = AHG AG'PGA' G'H'A'HP'H' (minimale)

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 ? la 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 :

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

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

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 [DH]

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 son état est pair, alors on peut restaurer le Cube à partir de n'importe quel état (en faisant une rotation 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 [DH]

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

[DH]

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

Nous allons construire un algorithme autour du commutateur [DH]. c'est-à-dire chaque ligne de l'algorithme doit apparaitre le crochet [DH].
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!!!

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

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


Pour orienter les arêtes il suffit de bien observer U=A[DH]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[DH]A'.H = θ .
Soient a,b,c trois arêtes, et "===>" signifie "appliquer θ"
Alors θ permute 2 arêtes : a,b, c ===> b°,a, c°
et θ² pivote 2 arêtes , en effet :
a,b, c ===> b°,a, c° ===> a°,b° , c°°=c
On a bien pivoté deux arrêtes a,b
On va prendre θ = A[DH]A'.H pour placer les arêtes et θ² pour pivoter les arêtes.

θ = A[DH]A'.H (HG)°(HP)° = (A[DH]A'.H)²

NOTE: La formule θ permute 2 arêtes et 2 sommets θ = (HG,HP)(HGP,HDA)

Voyons maintenant pour les sommets

[DH] modifie une seule pièce de la face G, il échange le sommet (HGP) de la face G, avec (HPD) un autre sommet du Cube, on peut facilement fabriquer un 3-cycle-sommets comme ceci:
[[DH]G] = [DH] .G'[HD]G = (HGP)->(HAG)->(HPD)
Q = [DH] .G'[HD]G

Pour orienter les sommets , obsevons [DH]²:

[DH]²

[DH]² modifie une seule pièce de la face G, il pivote le sommet (HGP) de la face G, il suffit de placer le sommet (HAG) en (HGP) et appliquer l'inverse de ([DH]²)'=[HD]² pour pivoter 2 sommets :
[[DH]²G] = [DH]² .G'[HD]²G = (HGP)°(HAG)°
T = [DH]² .G'[HD]²G

On a donc F = {θ, Q, T}
Et l'algorithme Alg3(3) associé:

1. (HG)↔(HP) = θ
2. (HG)°(HP)° = θ²
3. (HGP)->(HAG)->(HPD) = Q
4. (HGP)-(HAG)+ = T

(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 [DH]

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

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


Remarque : A partir de U, θ, Q, T 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: (HP)->(AD) = [DH]
    * Haut: (HP)->(HA)->(HD) = A[DH]A'
  2. Pivoter les arêtes: (HG)°(HP)° = (A[DH]A'.H)²
  3. Placer les sommets: (HGP)->(HAG)->(HPD) = [DH] .G'[HD]G
  4. Pivoter les sommets: (HGP)-(HAG)+ = [DH]² .G'[HD]²G

Quatre équations de la résolution


(HG)↔(HP) = θ
(HG)°(HP)° = θ²
(HGP)->(HAG)->(HPD) = Q
(HGP)-(HAG)+ = T

On dira aussi les 4 équations de la restauration.
Voilà, on remonte le Cube avec un algorithme construit autour du commutateur [DH], chaque ligne on voit apparaitre [DH]:
¤ 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[DH]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 perturbe 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 (HGP)->(HDA) (avec la conjugaison) en veillant de ne pas toucher les arêtes (HG) et (HP) c'est-à-dire ne pas utiliser les rotations H, G et P, 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[DH]A'.H}
Et l'algorithme Alg4(1) associé:
  • (HG)<->(HP) = θ = A[DH]A'.H
  • (HGP)<->(HDA) = θ = A[DH]A'.H
  • (HG)+(HP)+ = θ² = (A[DH]A'.H)2 (ou θ6)
  • (HGP)+(HAG)+(HDA)+ = θ4 = (A[DH]A'.H)4

(HG)<->(HP) = A[DH]A'.H (HGP)<->(HDA) = A[DH]A'.H

(HG)+(HP)+ = (A[DH]A'.H)2 (HGP)+(HAG)+(HDA)+ = (A[DH]A'.H)4


NOTE: à l'étape (2) , voici quelques formules pour vous aider à placer les sommets Haut

un 3-cycle: (HDA)->(HPD)->(HGP) = [θD'] Dans ce cas appliquer D'θD .θ pour avoir un 3-cycle

Dans ce cas appliquer θ .D'θD pour avoir un 3-cycle

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

Cet algorithme en pratique n'est pas vraiment utilisable mais en théorie il peut être très utile, par ex on peut programmer un Robot pour résoudre le Cube, à part l'algorithme, il faut stocker les formules en mémoire, donc si la mémoire coûte chère on peut faire des économies en utilisant l'agorithme minimal avec une seule formule à stocker.

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

Donc l'algorithme minimal est par définition :
  • Placer les arêtes : µ
  • Placer les sommets : µ
  • Pivoter les arêtes : µ²
  • Pivoter les sommets : µ4
où µ est une formule , la formule µ dans l'algorithme minimal est nommée formule première.

Finalement on a 4 équations pour restaurer le Cube , ces équations n'utilise qu'une seule formule θ
  • (HG)↔(HP) = θ
  • (HGP)↔(HDA) = θ
  • (HG)°(HP)° = θ²
  • (HGP)+(HAG)+(HDA)+ = θ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: 22/04/2021







Facile

Moyen

Difficile

Les Crazy

Les Bandages

Les Stars

Divers

Le MathCubing

Quiz (Master Cube)