[2x2x2] Programmer l'algorithme de Dieu

[Rhapsode]

Bonjour à tous !

Dans le cadre de mes TIPE (sous cet acronyme barbare se cache en fait un vulgaire exposé...), j'aimerais réaliser un programme qui calcule l'algorithme de Dieu pour le 2x2x2. Beaucoup de personnes sur ce site affirment que c'est très simple... Perso, je suis relativement (euphémisme...) nul en info et je trouve ça... pas si trivial que ça...

J'essaye donc de construire un arbre qui liste toutes les positions accessibles du Pocket Cube. On part de l'identité et on applique une des six permutations possibles. Le problème étant de savoir quand on s'arrête... Je ne vois pas d'autre méthode que de comparer, à chaque nœud, l'état du cube avec tous les autres états du cube déjà calculés, afin de savoir quand on doit s'arrêter.

Voilà...! Quelqu'un aurait-il des indications ? Voire un pseudo-code ?

Merci d'avance à quiconque à pris le temps de lire ce post !

P.S. : Je suis censé coder en CamL ou en Maple.

[SqAtx]

Haha visiblement je suis pas le seul à caser "mouvement" dans le titre de mon TIPE sur le cube :p

J'avais pensé à faire un truc un peu comme ça aussi, mais mon aversion pour l'info était vraiment trop forte

Sinon, ça veut rien dire "calculer l'algorithme de Dieu". Ou c'est moi qui comprends rien.

[Rhapsode]

De toutes façons, le jour J, il s'agit de baratiner pour faire croire au jury que notre sujet s'inscrit dans le thème de l'année (ça sent l'expérience de 5/2...) ! Sinon, par "calculer l'algorithme de Dieu", j'entendais "connaître, pour chaque mélange du cube, l'algorithme optimal qui le résout".

[Arsonist]

Un arbre de possibilités, pour les 7^3 * 7! positions possibles?

[WydD]

Si tu veux faire ça de façon la plus bourine possible c'est pas dur.

Représente ton cube de façon interne avec les stickers qui vont bien.
Code les trois opérations RUF et leurs variations (' et 2)

Et à partir de là tu fais une grosse récursivité qui marche tout seul. (note ceci n'est pas un langage qui ressemble à quelque chose.

Code : Tout sélectionner

[entier, chaine] résoudre(profondeur, max, cube, solution) {
   Si profondeur > max alors retourne [profondeur, null];
   Si cube est à l'état résolu alors retourne [profondeur, solution];

   entier minProf = max;
   chaine minSol = null;

   Pour tous les mouvements possibles M (avec variations) {
       nouveauCube = appliquerMouvement(M, cube);
       [profNouveauCube, solNouveauCube] = resoudre(profondeur+1, max, nouveauCube, solution+M);
       Si profNouveauCube < minProf Alors {
            minSol = solNouveauCube;
            minProf = profNouveauCube;
       }
   }
   retourne [minProf, minSol];
}

Pour information, la profondeur max de l'arbre c'est 11 pour le 2x2.
Note que ce genre de truc se code très bien en progra fonctionnelle genre ce que peut faire Caml.

[deadalnix]

Tu n'as pas besoin de stocker les solutions. Tu as juste besoin de la profondeur modulo 3 (ça te permet de savoir si tu va dans le bon sens ou as quand tu résous).

Le plus simple pour l'algo de dieu sur le 2x2x2, c'est tout d'abord de faire une représentation du cube « naturelle » (une permut et une orient) et un système pour passer de cette représentation naturelle à un index. Ensuite, on utilise cette représentation naturelle pour construire une table décrivant les mouvement de base avec les indexes.

Ainsi, on sait que si l'on à la permutation n°XX, et qu'on applique un mouvement, on obtient la permutation n°YY . Ça permet de parcourir le cube extrêmement rapidement.

Puis des parcours en profondeur, en augmentant petit à petit la profondeur max, pour connaître le nombre de coups associé à chaque position, et c'est gagné.

[Rhapsode]

Merci à vous tous ! Ce qui me manquait cruellement, c'est un "index" (tel que deadalnix l'a défini dans son précédent post). Je me demande cependant comment construire la table en question même en disposant d'un index... Cela demanderait de se déplacer dans un arbre :

1) Je mets l'identité à 0,
2) Je traite U(identité), R(identité), etc. et je les mets à 1,
3) Je traite U(U(identité)), U(R(identité)),..., R(U(identité)), R(R(identité)),... etc.

etc.

Mais il y a de plus en plus de cas et les branches se ramifient de proche en proche... Comment traiter cela de manière itérative ? :S

[NikaZ']

J'ai tenté de programmer un calcul du nombre de Dieu... En théorie, il marche, mais en pratique non car la complexité est juste abusée.

pour 0, 1 et 2 moves : 0 sec
pour 3 moves : 0.1 sec
pour 4 moves : 1 sec
pour 5 moves : 14 sec
pour 6 moves : 400 sec

pour 7 moves : Fail, Au bout de 2-3 heures (si je me rappelle bien) un message d'erreur s'affiche.

Je comparerai avec ce qu'à écrit WydD. J'imagine que ça m'aidera.

Je créé toutes les listes possibles et imaginables avec un crédit de n moves. Donc pour n = 2, on a [Id] (en réalité, je contourne ce cas), [R] , [R']... , [R,F] , [R,F'].... Mais je ne créé pas de listes inutiles du type [R,R,R'].

Je les applique toutes sur mon cubes, et je regarde combien de cas ont été générés, les résultats jusqu'à 6 sont ceux publiés sur internet, donc je suis sûr que le programme est correct au moins.

Donc oui ça fait plus de 600 millions de listes pour n = 11 :/. C'est trop pour un PC ?

C'était donc prévisible ?

EDIT 1 (que j'avais pas signalé) :

Un arbre de possibilités, pour les 7^3 * 7! positions possibles?

Ça n'a choqué personne au fait ^^' ? À moins que 343 = 729.
Enfin bref osef de ça.

Ce que j'ai pu lire m'a donné des idées même si j'ai pas bien compris. Mais faire du récursif sur maple, c'est pas possible T_T' ?

EDIT 2 : Je l'ai codé différemment en m'inspirant de ce que j'ai lu (même si j'ai pas tout compris), cette fois-ci, je génère la liste des différents résultats pour n mouvements (qui fera au pire 3 764 160 éléments) et j'applique sur cette liste les 9 mouvements de bases, et je regarde lesquels sont nouveaux. C'est bien plus court à écrire, et c'est je pense un peu plus efficace,
pour n = 1 et 2, t = 0 sec
pour n = 3, t = 0.031 sec
pour n = 4, t = 0.343 sec
pour n = 5, t = 4.774 sec
pour n = 6, t = 105.35 sec
pour n = 7, fail encore... en 1500 sec
J'espère que ce qu'il me manque pour que ça tourne plus vite est ce que je n'ai pas compris...

EDIT 3 : Pour finir, ca tourne en 15h.