Résoudre un Rubik's Cube en marchant dans un graphe

Le groupe du cube

Les rotations engendrent G₀ = ⟨U, R, F, D, L, B⟩, sous-groupe de 𝔖₄₈ (permutations des 48 facettes mobiles). Un état est un quadruplet (σ_c, o_c, σ_e, o_e) ∈ 𝔖₈ × ℤ₃⁸ × 𝔖₁₂ × ℤ₂¹². Le groupe des assemblages (𝔖₈ ⋉ ℤ₃⁸) × (𝔖₁₂ ⋉ ℤ₂¹²) contient G₀ comme sous-groupe d'indice 12, découpé par trois invariants : Σo_c ≡ 0 (mod 3), Σo_e ≡ 0 (mod 2), sgn σ_c = sgn σ_e^[9].

|G₀| = 8!·3⁷·12!·2¹¹ / 2 = 2²⁷·3¹⁴·5³·7²·11. Un remontage uniforme tombe dans G₀ avec probabilité 1/12 ; ces invariants jouent le rôle de quantités conservées. C'est une image : il s'agit d'homomorphismes vers un groupe abélien (somme des orientations, signature), pas d'un théorème de Noether, qui relie une symétrie à une quantité conservée.

Graphe de Cayley

Γ = Cay(G₀, S), |S| = 18, S = S⁻¹ : graphe non orienté, 18-régulier, sommet-transitif. Son diamètre vaut 20^[2] ; la plupart des positions sont à distance 18.

Borne inférieure par comptage : en interdisant deux coups sur la même face et en ordonnant les faces opposées (qui commutent), le nombre de séquences canoniques de longueur k croît comme ≈ 18·13,35^k−1. Comme Σ_k≤17 reste inférieur à |G₀|, certaines positions exigent au moins 18 coups. Le « superflip » en exige exactement 20 (Reid, 1995)^[12].

Sous-groupe et graphe de Schreier

G₁ = ⟨U, D, R2, F2, L2, B2⟩ est le stabilisateur des orientations et de la tranche E^[1]. Indice [G₀ : G₁] = 3⁷·2¹¹·C(12,4) = 2 217 093 120 ; un état uniforme est déjà dans G₁ avec probabilité ≈ 4,5·10⁻¹⁰.

Phase 1 : plus court chemin dans le graphe de Schreier Sch(G₀, G₁, S), dont les sommets sont les classes G₁g (diamètre 12). Phase 2 : plus court chemin dans Cay(G₁, S₂), |S₂| = 10, |G₁| = 8!·8!·4!/2 = 19 508 428 800 (diamètre 18). Si chaque phase est résolue de façon optimale, on obtient donc au plus 12 + 18 = 30 coups ; le solveur de cette page borne son temps de recherche (500 ms), donc la phase 2 peut ne pas l'être et cette borne n'est alors qu'indicative. Thistlethwaite (1981) utilisait une chaîne de quatre sous-groupes, pour au plus 52 coups^[10].

Heuristique admissible et IDA*

Une projection π : Γ → Γ′ (ici sur des coordonnées : orientation des coins 3⁷, des arêtes 2¹¹, tranche C(12,4)…) est un morphisme de graphes, donc 1-lipschitzienne : d_Γ′(πx, πe) ≤ d_Γ(x, e). Un BFS exhaustif sur Γ′ (~10⁶ sommets, coût O(|V|·|S|)) donne ces distances exactes. Le maximum de deux heuristiques admissibles reste admissible, et h est cohérente : |h(x) − h(xs)| ≤ 1.

IDA*^[4] : DFS itératif avec la borne f = g + h ≤ L, mémoire O(L), optimal dans chaque phase. Le coût dépend de la distribution de h (histogrammes ci-dessus) : nombre de nœuds ≈ Σ_d N(d)·P(h ≤ L − d)^[6]. Korf a trouvé les premières solutions optimales de positions aléatoires ainsi, avec des tables de motifs plus grandes^[5].

Mélange fini et marche aléatoire

La recherche est une fonction de l'état x seul : l'historique n'intervient pas (propriété de Markov). Ce qui dépend de la longueur k, c'est la loi de x : un mélange est une marche aléatoire X_k = s₁⋯s_k sur Cay(G₀, S), avec d(X_k) ≤ k. Pour k < 20, les positions lointaines sont inaccessibles.

En métrique demi-tour, le graphe contient des triangles (R·R·R2 = e), donc n'est pas biparti : la chaîne est irréductible et apériodique et converge vers l'uniforme sur G₀^[8]. En métrique quart de tour, chaque quart de tour est une permutation impaire des 48 facettes : le graphe est biparti, un mélange de k quarts de tour n'atteint que la moitié de G₀ (parité de k) et la loi ne converge jamais vers l'uniforme. D'où les mélanges « à état aléatoire » de la WCA : tirer (σ_c, o_c, σ_e, o_e) uniformément sous les trois invariants, puis résoudre l'inverse.

Détours et contre-exemples

Forcer une arête s depuis x : par l'inégalité triangulaire, d(xs) ∈ {d(x) − 1, d(x), d(x) + 1}. Pour des chemins optimaux, l'écart de longueur totale vérifie donc Δ ∈ {0, 1, 2} (Δ = 1 possible car Γ n'est pas biparti). Tout Δ < 0 observé est un contre-exemple à l'optimalité du chemin initial ; tout Δ > 2 montre que le nouveau chemin n'est pas optimal. Kociemba borne le temps de calcul, pas la longueur.

Un coup hors de S₂ appliqué à x ∈ G₁ donne xs ∉ G₁ (car G₁ est un sous-groupe) : l'état retourne dans le graphe de Schreier et une nouvelle phase 1 est nécessaire. Autre contre-exemple classique : la meilleure phase 1 ne mène pas forcément à la meilleure solution totale, d'où l'énumération de plusieurs chemins de phase 1.

Même structure, autres graphes

Taquin n×n : sommets = configurations, arête = glissement ; (n²)!/2 états atteignables (9!/2 = 181 440 pour le 3×3, 16!/2 ≈ 1,05·10¹³ pour le 4×4), diamètres 31 et 80^[18]. Invariant : parité de la permutation combinée à la ligne de la case vide, d'où exactement deux orbites^[15]. L'heuristique de Manhattan est une somme de distances dans des graphes projetés (une plaque seule sur la grille), admissible car un coup déplace une seule plaque d'une case. IDA* a été introduit sur ce problème^[4], et les bases de motifs^[16] sont l'analogue exact de nos tables BFS sur projections.

GPS : graphe pondéré (carrefours, tronçons, temps de parcours) ; A*^[14] avec h = distance euclidienne / vitesse maximale, admissible par l'inégalité triangulaire. Hiérarchies de contraction^[17] : les sommets sont ordonnés par importance et la recherche bidirectionnelle ne monte que vers des sommets plus importants. C'est l'analogue de la chaîne G₀ ⊃ G₁ ⊃ {e} : on ramène d'abord le problème dans un sous-graphe plus petit et plus structuré.

Liens avec d'autres sciences

Physique : groupes de symétrie (cristallographie, SU(3) des quarks), invariants et lois de conservation. Chimie : groupes ponctuels moléculaires. Probabilités : marches aléatoires sur les groupes et temps de mélange^[8]. IA : A*/IDA*, heuristique apprise par réseau de neurones et apprentissage par renforcement (DeepCubeA)^[7], convolution sur la structure locale du graphe^[3]. Informatique : BFS, programmation dynamique, calcul distribué (la preuve du nombre 20 a demandé ~35 années CPU)^[2].