[News] Le Rubik's Cube peut se résoudre en 26 mouvements maximum
Modérateur : Modérateurs
-
- Site Admin
- Messages : 23657
- Inscription : 02/06/2004 - 18:58:53
- Activité : Ingénieur
- Localisation : 78
[News] 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
Illustration: Wikipédia
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
Illustration: Wikipédia
Dernière modification par Adrien le 05/07/2007 - 18:19:10, modifié 1 fois.
Jill a écrit :tt dépend du rubix cube aussi.......
Bah en faite avec la méthode débutant pour résoudre un 3×3×3, j'arrive a résoudre un 4×4×4, et un 5×5×5, Et même un mégaminx ( dodécaèdre ), donc en faite il reste beaucoup de similitude avec quelques difficulté supplémentaire selon le rubik's.
Anthobask a écrit :Sinon, le titre devrais plutot etre : "Le Rubik's Cube peut se résoudre en 26 mouvements minimum", non ?
Non, le titre est correct. On peut imaginer un Rubik's cube dans un état de quasi-ordre tel qu'une seule permutation suffise à le résoudre.
Par contre, le titre veut bien dire que, dans l'état de désordre maximal, 26 permutations suffisent à le résoudre. Il est donc correct de dire que le Rubik's Cube peut se résoudre en 26 mouvements maximum, même s'il auarit été moins abscons d'écrire "il suffit de 26 mouvements pour résoudre n'importe quel Rubik's Cube."
yoritomo a écrit :Je vais me faire traiter de coupeur de cheveux en 4, mais bon ...
8! x 3 x 10E7 x 12! x 2 x 10E10 =
11.588.006.707.200.000.000.000.000.000.000
et pas 43.252.003.274.489.856.000
Cherchez l'erreur ...
Wikipedia répond très bien à ton interrogation :
In fact, there are (8! × 38) × (12! × 212) = 519,024,039,293,878,272,000 (about 519 quintillion on the short scale) possible arrangements of the pieces that make up the Cube, but only one in twelve of these are actually reachable. This is because there is no sequence of moves that will swap a single pair or rotate a single corner or edge cube. Thus there are twelve possible sets of reachable configurations, sometimes called "universes" or "orbits", into which the Cube can be placed by dismantling and reassembling it.
Et le détail du calcul est donné par le Wikipedia français à cette adresse.
sonic a écrit :jamais réussi à le finir ce truc...
Tiens, ils ont sorti un modèle spécialement pour toi!
ha le rubik
vraimment cool le modèle à 24 face
c'est celui qu'il me faut.
Moi aussi j'ai décollé les autocollants... sob
c'est celui qu'il me faut.
Moi aussi j'ai décollé les autocollants... sob
Salut,
En voyant cette news j ai tenté d elucider le probleme...
Et j'ai reussi a trouver le nombre exact de mouvements à faire pour resoudre le rubicube depuis nimporte quelle facette .. Pas besoin de mega super calculateurs de la nasa mais juste un cerveau un crayon et une calculette.
Ok, j ai tout mes calculs, un resultats, je sais plus quoi faire ?
Sinon pour ma part je reussi a le finir en 1 minute.
En voyant cette news j ai tenté d elucider le probleme...
Et j'ai reussi a trouver le nombre exact de mouvements à faire pour resoudre le rubicube depuis nimporte quelle facette .. Pas besoin de mega super calculateurs de la nasa mais juste un cerveau un crayon et une calculette.
Ok, j ai tout mes calculs, un resultats, je sais plus quoi faire ?
Sinon pour ma part je reussi a le finir en 1 minute.
tTz a écrit :Heu ok, mais je le ferai pas sur ce forum héhé.. =)
Sinon mon idee est assez simple ouiSymetrie .. je comprends pas trop ?
le rubycube est basé sur des itération de rotations pour obtenir un coté unicolore, les symétries sont des rotations dans une supersymétrie cubique bref un problème des symétries que les matheux cherchent à comprendre
non le nombre de mouvements exact que j ai trouvé se trouve en dessous de 26... =) ca servirai a rien que je parle sinon..
enfin, j ai fais qqs recherches qui m ont appris bien de choses sur les recherches qui se font sur le nombre de mlouvements maximum... Et je suis tombé par hasard........
sur un logiciel qui s appelle : "Cube explorer 1.5"
que vous pouvez telecharger a cette adresse si ca vous interesse :
http://trucsmaths.free.fr/telech/cubexp15.zip
Et qui permet de trouver la solution de resolution de nimporte quelle configuration du rubicube En un maximum de 22 mouvements !
Je l'ai testé ca marche reellement...
Mais moi je comprends plus rien. Ou alors j ai pas bien compris ce que les scientifiques ont tentés de chercher...
Car 128 processeurs qui trouve juste le nombre de mouvements maximum en plusieurs jours.
Opposé à un logiciel alimenté par mon pauvre ordinateur qui trouve le nombre de mouvements minimum possible en quelques minutes et sans ecceder 22 mouvements.. et en plus qui dit comment faire......
enfin, j ai fais qqs recherches qui m ont appris bien de choses sur les recherches qui se font sur le nombre de mlouvements maximum... Et je suis tombé par hasard........
sur un logiciel qui s appelle : "Cube explorer 1.5"
que vous pouvez telecharger a cette adresse si ca vous interesse :
http://trucsmaths.free.fr/telech/cubexp15.zip
Et qui permet de trouver la solution de resolution de nimporte quelle configuration du rubicube En un maximum de 22 mouvements !
Je l'ai testé ca marche reellement...
Mais moi je comprends plus rien. Ou alors j ai pas bien compris ce que les scientifiques ont tentés de chercher...
Car 128 processeurs qui trouve juste le nombre de mouvements maximum en plusieurs jours.
Opposé à un logiciel alimenté par mon pauvre ordinateur qui trouve le nombre de mouvements minimum possible en quelques minutes et sans ecceder 22 mouvements.. et en plus qui dit comment faire......