La mathématique du Rubik's Cube

L'endroit pour balancer tous les liens que vous trouvez sur et autour des cubes !
Boutiques de cubes sur internet | Les Timers | Liens vers quelques méthodes différentes | Johannes Laire - Méthode Petrus
Répondre
Désactivé

La mathématique du Rubik's Cube

Message par Désactivé »

J'ai écrit un billet là dessus: http://www.abstraction.fr.nf
Pour les matheux ;) j'y évoques le nombre de combinaisons et son calcul, comment on crée les algorithmes et la place de l'informatique
Bannière atoutcubes.com
Avatar du membre
Spols
Le belge du Magic
Messages : 5455
Enregistré le : jeu. août 18, 2005 2:44 pm
Localisation : Sur mon clavier ou dans mon lit
Contact :

Re: La mathématique du Rubik's Cube

Message par Spols »

J'ai pas encore tout lu mais je compte bien le faire prochainement

j'ai juste une phrase qui m'a fait tyiquer.
En effet, l’opération serait réaliser les mélanges l’un après l’autre, l’élément neutre serait l’absence de mouvement et tout mélangé possède son mélange inverse.
je pense qu'il y a quelques corrections à faire
En effet, l’opération serait de réaliser les mélanges les uns après les autres, l’élément neutre serait l’absence de mouvement et tout mélange possède son mélange inverse.
Ce nouveau forum valait bien une nouvelle signature
Avatar du membre
Cubeur-manchot
VIP au club des 1000
Messages : 2999
Enregistré le : jeu. sept. 11, 2014 5:16 pm
Localisation : Bures-sur-Yvette (91)
Contact :

Re: La mathématique du Rubik's Cube

Message par Cubeur-manchot »

Voilà un joli petit article tout mignon :oui:

Bon, je ne t'embêterai pas trop avec les fautes, juste une d'entre elles :
:arete

Sinon un paragraphe qui m'a choqué :
La mathématique du rubik's cube a écrit :Cependant, n’existerait il pas une méthode plus simple qui ne nécessiterait ni intuition, ni logique, ni apprentissage? À vrai dire si. Les cubeurs appellent ça l’algorithme de Dieu. C’est un algorithme qui à partir de n’importe quelle configuration permettrait par simple itération de celui-ci de résoudre le casse-tête. Il est évident que ce dernier devra parcourir toutes les configurations du cube et un humain pourrait mettre plusieurs milliards d’années à effectuer l’algorithme avant qu’il ne parvienne en effet à résoudre le puzzle.
Ouille, là ça pique les neuils :?
  • Il faut savoir que qu'"exécuter l'algorithme de Dieu" signifie résoudre le cube avec le nombre optimal de mouvements. Il faut être totalement omniscient sur le cube pour pouvoir déterminer cette séquence de mouvements, d'où le caractère divin de l'appellation.
    Par conséquent, si on résout le cube avec le nombre minimal de mouvements, alors justement on ne passe pas par toutes les positions, au contraire on veut essayer d'en parcourir le moins possible... ou alors ce que tu voulais dire c'est qu'il faut mentalement parcourir toutes les positions pour savoir par lesquelles il faut passer, et ensuite résoudre le cube selon cette séquence ?
  • Autre petite chose, quand tu parles d'itération, tu parles d'exécution ou de répétition ? Si c'est exécution, alors ok pas de soucis, sinon c'est faux. La plus grande périodicité de permutation doit être un truc comme 1260 si je me rappelle bien. C'est-à-dire que tout algorithme exécuté 1260 fois (sans rotation de cube, sinon le nombre est plus grand), quel qu'il soit, nous fait forcément retomber sur la position initiale. On parcourerait donc 1259 états du cube avant de retomber sur l'état initial, le 1260ème état, et on est loin d'avoir parcouru les 43 trillions (et des brouettes) combinaisons.
  • Si on voulait parcourir toutes les combinaisons une et une seule fois (un chemin Hamiltonien dans notre graphe des combinaisons), alors là oui on passerait par tous les états du cube, mais aucune optimalité pour atteindre un état donné (au contraire), et il n'y aurait qu'une seule itération (on n'irait d'ailleurs même pas jusqu'à la fin de l'algorithme, sinon on retomberait sur la position initiale).
Sinon très bonne initiative, c'est bien d'avoir mis des valeurs numériques, pour bien qu'on se rende compte de la grandeur des chiffres :oui:
Et c'est très bien aussi d'avoir mis la formule générale pour les cubes NxNxN :oui: Juste petit détail mais vraiment du détail, j'ai voulu vérifier et c'est vrai que préciser si un 24! c'est parce que 4 positions sur chacune des 6 faces, ou bien si c'est parce que 4! combinaisons sur une face, ça peut apporter en clarté de compréhension, même si ça allourdirait la formule encore plus qu'elle ne l'est déjà pour un non-matheux... C'est toi qui vois :oui:
La mathématique du rubik's cube a écrit :Heureusement le génie des programmeurs et les ordinateurs de Google sont venus à bout de cette contrainte
Maigre résumé, mais je ne peux pas l'infirmer :P
Désactivé

Re: La mathématique du Rubik's Cube

Message par Désactivé »

