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 le mois dernier 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 x 10E7 x 12! x 2 x 10E10 = 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 premier noeud 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 :
– Northeastern University researchers solve Rubik’s Cube in 26 moves
https://www.eurekalert.org/pub_releases/2007-05/nu-nur053107.php
– The search for ‘God’s Number’ in a Rubik’s Cube, 25 juin 2007 (article grand public)
https://www.boston.com/news/globe/health_science/articles/2007/06/25/the_search_for_gods_number_in_a_rubiks_cube/
– Twenty-Six Moves Suffice for Rubik’s Cube, D. Kunkle et G. Cooperman, Proc. of International Symposium on Symbolic and Algebraic Computation (ISSAC ’07), ACM Press, 2007, à paraître, la publication d’origine
https://www.ccs.neu.edu/home/gene/papers/rubik.pdf
Pour en savoir plus, contacts :
– Refereed Publications of Gene Cooperman
https://www.ccs.neu.edu/home/gene/papers.html
– Recherches de Dan Kunkle
https://www.ccis.neu.edu/home/kunkle/projects.html#aas
– Northeastern University
https://www.northeastern.edu/neuhome/index.html
– Group Theory via Rubik’s Cube, 6/12/2006 (document de travail)
https://www.geometer.org/rubik/group.pdf
Code brève
ADIT : 43421
Rédacteur :
Vincent Reboul [email protected] – Jean-Philippe Lagrange, [email protected]
