20 est le nombre de Dieu… au Rubik’s Cube

C’était il y a trente ans. Sous le sapin du Noël 1980 m’attendait un cadeau infernal : un cube à 6 faces de couleurs différentes, chacune décomposée en 9 pastilles carrées. Le cube du Hongrois Ernö Rubik venait de faire son entrée dans mon existence, tout comme il allait hanter des centaines de millions de foyers à la surface du globe. Je n’eus pas la ténacité de ce Britannique qui employa vingt-six années de sa vie à résoudre ce casse-tête sans la moindre aide et la solution me fut donnée par mon prof de maths de quatrième, sous la forme de quelques pages découpées dans une revue scientifique. Certes, il me fallut apprendre des formules absconses par cœur mais ce n’était pas si difficile que cela, surtout si l’on mettait en regard de cet effort l’aura que me valut le pouvoir presque magique de refaire ce maudit cube… Et puis, comme dans Toy Story 3, le jouet finit par me tomber des mains et rejoindre les jolis fantômes de mon enfance.

Puisque le temps passe, lorsque j’ai eu à mon tour des enfants, un Rubik’s Cube est réapparu chez moi. Bien sûr, j’avais oublié les deux tiers de mes formules. Il a donc fallu que je me documente pour, de nouveau, passer pour un dieu, cette fois aux yeux de mes fils. Ce qui m’a permis de découvrir des méthodes de résolution plus simples que la mienne ainsi que… les maths cachées derrière ce casse-tête. Surtout, j’ai appris qu’une énigme plus forte que le Rubik’s Cube lui-même résistait depuis des années aux chercheurs : quel était le nombre maximum de mouvements à effectuer pour reconstituer le cube, quelle que soit la position de départ ? Cette question pourra sembler complètement futile mais il s’agit en réalité d’un défi sérieux posé à une branche des mathématiques appelée théorie des groupes.

Pendant trente ans, elle a tenté de trouver la valeur de ce nombre maximal, surnommé le nombre de Dieu. Et elle vient d’y parvenir. Il faut dire que le travail était titanesque. Imaginez-vous qu’il y a exactement 43.252.003.274.489.856.000 positions de départ possibles. Si vous avez du mal à lire des nombres aussi longs, c’est plus de 43 milliards de milliards de positions. A côté de cela, le nombre de combinaisons à Euro Millions est ridiculement petit : 76.275.360, soit 567 milliards de fois moins… Evidemment, pour les chercheurs qui s’intéressaient au nombre de Dieu, pas question de vérifier les possibilités une par une.

Il leur fallait donc surmonter deux obstacles : le premier, purement mathématique, consistait à réduire le nombre de positions pertinentes (beaucoup de positions sont les miroirs des autres) et à élaborer un algorithme capable de calculer le nombre de mouvements nécessaire pour recomposer le cube ; le second, purement technique, à trouver assez de “temps d’ordinateur” pour faire tourner l’algorithme. Le mathématicien Morley Davidson, l’ingénieur John Dethridge, le professeur de mathématiques Herbert Kociemba et le programmeur Tomas Rokicki viennent d’y parvenir. Le nombre de Dieu est 20. Quelle que soit la position de départ du cube, il faut, en théorie, au maximum 20 coups de poignet pour que les six faces retrouvent leur uniformité de couleur. En réalité, de 16 à 19 mouvements suffisent la plupart du temps mais, pour 100 à 300 millions de positions, 20 sont nécessaires.

Pour obtenir ce résultat, le quatuor cité plus haut a divisé les quelque 43 milliards de milliards de combinaisons en 2.217.093.120 ensembles contenant chacun 19.508.428.800 positions. Puis, ils ont réduit le nombre d’ensembles à 55.882.296, en exploitant les symétries et les recouvrements d’ensembles. Ils ont ensuite écrit un programme qui parvenait à résoudre un ensemble en 20 secondes environ sur un bon ordinateur portable (4 cœurs, 2,8 GHz, pour les puristes qui ne manqueront pas de me le demander si je ne leur fournis pas ce détail). Mais il y avait comme un hic. Comme un rapide calcul le montre, même en ne prenant que 20 secondes pour chaque ensemble de 19,5 milliards de positions, avec 55.882.296 ensembles, il faut… 35 ans pour faire le tour de la question ! C’est là que John Dethridge a été utile. Il faut préciser que cet homme est ingénieur chez Google et que sa société possède beaucoup, mais alors beaucoup, d’ordinateurs. En répartissant la tâche sur plusieurs machines, le temps de calcul a été ramené à quelques semaines.

Il n’est pas sûr que ces travaux soient très utiles, en pratique, aux champions du Cube. D’autant que ceux-ci se sont déjà empiriquement rapprochés de Dieu. Les techniques actuelles de résolution nécessitent une trentaine de mouvements, voire moins. Le record du monde de rapidité est un époustouflant 7,08 secondes, réalisé par le Néerlandais Eric Akkersdijk en 2008. A savourer ci-dessous, même si la vidéo est de piètre qualité.

Pierre Barthélémy