Page 1 sur 2

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

Publié : 05/07/2007 - 0:00:37
par Adrien
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

Publié : 05/07/2007 - 9:55:13
par Anthobask
lol, généralement, je le résoud en moyenne avec 150 mouvements avec la méthode Lars Petrus.


Sinon, le titre devrais plutot etre : "Le Rubik's Cube peut se résoudre en 26 mouvements minimum", non ?

Publié : 05/07/2007 - 10:13:01
par sonic
jamais réussi à le finir ce truc...

Publié : 05/07/2007 - 10:14:44
par Anthobask
Sur internet il y a des méthodes qui rendent la chose assez simple ;)

Publié : 05/07/2007 - 11:34:12
par Jill
tt depend du rubix cube aussi....... :sarcastic:

Publié : 05/07/2007 - 11:49:26
par Aldebaran
Rah moi ça m'énerve ce truc, la seule méthode que j'ai trouvé quand j'avais 8 ans c'est de décoller les étiquettes couleurs et de les replacer comme il faut :fada:

Publié : 05/07/2007 - 12:04:24
par Anthobask
Jill a écrit :tt dépend du rubix cube aussi....... :sarcastic:


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.

Publié : 05/07/2007 - 12:35:02
par halman
sonic a écrit :jamais réussi à le finir ce truc...


J'y suis arrivé une fois, je n'ai jamais réussi à retrouver comment.

Publié : 05/07/2007 - 13:58:28
par yoritomo
Je vais me faire traiter de coupeur de cheveux en 4, mais bon ... :sarcastic:
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 :non:

Cherchez l'erreur ... :grat:

Publié : 05/07/2007 - 14:21:49
par JuLieN
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 ... :sarcastic:
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 :non:

Cherchez l'erreur ... :grat:


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! :lol:
Image

Publié : 05/07/2007 - 14:23:43
par sonic
JuLieN a écrit :...
sonic a écrit :jamais réussi à le finir ce truc...


Tiens, ils ont sorti un modèle spécialement pour toi! :lol:
Image


:lol: excellent :D

Publié : 05/07/2007 - 15:21:05
par yoritomo
@JuLieN: merci pour tes infos :jap:

La formule est donc en fait
8! x 3E7 x 12! x 2E10
et pas 8! x 3 x 10E7 x 12! x 2 x 10E10 :siffle:

Publié : 05/07/2007 - 15:21:09
par Anthobask
JuLieN a écrit :
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.


ah oui en effet ;)

ha le rubik

Publié : 31/07/2007 - 0:39:57
par armir
vraimment cool le modèle à 24 face
c'est celui qu'il me faut.

Moi aussi j'ai décollé les autocollants... sob

Publié : 31/08/2007 - 17:33:52
par tTz
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. :D

Publié : 31/08/2007 - 17:42:12
par Victor
Tu as le droit à une médaille mais pas le Nobel vu que monsieur était jaloux d'un matheux qui l'avait fait cocu

Publié : 31/08/2007 - 17:53:45
par tTz
T es serieux ?

Ah oui je me souviens de cette histoire de nobel erff

trop b1 o_O
Sinon quelqu un saurait il si il y a un endroit special pour deposer sa decouverte ou un truc du genre..etc ?

Publié : 31/08/2007 - 17:55:48
par Victor
Si tu arrives a expliquer les symétries nécessaires simplement oui!

Publié : 31/08/2007 - 17:58:06
par tTz
Heu ok, mais je le ferai pas sur ce forum héhé.. =)

Sinon mon idee est assez simple oui

Symetrie .. je comprends pas trop ?

Publié : 31/08/2007 - 18:06:24
par Victor
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

Publié : 31/08/2007 - 18:24:27
par tTz
oh ok ! je vais me renseigner sur le sujet.. Je n ai encore pas regarder les methodes qu on utilisé les super matheux pour resoudre ce probleme.

En ce qui concerne ma solution il ne me semble pas avoir utilisé de super symetrie.. peut etre, dans quel cas je en connais pas la definition exacte

Publié : 31/08/2007 - 18:26:46
par Victor
Regarde du coté de la cristalo tu verras des trucs la théorie des groupes de Galois dans ton cas je ne sais pas

Publié : 31/08/2007 - 23:44:43
par fffred
tu as trouvé 26 mouvements aussi ? ^^

Publié : 01/09/2007 - 12:34:47
par Victor
On ne dira jamais l'efficacité des casse têtes... Que ce soient des puzzles... Des cassses têtes chinois ou le rubik'c Cube... Dans la capacité de gérer des données réelles du problème et d'agir sur ce problème... Dans ma jeunesse j'avais trop ce genre de trucs, puis j'en ai eu très marre

Publié : 02/09/2007 - 10:37:22
par tTz
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 !

:heink: :heink:

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......

:larme: