La mathématique du Rubik's Cube
La mathématique du Rubik's Cube
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
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
- Spols
- Le belge du Magic
- Messages : 5465
- 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
J'ai pas encore tout lu mais je compte bien le faire prochainement
j'ai juste une phrase qui m'a fait tyiquer.
j'ai juste une phrase qui m'a fait tyiquer.
je pense qu'il y a quelques corrections à faireEn 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.
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
- 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
Voilà un joli petit article tout mignon
Bon, je ne t'embêterai pas trop avec les fautes, juste une d'entre elles :
Sinon un paragraphe qui m'a choqué :
Et c'est très bien aussi d'avoir mis la formule générale pour les cubes NxNxN 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
Bon, je ne t'embêterai pas trop avec les fautes, juste une d'entre elles :
Sinon un paragraphe qui m'a choqué :
Ouille, là ça pique les neuilsLa 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.
- 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).
Et c'est très bien aussi d'avoir mis la formule générale pour les cubes NxNxN 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
Maigre résumé, mais je ne peux pas l'infirmerLa 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
Re: La mathématique du Rubik's Cube
Ca fait plaisir d'avoir des retours !
Après je n'ai jamais dit qu'un tel algo existait
Je me lance donc dans ces quelques corrections et merci pour les critiques constructives
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é'"exécuter l'algorithme de Dieu" signifie résoudre le cube avec le nombre optimal de mouvements
Pour moi cela est une exécutionitération
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 5La 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.
Après je n'ai jamais dit qu'un tel algo existait
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é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).
On me l'a déjà dit donc je pense que je vais rester là-dessusmême si ça allourdirait la formule encore plus qu'elle ne l'est déjà pour un non-matheux
Si tu as une quelconque source détaillant le processus je suis preneurMaigre résumé, mais je ne peux pas l'infirmer
Au contraire n'hésite pas !!je ne t'embêterai pas trop avec les fautes
En effet il manque un plurielJe pense qu'il y a quelques corrections à faire
Je me lance donc dans ces quelques corrections et merci pour les critiques constructives
Re: La mathématique du Rubik's Cube
Voilà une source parmi tant d'autres sur ma vision de l'algorithme de Dieu https://youtu.be/VONX2gO3XcU
- 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
Je pense que tu es plus à la recherche d'un Devil's Algorithm
(Tu devrais trouver des renseignements sur la page de Jaap)
(Tu devrais trouver des renseignements sur la page de Jaap)
- 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
Devil's algorithm = algorithme du Diable // God's algorithm = algorithme de DieuVickTor a écrit :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é'"exécuter l'algorithme de Dieu" signifie résoudre le cube avec le nombre optimal de mouvements
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
Exact, bien vuVickTor a écrit :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 5La 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.
Après je n'ai jamais dit qu'un tel algo existait
Si tu causes anglais il y a le site de Kociemba. Éclate toiVickTor a écrit :Si tu as une quelconque source détaillant le processus je suis preneurMaigre résumé, mais je ne peux pas l'infirmer
Re: La mathématique du Rubik's Cube
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
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
Re: La mathématique du Rubik's Cube
Voilà l'illustration pour le billet sur les algorithmes de Dieu et du Diable
Re: La mathématique du Rubik's Cube
J'ai écrit l'article correspondant,https://abstractionmathematique.wordpre ... du-diable/ j'aimerai avoir votre avis
- 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
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.
Ce graphe est très laid, par ailleurs, et tu as sur cube20 un tableau beaucoup plus précis de la répartition.
Re: La mathématique du Rubik's Cube
A quelle endroit cette confusion ?
*edit* J'ai repéré et rectifié l'erreur merci
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.
*edit* J'ai repéré et rectifié l'erreur merci
Merci c'est très constructifCe graphe est très laid
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.