Programme de résolution selon la méthode Fridrich

[sakd0]

Je viens de finir de mettre au point un petit programme qui trouve la solution la plus courte pour un cube en suivant la méthode Fridrich. Le programme teste toutes les possibilités : choix de la face de départ, choix de l'ordre dans lequel on place les arêtes de la croix, choix de l'ordre dans lequel on résoud les 4 paires de f2l, (pas trop de choix pour l'oll et la pll)

si vous avez un mélange à soumettre je vous donne la solution la plus courte après l'avoir rentré dans le programme !

je crois qu'il trouve à peu près tout le temps une solution en 40-41 mouvements

[mickacka]

FU'RU'D2LB'F2D'LRU2D' pour voir?

[sakd0]

petit problème technique avec la méthode fridrich la phase de débug doit pas être complètement terminée, c'est louche d'ailleurs...


EDIT : en fait c'est la rotation du cube pour le passage au LL qui foire un peu, mais voilà la résolution

(le mélange est à faire avec la face blanche sur la face L si on veut commencer par la face blanche, et la solution s'effectue aussi avec la face blanche sur L)
41 mouvements : F2 iR U2 iR B2 R2 F iR iF B iR iB R2 iF iR F iR iF R F iR F R2 iF R2 F iR iF R U iR iU iR iB D B iU iB iD B U
dans ce cas là on a une pll skip


iR=R', iF=F' etc

[sakd0]

petit up pour dire que tout est ok

[Subaruiz]

Petit test :
F' R2 D2 F' D' F' L' U D2 L U2 R2 L F' L D2 L' B D R' B U2 B' U' L'

En tout cas bravo

[sakd0]

Petit test :
F' R2 D2 F' D' F' L' U D2 L U2 R2 L F' L D2 L' B D R' B U2 B' U' L'

après avoir fait le mélange, faire une rotation y du cube : U reste U, mais la face R devient la face F
42 coups ... si on compte les mouvements de tranche centrale comme un mouvement, ce qui n'est pas le cas en FMC ...
iF, R, B2, iL, iF, B2, L, iR, iU, R, U, iB, R2, iB, iR, B, iR, iB, R2, B2, iD, R, D, iR, iF, R, F, B, R, iB, iR, B, R, iB, S2, L, E2, iL, iE, S2, E, iR
on a une oll skip cette fois

S2 = U2 D2 y2
E2 = F2 B2 z2
iE = tranche entre FB qui descend

EDIT : mieux encore, je sais pas pourquoi il me l'a pas sortit tout de suite :

rotation y' après le mélange : 40 coups, indiscutable
iR, U2, R2, B2, F2, L, R, iF, iR, F, iR, B, iR, iB, F, iR, iF, R, B, iR, iB, iR, iD, R, D, iB, R, B, iR, U, R2, iU, R2, U, iR, F, R, iF, iR, iU
oll en 6coups, pll skip, qui dit mieux ?

comme quoi sur chaque cube pratiquement on peut avoir un skip en utilisant Fridrich, il suffit juste de trouver la bonne manière de le résoudre mais aussi ... de commencer par la bonne face !! commencer toujours par la face blanche ça élimine déjà 83% des possibliltés, ça fait qu'il n'en reste plus que 4!x4! = 576

edit : jviens de lancer le programme en lui disant de compter le nombre de skip qu'il trouvait sur l'ensemble des différentes résolutions, et pour le mélange de subaruiz là, il a trouvé 27 skip sur les ~3500 façons de résoudre

[Gprano]

Intéressant comme soft, gg !
Ca prouve qu'avec la fridrich en fmc d'optimisation bourrin on pourrait obtenir des trucs corrects, mais que pour faire du bon fmc il faut avoir de l'intuition en plus

C'est programmé en quoi ? (les sources sont libres ? )

[sakd0]

c'est programmé en Maple ! c'est un langage de programmation scolaire qu'on nous apprend en prépa ... aux oraux des concours on peut nous demander de faire des petits programmes dessus

faudrait que j'arrive à mettre ça sous la forme d'un fichier exécutable comme acube mais j'ai l'impression que c'est impossible

(le programme met quand même 5min avec mon petit 2,4 ghz biproc pour parcourir toutes les sol... je dis pas qu'un homme y arriverait pas en 2h mais ... presque : 3600s = 1h, 3500 solutions possibles, 2h => 2s pour tester une solution )

[mickacka]

programme disponible sur le net pour le telecharger?

[Subaruiz]

Je pense pas , sinon ils nous aurait paser le lien.

En tout cas merci , c'est marrant de le resoudre avec un "algo" . Et puis on apprend des trucs, en voyant comment optimiser larésolution ça instruit.

[sakd0]

il faut avoir maple pour le faire tourner, donc soit 'acheter' maple (=105€ student edition) ou alors se le procurer légalement ( ) et ensuite le programme je l'ai mis à ici :
Cube Explorateur v5.3

une fois que tout ça est fait, là commence les ennuis, il faut comprendre comment ça marche, j'ai rapidement expliquer avec des lignes de commentaires, peut-être que ça suffit.

y'a pas de soucis je suis pour le partage des biens et des richesses !

(si il y a des curieux qui voudrait voir le code source sans avoir maple voilà tout ça en html : Cube Explorateur html (merci maple ça c'est bien foutu au moins) )

[deadalnix]

Quel algo pour resoudre la croix ?

[sakd0]

pour la croix, le prog place les arêtes une par une (4arêtes x 12positions x 2orientations = 96 cas envisagés), sinon ça aurait été beaucoup plus (trop peut-être) compliqué et c'est déjà assez efficace comme ça (le programme globalement)

croix pour FU'RU'D2LB'F2D'LRU2D' (mélange de mickacka)
=> F2 iR U2 iR B2 , 5 moves mais elle était facile

croix pour F' R2 D2 F' D' F' L' U D2 L U2 R2 L F' L D2 L' B D R' B U2 B' U' L' (mélange de subaruiz)
=> y' iR U2 R2 B2 F2 (L) , 6 mouvements (croix de la face B p/r au mélange)

comme il y a 4! façon de faire la croix (suivant l'ordre dans lequel on place les arêtes) et qu'on peut commencé par 6 faces différentes, ça fait 144 croix possibles, ça doit aider à trouver une croix facile

[cyril]

Passionnant. Très joli boulot, je ne pense pas qu'il existe d'autre programme pour tester les limites de la méthode Fridrich. Pour te titiller un peu, voici quelques idées d'optimisation :
- favoriser des suites de mouvements qui se compensent/annulent le dernier mouvement de l'étape précédente(entre deux paires des F2L par exemple)
- tester différentes séquences pour former/insérer les paires coin-arête lors des F2L
- plus plein d'autres conseils que m'avaient donné les pros du FMC quand j'avais développé mon genetic Rubik's Cube solver

D'ailleurs .. petit clin d'oeil, voici son résultat pour le mélange de Subaruiz :

Explication :
2x2x3 : y x y U'LF2U'L2BU'L2U'L2 (10 HTM)
Orientation des arêtes et positionnement des coins pour entrer dans le sous-groupe "2-generator" : U'LFL'F'RUR' (8 HTM)
Fin en 2-gen : F U' F' U2FU'FU2F'UF'U'F2U'F (15 HTM)

Total : 33 HTM. Temps de calcul : environ 1h. Pour mémoire, mon genetic solver ne "connaît" aucune séquence au départ, il les invente toutes en cours de résolution.

[Carugo]

Si j'ai un peu de temps dans les semaines a venir , j'essaye de vous faire ca en C++ , histoire d'avoir un .exe , ca permettrait en plus un resultat plus rapide .
Par contre faudrait savoir si tu utilise des outils mathematiques propres a maple , j'ai aps regarder ton code Sakd0