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 (Le mot monde peut désigner 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 (L'heure est une unité de mesure de calcul à 128 processeurs (soit 8.000 heures CPU) et 7 Tbits de données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose,...) 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 (Un réseau informatique est un ensemble d'équipements reliés entre eux pour échanger des informations. Par analogie avec...) Teragrid en utilisant un disque (Le mot disque est employé, aussi bien en géométrie que dans la vie courante, pour désigner une forme ronde et...) 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 (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage...) des groupes (théorie des groupes de permutation (En mathématiques, la notion de permutation exprime l'idée de réarrangement d'objets discernables. Une permutation de n...), 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 (L'informatique désigne l'automatisation du traitement de l'information par un système, concret (machine) ou abstrait....). 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
Illustration: WikipédiaCommentez cette news: 44 commentaires







//////////////////////////////////////////////////////////////////