Programme de résolution selon la méthode Fridrich

[deadalnix]

Pour information ca s'apelle DF-IDA comme algo : recherche en profondeur sur un graphe, avec profondeur variable.

[sakd0]

je sais pas si il y a besoin d'un algo DF-IDA puisque tout est du repérage de cas : si tel cas, tel algo : tel f2l, tel algo, etc, à moins que cela puisse servir à trouver l'algo qui calera la paire de f2l sans mouvements de placement inutiles, et qui improvisera donc à partir de n'importe quel emplacement du coin et de l'arête, mais c'est comme le fait d'incorporer plusieurs oll pour le même cas histoire de voir si l'une donnera un skip ou pas : je trouve que ça s'éloigne trop d'une résolution 'humaine'...

je pensais plus à une résolution qui se rapproche de la méthode que l'on utilise vraiment, avec nos algorithmes, un par cas, nos f2l... peut-être qu'une aide de l'ordi peut-être intéressante pour les x-cross, là où il y a vraiment une part d'improvisation du cubeur.

(va se mettre à regarder de plus près des tutoriaux sur le C++)

[deadalnix]

Imagine les differnte sposition de ton cube comme un graphe. ces position sont reliés par une baterie d'algos. Chaque lien est marqué d'un cout (nombre de mouvmenets).

Tu effectue un parcours en profondeur avec une profondeur limite qui varie sur ce graphe, c'est donc bien de l'df-ida

Sauf que tu n'as "que" 4!*4! possibilités de chemin dans ton graphe; contrairement a une resolution a la cube explorer qui part des mouvements de base comme chemin et non des algos connus.

[sakd0]

c'est chaud parce que tout n'est pas silloné : par exemple pour les f2l je sais pas si t'imagine le bordel mais faut envisagé toutes les éventualités : paire inséré au mauvais endroit, arête ou coin inséré au mauvais endroit, et des fois je demande de faire des R ou des U jusqu'à trouver une pièce intéressante, je veux dire qu'il (le prog) ne vas pas vraiment d'un endroit à un autre en sachant à chaque fois où il va, des fois il 'tatonne' pour se remettre dans une position qu'il connait

enfin vu qu'en pratique je sais pas du tout comment ça se passe (sauf avec mon prog qui ne fonctionnait qu'avec des if et des boucles afin d'envisager toutes les éventualités) faudra qu'on en reparle quand j'aurais mis un peu les pied dans le C++.

(pour info le cube est numérisé par une liste d'entier : les 24 premiers entier correspond à "n°i de l'arête se trouve en position n°j ; suivi de son orientation (0 ou 1)", puis pareil pour les coins : 16 entiers sous la forme "coins i en position j, orientation du coin i (compris entre 1 et 3)", d'où un cube résolu qui ressemble à : [1,1,2,1,3,1,4,1,...11,1,12,1,1,1,2,1,3,4,1,...,7,1,8,1] )

sinon c'est pas tout à fait vrai ce que tu dis pour les chemins, il n'y a que "6x4!x4!" chemins à parcourir, mais il y a bien plus de possiblités, par exemple pour la croix il y a 125,000 possiblités de croix, et le prog repère 96 cas élémentaires, il faut donc improviser un peu pour se ramener plusieurs fois sur l'un des 96cas connus (pour les f2l c'est 2 ou 3 millions de possibilités et seulement 100cas/algos reconnus par le prog, d'ailleurs le sousprog qui résoud les f2l j'ai eu du mal à en venir à bout, il était vraiment monstrueux, je met au défi quelqu'un d'en comprendre 3 lignes complètes qui se suivent ! => Prog F2L )

[Carugo]

F2L1:=proc(A,affichage)
local i,j,j1,j2,m,ok,Liste1,Liste2,a,b0,c1,c2,p,AF2LLL,Aalgo;
Aalgo:=[];ok:=0;

Easy

[DJ Xav]

Hello les amis,

désolé pour le déterrage, mais ce sujet m'a beaucoup intéressé vu que je suis en cours de développement d'un soft de résolution . J'ai trouvé plusieurs sujets sur le développement de logiciels de résolution sur le forum: ne serait-il pas possible de créer une rubrique "coins des softeux"?

