É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 Image from iOS(15).jpg

L'image entière

Cette collection d'articles se compose de trois articles au total.

  1. Présentation
  2. Algorithme (cet article)
  3. 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. qiita20200810_1.png

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. iOS の画像.jpg

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 Image from iOS(18).jpg

À 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 Image from iOS(19).jpg

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 Image from iOS(20).jpg 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 Image from iOS(21).jpg 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' Image from iOS(22).jpg 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

Écrivez un programme pour résoudre le Rubik Cube 4x4x4! 2. Algorithme
Écrivez un programme pour résoudre le Rubik Cube 4x4x4! 3. Mise en œuvre
Écrivez un programme pour résoudre le Rubik Cube 4x4x4! 1. Vue d'ensemble
Écrivons un programme pour résoudre le Rubik Cube (Partie 2: IDA * Search)
Faisons un robot qui résout le Rubik Cube! 2 Algorithme
Comment créer un programme pour résoudre le Rubik Cube à partir de PC Koshien 2014 Floppy Cube
Ecrire un programme python pour trouver la distance d'édition [python] [distance Levenshtein]
Faisons un robot qui résout le Rubik Cube! 3 Logiciel
Faisons un robot qui résout le Rubik Cube! 1. Vue d'ensemble
Écrivons un programme de simulation simple pour le "problème de Monty Hall"
Ecrire un programme qui abuse du programme et envoie 100 e-mails
Divers commentaires à écrire dans le programme
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (théorie)
Écrivons un programme Python et exécutons-le
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (code Python)
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (résultat de l'exécution)
Comment écrire une interface graphique à l'aide de la commande maya
Je veux écrire en Python! (2) Écrivons un test
J'ai essayé de résoudre Soma Cube avec python
Comment utiliser la bibliothèque de solveurs "kociemba" de Rubik Cube
Trouver une solution au problème N-Queen avec un algorithme génétique (2)
Il est difficile d'écrire un algorithme très simple en php
Essayez de modéliser une distribution multimodale à l'aide de l'algorithme EM
Trouver une solution au problème N-Queen avec un algorithme génétique (1)
Je ne voulais pas écrire la clé AWS dans le programme
Comment démarrer la première projection
J'ai essayé "Implémentation d'un algorithme génétique (GA) en python pour résoudre le problème du voyageur de commerce (TSP)"
Une histoire dans laquelle l'algorithme est arrivé à une conclusion ridicule en essayant de résoudre correctement le problème du voyageur de commerce
Je voulais résoudre le problème ABC164 A ~ D avec Python
Écrivez un script pour calculer la distance avec le système Elasticsearch 5 sans douleur
Modifions le programme informatique Go CgfGoBan pour prendre en charge plusieurs langages de programme
[Python] Un programme qui fait pivoter le contenu de la liste vers la gauche
Écrire la sortie standard dans un fichier
Ecrire des algorithmes A * (A-star) en Python
L'histoire de l'exportation d'un programme
Réfléchissez à la façon d'écrire un filtre avec les versions Shotgun API-Contact
[Python] Un programme qui calcule le nombre de chaussettes jumelées
Le 16ème comment écrire un problème de référence en temps réel hors ligne à résoudre avec Python
Comment réparer la population initiale avec un algorithme génétique utilisant DEAP
[Introduction à Python] Comment écrire une chaîne de caractères avec la fonction format
Le 19ème comment écrire un problème de référence en temps réel hors ligne à résoudre avec Python
J'ai fait un programme pour vérifier la taille d'un fichier avec Python
Activons la caméra et appliquons la mosaïque au visage humain (OpenCV)