Le cube de Rubik en 26 mouvements ou moins

Tous connaissent le cube de Rubik, ce casse-tête géométrique à trois dimensions inventé en 1974 par le Hongrois Ernő Rubik, et qui a connu une popularité fulgurante dans les années quatre-vingt. Quel est le nombre minimal de mouvements requis pour résoudre n’importe quel cube Rubik?



Cette question intéresse au plus haut point les informaticiens et les chercheurs qui y voient un défi de programmation hors du commun. Ainsi, deux chercheurs américains, Daniel Kunkle et Gene Cooperman de l'Université Northeastern à Boston, ont programmé un superordinateur pour trouver la solution. Ils ont constaté rapidement qu’il faudrait un ordinateur encore plus puissant que celui utilisé pour résoudre ce problème complexe avec une certaine rapidité. L’énigme est qualifiée par certains d’algorithme de Dieu ou nombre de Dieu. Il existe 43 milliards de milliards de combinaisons possibles à ce petit jeu.

Ne disposant pas d’un supercalculateur suffisamment puissant, les chercheurs ont utilisé une méthode adaptée à la puissance de leur ordinateur. Ils ont donc programmé, dans un premier temps, l’ordinateur pour trouver 15 000 cubes à semi-résolus. De cette façon, la suite exigeait moins de puissance et le problème pouvait se résoudre en quelques mouvements. Après environ 63 heures de calcul, une solution exigeant 26 mouvements a finalement été identifiée. Cette solution n’est pas la solution optimale. Selon certains experts, le cube de Rubik pourrait se résoudre en près de 20 mouvements.

La véritable réponse à l’algorithme de Dieu reste encore à trouver. Il faudra, certes, disposer de superordinateurs pour trouver l’ultime solution. Pour le moment, le record officiel du temps minimum requis pour résoudre le cube Rubik est de 9,86 secondes et appartient à Thibaut Jacquinot, record homologué le 5 mai 2007. Le prochain championnat de cube Rubik se tiendra à Budapest, du 5 au 7 octobre prochain. Le championnat porte sur le temps minimum et non sur le nombre minimum de mouvements.