Écrivez un programme pour résoudre le Rubik Cube 4x4x4! 2. Algorithme
Quel est cet article?
Je suis actuellement en train de créer un robot qui résout le Rubik Cube 4x4x4 (Rubik Revenge) et vise un record du monde. Le plus gros obstacle dans la fabrication d'un robot était de mettre en œuvre un algorithme pour résoudre un cube 4x4x4 dans un temps réaliste et avec le moins d'étapes possible. Si vous le recherchez, vous constaterez qu'il existe peu de documents et d'ancêtres sur le 4x4x4. J'écris cet article en espérant que ce sera l'un de ces matériaux précieux. GitHub est ici ** Le contenu de cet article n'est pas complet. Il peut contenir certaines inefficacités. Je l'ajouterai au besoin s'il est amélioré à l'avenir. ** **
↓ Rubik Cube 4x4x4 pour la compétition et Rubik Cube 4x4x4 pour la compétition numéroté pour la production du programme
L'image entière
Cette collection d'articles se compose de trois articles au total.
- Présentation
- Algorithme (cet article)
- Mise en œuvre
De quoi parler dans cet article
Dans cet article, j'expliquerai en détail l'algorithme de Tsai dont j'ai parlé dans l'article précédent.
Brouillage réel
Dans un souci de clarté, cet article utilisera de vrais brouillages. Le brouillage utilisé (le côté blanc est le côté U, le côté vert est le côté F),
r2 b2 f2 d2 r2 b2 d f2 d' f2 d b' f' d' f2 r u f2 l d' rw2 fw2 u r' u' d2 fw2 f2 l uw2 d' l u2 fw' r uw2 u2 b l uw' d' rw uw2 b rw r
est. Si vous avez un cube rubic 4x4x4, veuillez le lire en le tournant. L'état du cube est comme indiqué sur la photo. Lorsque vous voyez une image de cubes alignés, considérez-la comme l'orientation de cette photo.
Phase 0
Dans la phase 0, vous procédez comme suit:
** Amenez toutes les parties centrales du côté R et du côté G du côté R ou du côté L **
À titre d'exemple, dans le brouillage précédent, suivez les étapes ci-dessous.
rw l' uw r' rw d fw
L'état après le virage est comme indiqué sur la photo.
Vous pouvez voir qu'il n'y a que du rouge ou de l'orange dans les quatre parties centrales des côtés R et L. C'est ce que nous visons cette fois.
À l'état terminé, les parties rouges et orange seront rassemblées respectivement sur le côté R et le côté L (en fonction de l'orientation, bien sûr, pour plus de commodité, le blanc est le côté U et le vert est le côté F).
Dans cette phase, il n'y a aucune restriction sur la rotation utilisée et vous pouvez la faire pivoter librement. Les rotations utilisées sont les suivantes (tous types de rotations).
r, r2, rw, rw2, l, l2, u, u2, uw, uw2, d, d2, f, f2, fw, fw2, b, b2
La phase 1
Dans la phase 1, vous effectuez les opérations suivantes:
** 1. Amenez toutes les parties centrales du côté F et du côté B du côté F ou du côté B **
** 2. Bord haut et bord bas séparés **
** 3. Faites de l'état central des côtés R et L l'un des 12 états qui peuvent être traités à l'avenir **
** 4. Éliminer la parité OLL **
Il y a beaucoup de. Utilisons l'exemple de brouillage pour le moment. La procédure est la suivante. Tournez cette étape une fois la phase 0 terminée.
l2 d2 f rw f2 r2 b2 rw
À première vue, je pense que les centres du côté F et du côté B, ainsi que du côté U et du côté D sont regroupés de la même manière que dans la phase 0. C'est le premier objectif à atteindre.
Deuxièmement, les bords hauts et bas peuvent être un peu déroutants. C'est une descente, mais si cela ressemble à l'image, associez (collez) ces deux bords sans utiliser la rotation de 90 degrés de la couche interne (Uw, Rw, Fw). État) Impossible. Dans les opérations futures, nous limiterons l'utilisation de la rotation à 180 degrés uniquement pour la rotation de la couche interne, nous allons donc la rendre dans un état où elle peut être résolue même si cela se produit.
Maintenant, dans l'image, les bords avec la même paire de couleurs sont du même côté et dans la rangée. C'est une mauvaise situation. Je veux éviter cette situation.
La troisième est la restriction selon laquelle la rotation de R, L '' ne sera pas utilisée à l'avenir (c'est-à-dire qu'elle sera tournée de 180 degrés lors de la rotation de la surface R ou L). Si vous n'utilisez pas les deux types de rotation, R, L '', en bref, le centre peut avoir un motif en damier comme indiqué sur l'image, ou une seule couleur face à face peut être mélangée. Je ne peux pas m'aligner. Évitez cette situation.
Le quatrième est l'évitement de la parité OLL, qui est un phénomène propre au 4x4x4. Afin d'éliminer la parité OLL, il est essentiel de tourner la couche intérieure de 90 degrés. Par conséquent, la parité OLL est évitée à ce stade. Plus précisément, le nombre d'EO inversés (Orientation des bords) est compté, et s'il est impair, il est jugé qu'il y a parité OLL, et s'il est pair, il est jugé qu'il n'y en a pas.
La rotation utilisée dans la phase 1 est la suivante.
r, r2, rw, rw2, l, l2, u, u2, uw2, d, d2, f, f2, fw2, b, b2
Phase 2
Dans la phase 2, vous effectuez les opérations suivantes:
** 1.Faites une "rangée" au centre du côté (côté `` F, R, B, L '') **
** 2. Associez les bords situés sur les côtés **
Dans l'exemple de brouillage, suivez les étapes ci-dessous.
d l2 uw2 rw2 d f' uw2 b
Le premier objectif est la contrainte de ne pas utiliser la rotation `` F, F '' '' dans le futur. Faites le motif du centre latéral aligné ou verticalement de la même couleur.
Le deuxième objectif est simplement de coupler les bords situés sur le côté (bords `FR, BR, BL, FL ''). Si vous regardez l'image, vous pouvez voir que les bords à cette position sont alignés.
La rotation utilisée dans la phase 2 est la suivante.
r2, rw2, l2, u, u2, uw2, d, d2, f, f2, fw2, b, b2
Phase 3
Dans la phase 3, vous procédez comme suit:
** 1. Complétez 6 centres **
** 2. Associez les bords restants **
** 3. Éliminer la parité PLL **
Dans l'exemple de brouillage, suivez les étapes ci-dessous.
l2 u l2 u rw2 d fw2 l2 u b2 rw2
En un coup d'œil, vous pouvez voir que le puzzle est "3x3". Ceci est appelé «réduction» dans la terminologie Speed Cube.
Premièrement, le centre est terminé.
Deuxièmement, tous les appariements d'arêtes sont effectués.
Le troisième n'est pas évident à première vue. L'état de parité PLL, qui est un échange d'arêtes en deux points, ne peut pas être résolu sans tourner la couche interne. À l'avenir, nous organiserons les énigmes uniquement en tournant la couche externe, de sorte que la parité PLL sera éliminée.
La rotation utilisée dans la phase 3 est la suivante.
r2, rw2, l2, u, u2, uw2, d, d2, f2, fw2, b2
Phase 4
Dans la phase 4, vous allez:
** 1. Apportez les autocollants qui doivent être sur les côtés U et D du côté U ou D **
** 2. Éliminer l'OE **
Dans l'exemple de brouillage, suivez les étapes ci-dessous.
d l' f' d r' l' u2 f' d r b
En un coup d'œil, vous pouvez voir qu'il n'y a que du blanc (la couleur qui vient finalement du côté U) et du jaune (la couleur qui vient finalement du côté D) sur les côtés U et D. C'est le premier objectif à atteindre.
Le second est l'élimination de l'OE. À partir de maintenant, la phase finale, la phase 5, n'utilisera plus la rotation `` R, L, F, B '' (utilisez toujours une rotation de 180 degrés lors de la rotation de ces faces). L'inversion de bord (EO) ne peut pas être éliminée sans l'utilisation d'une rotation à 90 degrés de deux plans orthogonaux. Par conséquent, EO sera éliminé maintenant.
La rotation utilisée dans la phase 4 est la suivante.
r, l, u, u2, d, d2, f, b
Phase 5
C'est la phase finale. Dans la phase 5, vous terminerez enfin le ** puzzle **.
Dans l'exemple de brouillage, suivez les étapes ci-dessous.
u r2 u l2 u2 l2 b2 u f2 u2 l2 b2 u'
Vous pouvez voir que les énigmes sont terminées.
La rotation utilisée dans la phase 5 est la suivante.
r2, l2, u, u2, d, d2, f2, b2
Résumé
Dans cet article, j'ai présenté un algorithme pour un ordinateur pour résoudre un cube rubic 4x4x4 basé sur l'algorithme de Tsai. Dans le prochain article, je présenterai quelques directives approximatives pour la mise en œuvre concrète de ceci et des conseils sur la mise en œuvre.
Recommended Posts