Je n'en suis qu'au début puisque mon soft ne résout que la croix blanche à ce jour. Mais rien que pour la croix on peut soit faire le boeuf (ce qui est mon cas pour l'instant) et résoudre les arêtes une par une en se donnant la contrainte maximale dès la première arête (c a d ne modifier aucune autre arête) soit essayer d'être un peu plus subtil (augmenter les contraintes au fur et à mesure que les arêtes sont résolues), mais du coup au lieu d'utiliser une bibliothèque de 24 algos (12 positions de l'arête cible *2 orientations possibles) on se retrouve avec 2 voire 3 bibliothèques. De plus j'aimerais trouver plus subtil que de les résoudre une par une, même si on peut multiplier les cas pour trouver le meilleur.

En attendant de trouver une idée astucieuse pour les arêtes je vais continuer avec les F2L, ce qui devrait déjà m'occuper quelques heures...

Bonne journée,
DJ Xav

[Akala]

Tu veux impérativement créer un soft qui résout en fridrich ?
Parce que si non, je pense qu'une méthode à base de cycles sera peut être plus facile à implémenter.

[DJ Xav]

Bonjour Akala,

je n'ai en effet pas d'obligation d'utiliser Fridrich dans mon programme. Mais puisque je cube avec cette méthode, autant la programmer.

J'ai l'intention de programmer une des méthodes de blind à cycles ensuite comme tu le proposes. Mais j'ai aussi envie de tenter un Megaminx, voire un Tuttminx. L'idée serait d'avoir un programme le plus universel possible. Un tel programme pourrait aussi générer de nouveaux algos.

Bonne journée,
DJ Xav

[DJ Xav]

Hello les amis,

quelques nouvelles de mon soft:
il est opérationnel mais ne résoud que le 3x3x3 et seulement avec la méthode Fridrich
croix blanche arête par arête dans un ordre fixe
F2L avec set-up du coin et de l'arête cibles dans des positions fixes. Du coup il n'y a que 6 F2L utilisées (3 orientations du coin x 2 orientations de l'arête). Il y a moyen de faire mieux mais c'est beaucoup de travail pas très fun.
Full OLL (57) avec adaptation en U / U2 / U' et traduction automatique des algos pour éviter des U inutiles (j'en serais moi-même incapable)
Full PLL (21) avec les mêmes traductions en U / U2 / U' que pour les OLL

Je travaille actuellement sur un programme beaucoup plus universel qui pourrait gérer des cubes de toutes tailles, mais aussi des tétraèdres, des dodécaèdres et si possible les icosaèdres tronqués. Pour cela j'ai adopté une nouvelle strucutre de données:
l'élément de base est un tableau 1D de stickers dont l'indice 0 est un "coin"
je rassemble ensuite ces "arêtes internes" dans un tableau (donc 2D) qui est une couronne de largeur 1 autour d'un centre (ou le centre lui-même pour l'indice 0).
Je rassemble ces couches dans un tableau qui représente donc une face.
Ces faces forment enfin un dernier tableau de dimension 4: le polyèdre à résoudre.

Vient ensuite la façon de décrire le polyèdre. L'information importante est le lien entre les faces (via les arêtes). Pour chaque face j'indique donc quelles sont les faces qui y sont reliées et avec quelle orientation (il faut bien une arête d'indice 0 pour chaque face: l'arête d'indice 0 d'une face peut être reliée à une arête d'indice 0 ou 1 ou autre d'une autre face).

