Modélisation informatique du cube (Mapple)

Vos questions / remarques sur le cube classique 3x3x3
Les méthodes principales du 3x3x3 et leurs variantes
Les visiteurs peuvent poster des messages dans cette partie
mathsup11
Discret
Messages : 1
Enregistré le : sam. mars 26, 2011 5:50 pm

Modélisation informatique du cube (Mapple)

Message par mathsup11 »

Bonjour,

Nous sommes actuellement deux étudiants en MPSI, nous avons choisi comme étude pour nos TIPE le rubik's cube. On a beaucoup de mal pour l'expérience informatique : la méthode Thistlethwaite. On ne comprend pas comment faire le programme en Mapple pour le placement des arrêtes. Plus précisément pour entrer dans une base de donnée la liste des mouvements du cube. C'est pourquoi on sollicite votre aide.

Ps: Que pensez-vous des autres méthodes modélisables par Mapple appliquées au cube ?

Merci d'avance.
Bannière atoutcubes.com
rafoo
VIP au club des 1000
Messages : 2861
Enregistré le : jeu. avr. 09, 2009 11:57 am
Localisation : Paris
Contact :

Re: Modélisation informatique du cube (Mapple)

Message par rafoo »

Je remets ce que j'ai déjà répondu par mp histoire que les autres puissent donner leurs avis. Je suis bien évidemment prêt à donner des détails



Il y a trois types de méthodes qu'on peut coder, du plus facile et intéressant au plus dur et chiant :
1) les méthodes purement informatiques (Thistlethwaite et Kociemba) : il y a pas mal de trucs à dire sur la théorie des groupes et les parcours de graphe
2) les méthodes de blind (3-cycles, old Pochmann) : à peine plus dur à coder et a le mérite de vous permettre d'apprendre à résoudre le cube sans les yeux !
3) les méthodes "classiques" (débutant, intermédiaire et méthodes de speed et de FM) : l’intérêt ici c'est surtout de pouvoir comparer les méthodes dans une optique de speed ou de FM.

À mon avis le plus important dans cette histoire c'est de bien modéliser le cube. Depuis Cube Explorer, on distingue trois niveaux de modélisation (stickers, permutations/orientations, coordonnées) et l'essentiel du code (de Cube Explorer) est consacré aux fonctions de base sur ces modélisations (appliquer un mouvement, composer, inverser) et au passage d'une modélisation à l'autre ; la résolution en tant que telle étant assez facile une fois qu'on a poussé la modélisation assez loin.

Après tout dépend de ce que vous voulez faire, si vous voulez afficher le cube ou permettre à l'utilisateur de rentrer un cube étiquette par étiquette vous n'échapperez pas au niveau stiker ; sinon vous pouvez rester en permutations/orientations.

Je vais détailler un peu mais Kociemba fait plus complet sur son site ; en particulier il donne tous les algos :

Niveaux de modélisation.

1) Niveau sticker (facelet level, http://kociemba.org/math/faceletlevel.htm" onclick="window.open(this.href);return false;)
Le cube est donné par la liste des couleurs des 48 étiquettes (54 si vous comptez les centres). Pour pas trop se faire chier à l'affichage, je vous conseille de prendre une liste de listes de listes de couleur.
Une couleur est un entier entre 1 et 6.
L'étiquette placée en (x, y) de la face de couleur c du cube C est donnée par C[c][x][y].
Ce niveau sert à afficher et entrer le cube donc a priori pas besoin de coder d'opérations compliquées. La composition par les mouvements de base à la limite si vous voulez que l'utilisateur puisse manipuler le cube.

2) Niveau permutations/orientations (cubie level, http://kociemba.org/math/cubielevel.htm" onclick="window.open(this.href);return false;)
Plus intelligent, on représente le cube pièce par pièce.
Les arêtes sont numérotées de 1 à 12, les coins sont numérotés de 1 à 8. Le cube est donné par la liste des arêtes (12 éléments de valeur entre 1 et 12), la liste des coins (8 éléments de valeur entre 1 et 8), la liste des orientations des arêtes (12 éléments de valeur entre 1 et 2) et la liste des orientations des coins (8 éléments de valeur entre 1 et 3).
Ce niveau permet de faire tout ce qu'on veut (composition, inversion, symétries) assez facilement.
Une variante possible est de regarder non pas des permutations de pièces mais des cycles de stikers. C'est intéressant pour les méthodes de blind (old Pochmann et 3-cycles entre autres) mais plus difficile à manipuler.

3) Niveau coordonnées (coordinate level, http://kociemba.org/math/coordlevel.htm" onclick="window.open(this.href);return false;)
On commence par numéroter les 18 mouvements de base (U, U', U2, D, D', D2, R, R', R2, L, L', L2, F, F', F2, B, B', B2).
C'est la même chose que le niveau précédent sauf qu'on remplace les quatre listes par quatre entiers en numérotant toutes les permutations et orientations possibles. Ça permet de créer des gros tableaux qui servent à effectuer rapidement des mouvements (qu'on appelle des tables de mouvements parce qu'on a plein d'imagination). Par exemple pour la permutation des coins, on peut créer un tableau T à 8! lignes et 18 colonnes qui se lit comme suit : de la position p, si j'applique le mouvement de base numéro n, je passe à la position T[p, n]. L'intérêt c'est que c'est beaucoup plus rapide d'aller chercher le contenu de la case T[p, n] que de calculer la composée de p et de n au niveau permutations/orientations ; en échange ça occupe de la mémoire.


Résolution (méthode Thistlethwaite) :
J'espère que vous savez déjà en quoi ça consiste parce que sinon vous allez avoir du mal à comprendre :-D .
La méthode Thistlethwaite procède par une succession de réductions à des sous-groupes. On part du groupe du cube tout entier et on termine par le groupe trivial qui ne contient que le cube résolu. La méthode repose sur le fait que les différents groupes par lesquels on passe sont caractérisables à la fois de l'intérieur (en donnant la liste des mouvements de base qui les génère) et de l'extérieur (en termes de permutations et d'orientations). On travaille au niveau coordonnées, et on fabrique une liste qui à chaque cas possible associe le coup à faire pour se rapprocher de la solution. Cette liste est remplie par un parcours en largeur en partant du cas résolu.

PS :
- "arête" avec un seul r
- évitez le terme "base de donnée" qui est un peu trop spécifique
"Singmaster has heard of solutions in 2 minutes, but I find this difficult to believe."
Leakim

Re: Modélisation informatique du cube (Mapple)

Message par Leakim »

Bonjour,
Je ne comprends pas bien la définition de l'orientation d'une arête.
Pouvez-vous m'éclairer ?
Merci
Répondre