Le Lézard

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.

Publié le 20/08/2007 à 18h00 par Normand Labelle



Nouvelle suivante:
La X07 au Canada

Autres nouvelles publiées en ce 20 août:

2001
Traduire la parole en temps réel!
Mauvais résultats chez Fujitsu
2002
L’alcool augmente l’attirance
Passer la tondeuse ... à partir du bureau!
2003
Un «gentil» virus?
Microsoft songe à automatiser les mises à jour
2004
Disparition des hivers en Europe d’ici 2080
Concours pour les lézards
Microsoft risque de perdre MSN Canada
Ubisoft donne encore plus de plaisir aux lézards
2005
Nouvelle console Nintendo : la Game Boy Micro
Le stylo de l’espace
2006
Des contacts d'affaires aux quatre vents