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

Pour parler math...

Modérateur : Modérateurs

Adrien
Site Admin
Messages : 17076
Inscription : 02/06/2004 - 17:58:53
Activité : Ingénieur
Localisation : 78
Contact :

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

Message par Adrien » 04/07/2007 - 23:00:37

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
Dernière modification par Adrien le 05/07/2007 - 17:19:10, modifié 1 fois.

Anthobask
Messages : 56
Inscription : 28/05/2007 - 0:23:09

Message par Anthobask » 05/07/2007 - 8:55:13

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 ?

Avatar de l’utilisateur
sonic
Messages : 2657
Inscription : 02/05/2006 - 8:53:14
Localisation : à coté d'antarès

Message par sonic » 05/07/2007 - 9:13:01

jamais réussi à le finir ce truc...

Anthobask
Messages : 56
Inscription : 28/05/2007 - 0:23:09

Message par Anthobask » 05/07/2007 - 9:14:44

Sur internet il y a des méthodes qui rendent la chose assez simple ;)

Avatar de l’utilisateur
Jill
Messages : 13
Inscription : 01/06/2007 - 16:20:40

Message par Jill » 05/07/2007 - 10:34:12

tt depend du rubix cube aussi....... :sarcastic:

Avatar de l’utilisateur
Aldebaran
Messages : 1807
Inscription : 15/06/2007 - 9:13:11

Message par Aldebaran » 05/07/2007 - 10:49:26

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:
«S'il n'y avait pas la Science, combien d'entre nous pourraient profiter de leur cancer pendant plus de cinq ans ?» P. Desproges

Anthobask
Messages : 56
Inscription : 28/05/2007 - 0:23:09

Message par Anthobask » 05/07/2007 - 11:04:24

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.

Avatar de l’utilisateur
halman
Messages : 173
Inscription : 11/06/2005 - 14:45:09

Message par halman » 05/07/2007 - 11:35:02

sonic a écrit :jamais réussi à le finir ce truc...


J'y suis arrivé une fois, je n'ai jamais réussi à retrouver comment.
L'homme est le Temple du Verbe, mais pas pour l'Eternité.

Les larmes d'Icare, les larmes de Neil Armstrong.

yoritomo
Messages : 2
Inscription : 05/07/2007 - 12:47:26

Message par yoritomo » 05/07/2007 - 12:58:28

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:

JuLieN
Messages : 112
Inscription : 26/06/2006 - 8:31:38

Message par JuLieN » 05/07/2007 - 13:21:49

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

Avatar de l’utilisateur
sonic
Messages : 2657
Inscription : 02/05/2006 - 8:53:14
Localisation : à coté d'antarès

Message par sonic » 05/07/2007 - 13:23:43

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

yoritomo
Messages : 2
Inscription : 05/07/2007 - 12:47:26

Message par yoritomo » 05/07/2007 - 14:21:05

@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:

Anthobask
Messages : 56
Inscription : 28/05/2007 - 0:23:09

Message par Anthobask » 05/07/2007 - 14:21:09

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 ;)

armir
Messages : 3
Inscription : 30/07/2007 - 22:34:35
Localisation : Paris / France
Contact :

ha le rubik

Message par armir » 30/07/2007 - 23:39:57

vraimment cool le modèle à 24 face
c'est celui qu'il me faut.

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

tTz
Messages : 9
Inscription : 31/08/2007 - 16:28:30

Message par tTz » 31/08/2007 - 16:33:52

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

Victor
Messages : 16087
Inscription : 05/06/2006 - 20:30:44
Activité : Retraité
Contact :

Message par Victor » 31/08/2007 - 16:42:12

Tu as le droit à une médaille mais pas le Nobel vu que monsieur était jaloux d'un matheux qui l'avait fait cocu

tTz
Messages : 9
Inscription : 31/08/2007 - 16:28:30

Message par tTz » 31/08/2007 - 16:53:45

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 ?

Victor
Messages : 16087
Inscription : 05/06/2006 - 20:30:44
Activité : Retraité
Contact :

Message par Victor » 31/08/2007 - 16:55:48

Si tu arrives a expliquer les symétries nécessaires simplement oui!

tTz
Messages : 9
Inscription : 31/08/2007 - 16:28:30

Message par tTz » 31/08/2007 - 16:58:06

Heu ok, mais je le ferai pas sur ce forum héhé.. =)

Sinon mon idee est assez simple oui

Symetrie .. je comprends pas trop ?

Victor
Messages : 16087
Inscription : 05/06/2006 - 20:30:44
Activité : Retraité
Contact :

Message par Victor » 31/08/2007 - 17:06:24

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

tTz
Messages : 9
Inscription : 31/08/2007 - 16:28:30

Message par tTz » 31/08/2007 - 17:24:27

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

Victor
Messages : 16087
Inscription : 05/06/2006 - 20:30:44
Activité : Retraité
Contact :

Message par Victor » 31/08/2007 - 17:26:46

Regarde du coté de la cristalo tu verras des trucs la théorie des groupes de Galois dans ton cas je ne sais pas

Avatar de l’utilisateur
fffred
Messages : 1538
Inscription : 10/06/2004 - 18:40:27
Localisation : ile de france

Message par fffred » 31/08/2007 - 22:44:43

tu as trouvé 26 mouvements aussi ? ^^
je suis certain que vous croyez avoir compris ce que j'essayais de vous dire, mais êtes-vous sûr que ce que j'ai dit correspondait vraiment à ce que je voulais dire ?

Victor
Messages : 16087
Inscription : 05/06/2006 - 20:30:44
Activité : Retraité
Contact :

Message par Victor » 01/09/2007 - 11:34:47

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

tTz
Messages : 9
Inscription : 31/08/2007 - 16:28:30

Message par tTz » 02/09/2007 - 9:37:22

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:

Répondre