[PYTHON] Écrivez un programme pour résoudre le Rubik Cube 4x4x4! 1. Vue d'ensemble

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.

1. Aperçu (cet article)
2. Algorithme
3. Mise en œuvre

De quoi parler dans cet article

Dans cet article, je présenterai les connaissances nécessaires pour écrire un programme pour résoudre un cube rubic 4x4x4 (à l'aide d'un algorithme de recherche), et parlerai brièvement du déroulement du programme.

Matériel de référence

Je présenterai les documents de référence dans l'ordre dans lequel je les trouve utiles.

• https://arxiv.org/abs/1601.05744
• https://github.com/cs0x7f/TPR-4x4x4-Solver
• http://cubezzz.dyndns.org/drupal/?q=node/view/525
• http://cubezzz.dyndns.org/drupal/?q=node/view/73

La première source est le seul article que j'ai trouvé sur les cubes 4x4x4. Le second est un référentiel qui a en fait été implémenté à l'aide de Java d'une manière similaire à un article. Cela a également été trouvé comme le seul exemple de mise en œuvre. Le troisième est un message du propriétaire du deuxième référentiel. Le quatrième est un post mystérieux qui a été trouvé pour le moment.

Connaissances requises pour lire cet article

Voici ce que vous devez savoir pour lire cet article et comment l'obtenir.

Symbole de rotation

Un symbole qui représente objectivement et précisément la rotation du Rubik Cube. Nous recommandons ici comme référence. Ceci est une description du symbole de rotation pour 3x3x3, mais 4x4x4 utilise exactement le même symbole.

Nom du visage

Le R, L, U, D, F, B '' qui apparaît dans le symbole de rotation est également utilisé comme nom de la face. Par exemple, la face F est la face avant.

Nom de la pièce

Il existe trois types de pièces à l'extérieur du Rubik Cube 4x4x4. Comme le montre l'image. Il y a 3 autocollants sur les coins, 2 sur les bords et 1 au centre.

Comment représenter la position des pièces

Pour la position des pièces, utilisez le R, L, U, D, F, B '' qui apparaît à nouveau avec le symbole de rotation. Puisque l'expression est différente pour les bords et les coins, je les présenterai séparément.

Bord

Le bord est naturel, mais il chevauche toujours deux côtés. Par conséquent, les arêtes sont représentées côte à côte en prenant deux faces qui chevauchent `` R, L, U, D, F, B ''. Par exemple, l'arête UF est l'arête qui chevauche les plans U et F.

coin

Le coin chevauche toujours trois côtés. Par conséquent, trois faces qui chevauchent `` R, L, U, D, F, B '' sont prises et affichées côte à côte. Par exemple, le coin UFR est un coin qui chevauche les côtés U, F et R.

parité

Les cubes rubis 4x4x4 ont une condition unique appelée "parité". Il existe deux types de parité, mais l'explication de ici est facile à comprendre. De plus, l'explication de la parité PLL est un peu difficile à comprendre sur ce site, mais en bref, elle est à l'état d'échange de 2 points uniquement d'arêtes (l'échange de 2 points n'est pas possible avec un cube rubic 3x3x3). Un exemple de parité OLL et de parité PLL est illustré dans la figure. La gauche est la parité OLL et la droite est la parité PLL. Tous les côtés invisibles sont complets.

CP, CO, EP, EO Chaque

• Permutation de coin
• Orientation des coins
• Permutation des bords
• Orientation du bord

C'est. Chaque partie qui constitue un cube 4x4x4 peut être représentée de manière unique par la position et l'orientation des bords et des coins, et la position du centre.

Algorithme de base

Résoudre un cube rubic 4x4x4 par exploration n'est pas si simple. Quoi qu'il en soit, l'arbre à rechercher (le terme et les connaissances de base en la matière sont résumés dans l'article ici) est trop grand. Par conséquent, un algorithme est souvent utilisé. Le matériel présenté et mon implémentation sont tous basés sur un algorithme appelé ** Algorithme de Tsai **. Expliquons le flux. De plus, s'il est écrit que la rotation " X``` est utilisée, par exemple, dans "Rotation à utiliser", il existe deux types de rotations qui sont effectivement utilisées: " X, X''. Et s'il dit d'utiliser la rotation X2 '', seul `` X2 '' est réellement utilisé. Je pense qu'il y a des mots et des expressions que je ne comprends pas. J'expliquerai chaque phase en détail dans le prochain article, alors dites "Hmm" ici.

Résumé

Dans cet article, j'ai donné une brève explication des connaissances nécessaires pour écrire un programme pour résoudre un cube rubic 4x4x4 et un aperçu de la façon de résoudre un cube rubic 4x4x4.