Manière de calculer la torsion totale en tétrade d'un cube de rubik
Je travaille sur une implémentation de l'algorithme de Thistlewaite pour résoudre un Rubik's cube et je suis maintenant confronté au problème des torsions de tétrades. Grâce à cette réponse , je comprends ce qu'ils sont et comment ils réduisent la quantité d'états dans la phase 3, mais le problème que j'ai est de trouver un moyen de calculer la torsion totale de la tétrade d'un cube à partir de son état uniquement.
La façon dont j'implémente cet algorithme n'est pas avec une recherche en profondeur et je ne peux donc pas simplement utiliser la condition plus forte trouvée ici et ici pour savoir si j'en ai fini avec l'étape 3 car cela ne m'est pas utile. La façon dont je le fais est que je précalcule les tables de recherche et que je les regarde pour savoir comment résoudre un certain état. Pour cette raison, je dois caractériser complètement les informations nécessaires pour distinguer les différents états de stade 3. J'ai déjà fait des tétrades de coin, des tranches d'arêtes et la parité, la dernière chose dont j'ai besoin est un moyen d'exprimer la torsion de tétrade d'un état (ou toute information équivalente). La meilleure chose serait de pouvoir simplement donner une valeur entre 0, 1 ou 2 et l'utiliser pour décrire la torsion totale.
J'espère que ma question est claire, et si ce n'est pas le cas, n'hésitez pas à poser des questions dans les commentaires, je ferai de mon mieux pour l'expliquer davantage.
Réponses
Il est assez difficile d'extraire ces informations directement des emplacements actuels des pièces d'angle. De loin, le moyen le plus simple est d'essayer de résoudre ces pièces d'angle en utilisant seulement des demi-tours (tout en ignorant les pièces de bord), et de voir jusqu'où vous allez.
Pour l'instant, je suppose que les pièces d'angle sont déjà situées dans leurs orbites tétrades correctes {UFR, UBL, DFL, DBR} et {UFL, UBR, DFR, DBL}. Vous pouvez résoudre les pièces d'une tétrade très facilement, pas plus d'un demi-tour pour chaque pièce, au plus 3 coups au total. Par exemple, résolvez DBR en utilisant au plus un parmi {D2, B2, R2}, puis DFL en utilisant au plus un parmi {F2, L2}, et enfin UBL en utilisant {U2} si nécessaire, ce qui laisse également UFR résolu.
Vous résolvez ensuite un morceau de la deuxième tétrade, par exemple DBL, en utilisant l'une des séquences de mouvements {F2 L2 F2 U2, U2 F2 U2 L2, L2 U2 L2 F2}. Ces séquences de mouvements effectuent un double échange sur les quatre pièces de la deuxième tétrade et sont les seules permutations possibles qui maintiennent la première tétrade fixe.
Cela laisse trois pièces non résolues, {UFL, UBR, DFR}. Ceux-ci peuvent être dans l'une quelconque des 3!=6 permutations. Ces 6 possibilités représentent la torsion de la tétrade en combinaison avec la parité de permutation, donc si vous mappez cette permutation sur un nombre de 0 à 5, vous avez codé à la fois la parité de permutation et la torsion de la tétrade en un seul nombre.
Pour l'algorithme Thistlethwaite, vous souhaiterez probablement coder une position arbitraire de la troisième étape de l'algorithme. Cela doit être fait de manière cohérente, ce qui signifie que si deux positions différentes sont amenées dans la quatrième étape par la même séquence de mouvements (c'est-à-dire qu'après avoir appliqué la séquence de mouvements à ces positions, elles deviennent toutes deux résolubles en utilisant seulement des demi-tours) alors ces deux positions doivent avoir le même encodage pour l'étape 3.
Vraisemblablement, votre programme répertorie les emplacements des coins du cube dans un ordre fixe particulier. Par exemple, vous pouvez avoir un tableau de longueur 8 représentant les emplacements dans l'ordre
UFR , UFL, UBL , UBR, DFR, DFL , DBL, DBR .
J'ai mis en gras les emplacements qui représentent l'une des tétrades, ceux aux indices 0, 2, 5, 7 dans le tableau. Vous avez peut-être choisi une convention de classement différente dans votre programme, mais la méthode est la même.
Supposons que vous ayez maintenant une position de cube arbitraire de niveau 3, une permutation aléatoire de ces 8 coins, par exemple :
UBR, UBL , DBR , DFR, DFL , UFR , UFL, DBL.
Une façon simple et cohérente de séparer les pièces en deux tétrades consiste à séparer littéralement les deux types de pièces sans changer leur ordre relatif :
UBL , DBR , DFL , UFR
UBR, DFR, UFL, DBL.
Et puis placez-les dans la matrice de stockage, dans l'ordre, chacun dans son ensemble correct d'emplacements de tétrade. Ainsi le premier ensemble va dans les indices 0,2,5,7, l'autre dans les indices 1,3,4,6.
UBL , UBR, DBR, DFR, UFL, DFL , DBL, UFR .
Maintenant, vous pouvez appliquer la technique de résolution que j'ai expliquée au début, pour aboutir à un encodage cohérent des positions tetrad twist et parity.
Ce qui précède suppose que vous utilisez une seule manière standardisée de représenter le cube et que vous appliquez des mouvements à cela. Vous pouvez plutôt conserver les deux listes séparées des morceaux de tétrade comme une représentation simplifiée de cette position, et les permuter directement au fur et à mesure que vous la résolvez pour extraire l'encodage twist+parity.
Vous pouvez jeter un coup d'œil à certains des programmes de cet ancien concours de programmation de cubes , bien que je ne sois pas sûr qu'ils seront très utiles car ils sont écrits pour être concis, pas pour être intelligible.