Le Rubik's Cube peut se résoudre en 26 mouvements maximum

Des chercheurs de la Northeastern University (Massachusetts), le professeur Cooperman et un étudiant en thèse, Dan Kunkle, ont prouvé une propriété qui va intéresser les fans de Rubik's Cube, alors que le record du monde de résolution de ce cube de 3x3x3 à 54 carrés de couleur vient d'être battu en 9.86 secondes par un français.

Un problème restait jusqu'alors entier: en combien de mouvements minimum peut-on être sûr de venir à bout de ce casse tête quelle que soit la configuration de départ ? Jusque-là le chiffre de 29 puis, l'an dernier, celui de 27 avaient été avancés. Cooperman et Kunkle ont établi que l'on peut y arriver en 26 mouvements seulement.

La difficulté réside surtout dans le nombre de possibilités, parmi les 8! x 3^7 x 12! x 2^10 = 43.252.003.274.489.856.000 configurations possibles du cube. Il aura fallu 63 heures de calcul à 128 processeurs (soit 8.000 heures CPU) et 7 Tbits de données temporaires pour conclure qu'il faut au maximum 26 mouvements pour venir à bout du Rubik's cube quelle que soit la configuration de départ (le calcul s'appuie cependant sur un pré-calcul de ce que donne un mouvement donné pour chacune des 6,5x10E13 familles de configurations de départ ou cosets). Les calculs ont été effectués sur le réseau Teragrid en utilisant un disque distribué de 7 Tbits, un des premiers noeuds d'un espace de stockage de 20 Tbits financé par une bourse de 200.000 dollars de la NSF.

Ces travaux de recherche qui mêlent la théorie des groupes (théorie des groupes de permutation, en exploitant les 48 symétries du Rubik's cube) et l'algorithmie parallèle, contribuent à démontrer la faisabilité de calculs combinatoires en manipulant des nombres gigantesques à l'aide de l'informatique. En poussant plus loin les calculs, il faut s'attendre prochainement à un nombre de mouvements encore inférieurs.




Source: BE Etats-Unis numéro 84 (29/06/2007) - Ambassade de France aux Etats-Unis / ADIT

Excellent!C'est très amusant ce jeu!

Il y avait aussi certains mouvements qui permttaient de le résoudre à coup sûr, mais faut que je les retrouve...

Oui j'avais un polycopié qui donnait la solution en faisant le cube en trois couronnes, mais dans mon souvenir ça prenait bien plus de 26 mouvements.

oui parce que c'etait pas une solution optimale....

C'était une solution qui était par contre assez facile à mettre en oeuvre, même pour un gosse comme moi à l'époque. J'aimerais vraiment connaitre ces 26 mouvements, le problème c'est que je n'ai plus de cube sous la main pour tester

oui mais pour connaitre ces 26 mouvements, tu as au minimum 500 000 000 000 de possibilités a mémoriser... donc methode optimale pour un ordi, mais pour un humain... pas sûr...

Moi je résoud le problème en décollant les cubes et en les remettant

Haha, ça m'est arrivé aussi

beh pareil... de toute facon je suis une tanche moi a ce jeu... au bout de 1000 mouvements, j'ai toujours rien...

Par pur hasard j'avais réussi a en remettre un en place, le temps que j'aille chercher mon père pour lui montrer, ma petite cousine avait déja tout démonté...

Depuis j'alimente une haine féroce contre les rubiks cube et ma cousine...