Ca fait plaisir d'avoir des retours !
'"exécuter l'algorithme de Dieu" signifie résoudre le cube avec le nombre optimal de mouvements
D'après ce que j'ai lu c'est en effet un des sens de cet appellation mais elle a également celui que j'ai cité
itération
Pour moi cela est une exécution ;)
La plus grande périodicité de permutation doit être un truc comme 1260 si je me rappelle bien. C'est-à-dire que tout algorithme exécuté 1260 fois (sans rotation de cube, sinon le nombre est plus grand), quel qu'il soit, nous fait forcément retomber sur la position initiale. On parcourerait donc 1259 états du cube avant de retomber sur l'état initial, le 1260ème état, et on est loin d'avoir parcouru les 43 trillions (et des brouettes) combinaisons.
En fait non, quand tu fais un algorithme de 10 mouvements 5 fois tu passes par 50 (ou moins selon l'algorithme) combinaisons mais pas 5
Après je n'ai jamais dit qu'un tel algo existait
Si on voulait parcourir toutes les combinaisons une et une seule fois (un chemin Hamiltonien dans notre graphe des combinaisons), alors là oui on passerait par tous les états du cube, mais aucune optimalité pour atteindre un état donné (au contraire), et il n'y aurait qu'une seule itération (on n'irait d'ailleurs même pas jusqu'à la fin de l'algorithme, sinon on retomberait sur la position initiale).
Très bonne remarque dans le cadre de TA définition de l'algorithme de Dieu, ce n'est as la mienne ni celle dune partie de la communauté ;)
même si ça allourdirait la formule encore plus qu'elle ne l'est déjà pour un non-matheux
On me l'a déjà dit donc je pense que je vais rester là-dessus :)
Maigre résumé, mais je ne peux pas l'infirmer :P
Si tu as une quelconque source détaillant le processus je suis preneur
je ne t'embêterai pas trop avec les fautes
Au contraire n'hésite pas !!
Je pense qu'il y a quelques corrections à faire
En effet il manque un pluriel :)

Je me lance donc dans ces quelques corrections et merci pour les critiques constructives
Désactivé

Re: La mathématique du Rubik's Cube

Message par Désactivé »

Voilà une source parmi tant d'autres sur ma vision de l'algorithme de Dieu https://youtu.be/VONX2gO3XcU
Avatar du membre
Arsonist
VIP au club des 1000
Messages : 1978
Enregistré le : mer. sept. 05, 2007 12:39 pm
Contact :

Re: La mathématique du Rubik's Cube

Message par Arsonist »

Je pense que tu es plus à la recherche d'un Devil's Algorithm

(Tu devrais trouver des renseignements sur la page de Jaap)
Image
Avatar du membre
Cubeur-manchot
VIP au club des 1000
Messages : 2999
Enregistré le : jeu. sept. 11, 2014 5:16 pm
Localisation : Bures-sur-Yvette (91)
Contact :

Re: La mathématique du Rubik's Cube

Message par Cubeur-manchot »

VickTor a écrit :
'"exécuter l'algorithme de Dieu" signifie résoudre le cube avec le nombre optimal de mouvements
D'après ce que j'ai lu c'est en effet un des sens de cet appellation mais elle a également celui que j'ai cité
Devil's algorithm = algorithme du Diable // God's algorithm = algorithme de Dieu
Je me souviens qu'il y avait eu un amalgame à un moment, mais en tout ça ce que j'ai écrit les deux lignes au-dessus c'est 100% vérité pas de doute :)
VickTor a écrit :
La plus grande périodicité de permutation doit être un truc comme 1260 si je me rappelle bien. C'est-à-dire que tout algorithme exécuté 1260 fois (sans rotation de cube, sinon le nombre est plus grand), quel qu'il soit, nous fait forcément retomber sur la position initiale. On parcourerait donc 1259 états du cube avant de retomber sur l'état initial, le 1260ème état, et on est loin d'avoir parcouru les 43 trillions (et des brouettes) combinaisons.
En fait non, quand tu fais un algorithme de 10 mouvements 5 fois tu passes par 50 (ou moins selon l'algorithme) combinaisons mais pas 5
Après je n'ai jamais dit qu'un tel algo existait
Exact, bien vu :oui:
VickTor a écrit :
Maigre résumé, mais je ne peux pas l'infirmer :P
Si tu as une quelconque source détaillant le processus je suis preneur
Si tu causes anglais il y a le site de Kociemba. Éclate toi :yawinkle:
Désactivé

Re: La mathématique du Rubik's Cube

Message par Désactivé »

Sur le forum speedsolving on peut lire sur une page consacrée au Devil's

A given sequence of moves, if repeated enough times, will return the cube to the original state.
The number of repetitions needed to return to the original state, multiplied by the QTM of the sequence, gives how many states the cube traverses.
A sequence can be found, that traverses every state of cube.
This sequence is God's algorithm, as defined
above.

Donc il y a bel et bien des confusions :p
Du coup je change l'article que je vais au passage diviser en deux parties pour ta source :)
L'anglais ne me pose pas trop de problème

Par conséquent merci bcp ! Je corrige cette nuance et réalisé les ajouts
C'est génial de tels retours
Désactivé

Re: La mathématique du Rubik's Cube

Message par Désactivé »

Voilà l'illustration pour le billet sur les algorithmes de Dieu et du Diable

Image
Désactivé

Re: La mathématique du Rubik's Cube

Message par Désactivé »

J'ai écrit l'article correspondant,https://abstractionmathematique.wordpre ... du-diable/ j'aimerai avoir votre avis :)
Avatar du membre
Arsonist
VIP au club des 1000
Messages : 1978
Enregistré le : mer. sept. 05, 2007 12:39 pm
Contact :

Re: La mathématique du Rubik's Cube

Message par Arsonist »

Chaud de confondre "millier" et "million"

Ce graphe est très laid, par ailleurs, et tu as sur cube20 un tableau beaucoup plus précis de la répartition.
Image
Désactivé

Re: La mathématique du Rubik's Cube

Message par Désactivé »

A quelle endroit cette confusion ?
*edit* J'ai repéré et rectifié l'erreur merci :)
Ce graphe est très laid
Merci c'est très constructif :?
Et le graphe n'est pas de moi j'ai cité la source en bas de page :) je peux changer si tu trouves qu'il y a plus beau.
Répondre