l'Algorithme de Thistlethwaite pour un Humain

[Morphocode]

Vous avez peut-être entendu parler de l'algorithme de Thistlethwaite, et si vous le cherchez sur internet mais alors c'est vraiment mal expliqué ...
Voyons un peu:
Tout se passe vers les années 1980-1981, on s'est intéressé par la question suivante:
-Quel est le nombre maximum de rotations (nécessaire) pour restaurer le Rubik's Cube à partir d'un état quelconque ?
Soit m le nombre de rotations maximum nécessaire, m est alors compris entre a=minimum et b=maximum
a ≤ m ≤ b
il y a des états qu'on ne peut pas s'en sortir avec moindre de a rotations, a est minimum, en cherchant un peu par l'ordinateur
on trouve a=26 càd il y a des états qu'on ne peut pas restaurer le Cube avec 25 rotations ! par ex l'état SuperFlip4Spot, longueur=26.
donc 26 ≤ m ≤ b
il faut prend b = maximum nessesaire car si on prend b = 65256 c'est bien mais c'est beaucoup trop ...
C'est Thistlethwaite qui apportait une valeur raisonnable de b.
Pour cela il utilisait les groupes !!!

à chaque tour H de sous groupes de M (le groupe des formules) on associe une tour de sous ensembles E de G (ensemble des états) .
Thistlethwaite proposait la tour suivante:
H0 = M = <H,B,A,P,G,D> ==> E0 = G
H1 = <H,B,A²,P²,G,D> ==> E1
H2 = <H,B,A²,P²,G²,D²> ==> E2
H3 = <H²,B²,A²,P²,G²,D²> ==> E3
H4 = {I} ==> E4 = {e} e=état résolu

Il démontrait que :
1) ∀s∈G ∃V∈M et |V| ≤ 14 telle que s•V = s1∈E1
2) ∀s1∈E1 ∃V1∈H1 et |V1| ≤ 26 telle que s1•V1 = s2∈E2
3) ∀s2∈E2 ∃V2∈H2 |V2| ≤ 30 telle que s2•V2 = s3∈E3
4) ∀s3∈E3 ∃V3∈H3 |V3| ≤ 34 telle que s3•V3 = e ,
e état résolu

donc au maximum b = 14+26+30+34 = 104 rotations
Ce que Thistlethwaite prouve :
1) On peut toujours restaurer le Cube à partir de n'importe quel état.
2) Le nombre maximum de rotations dans la résolutions serait 104.

Durant les années on diminue b et finalement en 2014 , b=26, autrement dit on restaure le Rubik's Cube au maximum 26 rotations.
On dit que le diamètre du Rubik's Cube est 26.

La méthode de Thistlethwaite donne un algorithme de résolution (à 4 étapes) car on part d'un état mélangé s et on arrive à l'état résolu e.
Le problème de cet algorithme est que les formules Vi sont trouvées par ordinateur.
Lorsqu'on change s , V change !!! s étant donné, l'ordinateur cherche V parmi 43 252 003 274 489 856 000 formules !
avec un peu d'astuce il cherche V parmi 2048 formules et une plus courte (il y a beaucoup de plus courtes formules) , tout cela est impossible pour un être humain.

Vers les années 2002, Ryan Heise a une idée de convertir l'AT (Algorithme de Thistlethwaite) en un ATH (Algorithme de Thistlethwaite Humain), mais alors il a vraiment un esprit tordu !! compliqué !!
On ne comprend pratiquement rien de ses explications !!! ce qui fait que l'exécution de son algorithme est vraiment tiré par les cheveux ...
Puis quelque année plus tard en 2008 une autre personne reproduisait l'ATH de Ryan Heise en vidéo, mais lui aussi, a un esprit tordu !!
au lieu de filmer par derrière (le caméra est derrière lui) il laisse le caméra devant lui, ce qui fait que les repérages des rotations
sont tous renversés !! parfois il tords ses mains pour montrer les rotations !!!
et ses explications sont comme Ryan Heise, compliqués incompréhensibles ....


Et pour tant les choses ne sont pas incompréhensibles et si compliquées que ça ......

[Morphocode]

