UNE CONSTANTE DE 10⁴⁰ RAMENÉE À 30,5 POUR LES RUBIK'S CUBES GÉANTS
Le Rubik’s Cube, qui vient d’avoir 50 ans, est peut-être le casse-tête le plus connu au monde, et l’une de ses grandes questions s’énonce simplement : dans le pire des cas, combien de coups faut-il pour le résoudre ? Pour le cube classique 3×3×3, la réponse est connue exactement : 20 coups, un résultat publié en 2014 par une équipe dont faisait partie Tomas Rokicki, l’un des auteurs de ce nouvel article.
Pour les cubes plus grands, avec n rangées le long de chaque arête, la réponse exacte est hors de portée — trouver la solution la plus courte d’un cube n×n×n donné est même NP-complet, une classe de problèmes pour lesquels on ne connaît aucune méthode efficace. Mais en 2011, Erik Demaine et ses collègues ont montré comment le pire cas grandit : comme n² / lg n, où lg est le logarithme en base 2. C’est un facteur logarithmique de mieux que les méthodes standard, qui résolvent les pièces quasiment une par une.
Une preuve à la constante absurde
Il y avait un piège. Le résultat de 2011 garantissait la vitesse de croissance, pas le nombre placé devant. En déroulant cet algorithme, les auteurs trouvent une constante d’environ 1,01 × 10⁴⁰. En cause : une vérification par ordinateur qui prouvait que certains coups atteignent toutes les dispositions d’un groupe de 24 pièces, sans dire en combien d’étapes. La seule borne sûre sur cette longueur était la taille de cet ensemble de dispositions, environ 3,1 × 10²³ étapes, et la formule finit par utiliser à deux endroits le nombre géant 24! (1 × 2 × … × 24, environ 6,2 × 10²³). À l’inverse, la borne inférieure — le nombre de coups dont presque tout cube mélangé a besoin — a une constante modeste, d’environ 12,88. Beaucoup, dans la communauté, pensaient donc qu’un tel algorithme ne serait jamais praticable pour des tailles raisonnables.
Jeremy Mrzyglocki, Tomas Rokicki, Maxine Perroni-Scharf et Erik Demaine, du MIT, de la TU Munich et de Palo Alto, ont désormais rendu cette constante explicite, et petite.
Des réseaux de tri pour des pièces de cube
Sur un grand cube, les pièces centrales dominent : leur nombre croît comme n², alors que coins et arêtes n’ajoutent que des termes proportionnels à n. Les pièces centrales se répartissent en familles de 24 qui ne peuvent s’échanger qu’entre elles. L’outil de base est le commutateur, une suite de la forme A B A′ B′ — faire A, puis B, puis défaire A, puis défaire B — qui laisse presque tout en place et ne permute que trois pièces d’une famille. L’équipe a trouvé des suites de coups pour les 4 000 échanges de trois pièces utilisables, chacune de 12 coups au plus.
Deux idées font chuter le compte. D’abord, le même commutateur peut s’appliquer à de nombreuses familles à la fois, sur des groupes entiers de lignes et de colonnes. Ensuite, au lieu de résoudre chaque famille séparément, toutes suivent une même séquence universelle d’échanges, en sautant simplement ceux dont elles n’ont pas besoin. Un lemme relie le tout : une séquence universelle de L étapes donne une constante dominante de L/2.
Pour raccourcir cette séquence, l’équipe emprunte à l’informatique ses réseaux de tri, des schémas fixes de comparaisons qui trient n’importe quelle entrée. Un réseau de tri optimal à six entrées donne 96 étapes, donc une constante de 48. Des réseaux qui répartissent les 24 positions en groupes de 12, puis de 4, trouvés par recherche informatique, la ramènent à 72 étapes, donc une constante de 36. Enfin, autoriser des coups qui déplacent plus de trois pièces à la fois et répartir autrement les positions la font descendre à 61 étapes.
Trente virgule cinq
Le théorème : tout cube n×n×n se résout en au plus 30,5 n²/lg n coups, plus des termes qui deviennent négligeables quand n est grand. La constante est améliorée d’un facteur de plus de 3,30 × 10³⁸, et se situe à un facteur 2,37 de la borne inférieure (30,5 / 12,88). Pour la version plate n×n×1, qui sert d’échauffement, la constante passe de 12 ou 18 à 1,5.

Huit images régulièrement espacées de la résolution d’un cube de 256 rangées par côté : les faces mélangées deviennent des couleurs unies. — Figure 1.1, Mrzyglocki et al. (2026), arXiv:2611.11018.
L’algorithme tourne en un temps proportionnel au nombre de pièces, et les auteurs fournissent un solveur libre, avec des scripts qui vérifient exhaustivement chaque réseau dont il dépend. Leur propre comparaison le place devant les solveurs existants à partir d’environ n = 840 ; des animations montrent la résolution de cubes de 256 et de 65 536 rangées par côté.
Le 2,37 est un énoncé asymptotique : les termes plus petits de la formule ne sont pas chiffrés, elle ne donne donc pas un nombre exact de coups pour un cube précis. Les prochains gains, suggèrent les auteurs, pourraient venir d’autres façons de regrouper les pièces dans les réseaux de tri et de meilleurs échanges de trois pièces — et la même machinerie pourrait s’attaquer à d’autres casse-tête géants, ou à des hypercubes en quatre et cinq dimensions.