Cela sera suffisant pour définir un mouvement de tranche mais me semble un peu court pour les mouvements du polyèdre entier (x y et z pour le cube). Sur un dodécaèdre (comme le Megaminx pour le plus simple d'entre eux) il faut au moins que j'indique au programme quelles sont les faces opposées. Ensuite comme les 10 autres faces ont au moins une arête commune avec une des deux faces opposées traversées par l'axe de rotation je peux me débrouiller. Par contre pour l'icosaèdre tronqué (tuttminx) certaines faces ne sont attachées à aucune des deux faces opposées. Il me faudra donc une information supplémentaire pour chaque rotation (surtout qu'il y en a 32 ).

Pour finir j'ai déjà converti l'ensemble de la notation 3x3x3 en mouvements R, x, y et z afin de rendre l'adaptation à tout polyèdre plus facile.

Au final les briques élémentaires seront:
1 mouvement pour chaque axe (par exemple x y et z pour un 3x3x3)
1 mouvement pour chaque tranche externe (par exemple R pour un 3x3x3, MR et R pour un 5x5x5)

Bonne journée,
DJ Xav

[DJ Xav]

Bonjour les amis,

quelques nouvelles de mon soft universel:
* pour l'instant je ne le teste que sur le 3x3x3
* les 2 premières couches sont codées. Je suis en cours de codage des 57 OLL. Pour cela j'utilise un tableau de dimension 6 (pour rappel mon polyèdre est un tableau de dimension 4). Je crée un "cube masque" avec les facettes jaunes et non jaunes. Je rajoute une dimension pour les 4 rotations possibles de ce cube masque en y/y' et bien sûr une 6ème dimension pour les 57 OLL.
* pour les PLL je compte créer un tableau de la dernière layer qui à chaque pièce associe un nombre de quarts de tours U/U' par rapport à la position finale. Ce tableau devrait me permettre de repérer les 21 cas avec chacune des 4 orientations possibles. Au lieu d'un indice de couleur c'est donc un nombre entier qui est stocké mais j'aboutirai de la même façon à un tableau de dimension 6.

L'avantage de cette stratégie pour les OLL et PLL est qu'elle est applicable à tous les cubes: les gros cubes ou le megaminx, le gigaminx... Je ne sais pas encore si je tiendrai des tableaux distincts pour les cubes et les dodécaèdres ou si je ferai entrer le tout dans la 7ème dimension.

N'hésitez pas si vous avez des conseils / commentaires.

Bonne journée,
DJ Xav

[TMOY]

Euh, pourquoi "universel" ? Pour le moment au moins, tu ne résous que le 3^3 et uniquement avec Fridrich, ça ne me paraît pas très universel tout ça...

[DJ Xav]

Euh, pourquoi "universel" ? Pour le moment au moins, tu ne résous que le 3^3 et uniquement avec Fridrich, ça ne me paraît pas très universel tout ça...

Bonjour TMOY,

merci d'avoir lu mon post

Il faut bien commencer par quelque chose. Tu m'accorderas qu'il est plus facile de résoudre un 3x3x3 q'un Gigaminx pour mettre au point un soft. J'utilise la méthode de résolution que je connais, c'est-à-dire Fridrich.

Ce qui est universel dans mon programme:
* la structure de données (dans la limite des polyèdres réguliers et dérivés, mais ça couvre une grande partie des puzzles existants)
* les mouvements (puisque définis par 4 paramètres: le type: tranche externe, tranche interne ou polyèdre entier; le numéro de l'axe; le sens de rotation (horaire ou trigonométrique) et le nombre de rotations élémentaires
* l'algorithme de résolution est bien sûr configurable à l'infini, on peut très bien imaginer choisir son algo avant de lancer la résolution

Je t'accorde que mon programme n'est pas universel mais soutiens qu'il est "potentiellement un peu universel"

Bonne journée,
DJ Xav

[Philfully]

Pour faire une méthode totalement universelle quelle que soit la taille du cube, je pencherais pour une méthode n'utilisant que des commutateurs. C'est facile à généraliser. par contre, en terme de temps de résolution, ce n'est clairement pas optimisé. Mais au moins ce serait universel ^^

[TMOY]

Il ne faut pas oublier les parités, qui ne peuvent pas se résoudre avec des commutateurs. Mais bon, ça ne change pas fondamentalement les choses non plus.

[DJ Xav]

Pour faire une méthode totalement universelle quelle que soit la taille du cube, je pencherais pour une méthode n'utilisant que des commutateurs.

Bonjour Philfully,

pour les cubes comme pour d'autres choses d'ailleurs ce n'est pas la taille qui compte

La méthode Hardwick de résolution des gros cubes en passant par des barres me semble assez facilement codable avec des boucles et donc de façon générique (puisque le terme universel ne plaît pas à TMOY). Et de toutes façons pour finir les derniers centres j'utiliserai les 3-cycles habituels, de même pour les arêtes (à part pour les parités comme judicieusement rappelé par TMOY).

Je pense que quand mon programme saura résoudre le Gigaminx je serai proche de mon objectif initial (s'il sait aussi résoudre les NxNxN, le Pyraminx et le Megaminx bien sûr).

Bonne journée,
DJ Xav