Voici ma version de l'Algorithme de Thistlethwaite pour un Humain.
Quand on résout le Cube , on utilise les formules comme on veut, il n'y a pas de contraintes sur les formules.
L'algorithme de Thistlethwaite est un algorithme pour le MathsCubing càd il faut connaitre le Cube mathématiquement pour comprendre l'algorithme.

1) Il faut savoir que les arêtes et les sommets sont mal ou bien orientés.
2) Il y a des contraintes sur les formules, donc il faut trouver de nouvelles formules


Algorithme se fait en 4 étapes:

étape 1 : Orienter toutes les arêtes.
=====================================
Pas de Contraintes

Ici on fait en 2 étapes:

a) On place les arêtes-équateur (pas de blanc, ni de jaune) dans l'équateur par :
J = A[DH]A'H

b) Orienter les arêtes:
(HG)°(HP)° = J²

___________________________________________________

Le problème dans cet étape, c'est qu'il faut reconnaitre les arêtes mal orientées !! ce qui n'est pas évident lorsqu'elles ne sont
pas dans leur emplacement origine (à l'état résolu).
Il faut donc connaitre par coeur le schéma de marquages et les couleurs dominantes.

Rappel: On fixe le Cube c'est-à-dire définir le Haut, le Bas, ... voici le marquage des facettes (à connaitre par coeur)

couleur dominante :
L'ordre des couleurs : blanc > jaune > vert > klein > orange > rouge


étape 2 : Orienter toutes les sommets.
======================================
Contraintes : les formules dans < H,B,A²,P²,G,D > ; donc pas de A, A', P, P'

Pivoter les sommets
(HGP)- (HAG)+ = [DH]² G'[HD]²G


étape 3 : Glisser toutes les sommets.
======================================
Contraintes : les formules dans < H,B,A²,P²,G²,D² > ; donc pas de A, A', P, P,', G, G', D, D'

Ranger les sommets-Bas
(HDA)->(BAD) = A²H'A²HA²

Ranger des sommets-Haut
(HDA)<->(HPD) = D²H(D²H')² .B . D²H'D²HD² .B'


étape 4 : Glisser toutes les arêtes.
======================================
Contraintes : les formules dans < H²,B²,A²,P²,G²,D² > ; donc pas de A, A', P, P,', G, G', D, D', H, H', B, B'


a) Ranger les arêtes-Bas :
(HD)->(BD) = (H²A²D²A²)²

b) Ranger les arêtes-équateur :
(AD)<->(PD) = (D²H²)3

c) Ranger les arêtes-Haut:
(HG)->(HD)->(BD) = (H²A²D²A²)²

[Morphocode]

Voici un résumé :
================
1) Placer les arêtes-équateur (pas de blanc, ni de jaune) dans l'équateur, et Orienter toutes les arêtes : pas de contrainte sur les formules
2) Orienter toutes les sommets, et les formules dans < H,B,A²,P²,G,D >
3) Ranger toutes les sommets et les formules dans < H,B,A²,P²,G²,D² >
4) Ranger toutes les arêtes et les formules dans < H²,B²,A²,P²,G²,D² >

[Morphocode]

Commentaires
============
Il y a des différences entre l'AT et l'ATH

1) à l'étape 1 par ex, dans l'AT la formule V avec |V| <= 14 place les arête-équateur et oriente toutes les mauvaises arêtes en même temps ! alors que dans l'ATH la formule J² pivote seulement deux arêtes ce qui fait que pour pivoter toutes les mauvaises arêtes il faut utiliser les conjugaisons XJ²X' (X=formule) donc au final on aura une grosse grosse formule : C = J² XJ²X' YJ²Y' ...
2) Si on change s, V change, alors que dans l'ATH on utilise toujours J² (mais les conjugués changent, les X changent)
3) l'ordinateur trouve V minimal , mais C n'est pas minimal .

Pour AT : on donne s l'ordinateur nous fournit les V, V1, V2, V3 avec |V|+|V1|+|V2|+|V3| <= 104
Si on change s en t l'ordinateur nous fournit les Q , Q1, Q2, Q3 avec |Q|+|Q1|+|Q2|+|Q3| <= 104

Pour ATH : si on change s en t on utilise toujours les même formules !! (mais les conjugaisons changent)