[PYTHON] Schreiben Sie ein Programm, um den 4x4x4 Rubik Cube zu lösen! 1. Übersicht

Was ist dieser Artikel?

Ich mache gerade einen Roboter, der 4x4x4 Rubik Cube (Rubik Revenge) löst und einen Weltrekord anstrebt. Die größte Hürde bei der Herstellung eines Roboters bestand darin, einen Algorithmus zu implementieren, um einen 4x4x4-Würfel in einer realistischen Zeit und mit so wenigen Schritten wie möglich zu lösen. Wenn Sie nachschlagen, werden Sie feststellen, dass es nur wenige Dokumente und Vorfahren zu 4x4x4 gibt. Ich schreibe diesen Artikel in der Hoffnung, dass er eines dieser wertvollen Materialien sein wird. GitHub ist hier ** Der Inhalt dieses Artikels ist nicht vollständig. Es kann einige Ineffizienzen enthalten. Ich werde es nach Bedarf hinzufügen, wenn es in Zukunft verbessert wird. ** ** **

↓ 4x4x4 Rubik Cube für den Wettbewerb und 4x4x4 Rubik Cube für den Wettbewerb, nummeriert für die Programmproduktion

Das ganze Bild

Diese Artikelsammlung besteht aus insgesamt drei Artikeln.

1. Übersicht (dieser Artikel)
2. Algorithmus
3. Implementierung

Worüber in diesem Artikel gesprochen werden soll

In diesem Artikel werde ich das Wissen einführen, das zum Schreiben eines Programms zum Lösen eines 4x4x4-Rubikwürfels (unter Verwendung eines Suchalgorithmus) erforderlich ist, und kurz über den Programmfluss sprechen.

Referenzmaterial

Ich werde die Referenzmaterialien in der Reihenfolge vorstellen, in der ich sie hilfreich finde.

• 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

Die erste Quelle ist das einzige Papier, das ich über 4x4x4-Würfel gefunden habe. Das zweite ist ein Repository, das tatsächlich mit Java ähnlich wie in einem Papier implementiert wurde. Dies wurde auch als einziges Implementierungsbeispiel gefunden. Der dritte ist ein Beitrag des Eigentümers des zweiten Repositorys. Der vierte ist ein mysteriöser Beitrag, der vorerst gefunden wurde.

Kenntnisse erforderlich, um diesen Artikel zu lesen

Hier ist, was Sie wissen müssen, um diesen Artikel zu lesen und wie Sie ihn erhalten.

Rotationssymbol

Ein Symbol, das die Drehung des Zauberwürfels objektiv und genau darstellt. Wir empfehlen hier als Referenz. Dies ist eine Beschreibung des Rotationssymbols für 3x3x3, aber 4x4x4 verwendet genau das gleiche Symbol.

Gesichtsname

Das im Rotationssymbol angezeigte `` `R, L, U, D, F, B``` wird auch als Name des Gesichts verwendet. Zum Beispiel ist die F-Seite die Vorderseite.

Teilname

Es gibt drei Arten von Teilen an der Außenseite des 4x4x4 Rubik Cube. Wie im Bild gezeigt. Es gibt 3 Aufkleber an den Ecken, 2 an den Kanten und 1 in der Mitte.

Darstellung der Position von Teilen

Verwenden Sie für die Position der Teile das `` `R, L, U, D, F, B```, das erneut mit dem Rotationssymbol angezeigt wird. Da der Ausdruck für Kanten und Ecken unterschiedlich ist, werde ich sie separat einführen.

Kante

Die Kante ist natürlich, überspannt jedoch immer zwei Seiten. Daher werden die Kanten nebeneinander dargestellt, indem zwei Flächen genommen werden, die sich von "R, L, U, D, F, B" erstrecken. Beispielsweise ist die UF-Kante die Kante, die die U- und F-Ebene überspannt.

Ecke

Die Ecke erstreckt sich immer über drei Seiten. Daher werden drei Gesichter, die sich von "R, L, U, D, F, B" erstrecken, nebeneinander aufgenommen und angezeigt. Beispielsweise ist die UFR-Ecke eine Ecke, die sich über die U-, F- und R-Seiten erstreckt.

Parität

4x4x4 Rubinwürfel haben eine einzigartige Bedingung, die als "Parität" bezeichnet wird. Es gibt zwei Arten von Parität, aber die Erklärung von hier ist leicht zu verstehen. Darüber hinaus ist die Erklärung der PLL-Parität an dieser Stelle etwas schwer zu verstehen, kurz gesagt handelt es sich jedoch um einen Zustand des 2-Punkt-Austauschs nur von Kanten (ein 2-Punkt-Austausch ist mit einem 3x3x3-Rubinwürfel nicht möglich). Ein Beispiel für OLL-Parität und PLL-Parität ist in der Abbildung dargestellt. Die linke ist die OLL-Parität und die rechte ist die PLL-Parität. Alle unsichtbaren Seiten sind vollständig.

CP, CO, EP, EO Beziehungsweise

• Eckpermutation
• Eckausrichtung
• Kantenpermutation
• Kantenausrichtung

Das ist. Jedes Teil, aus dem ein 4x4x4-Würfel besteht, kann durch die Position und Ausrichtung der Kanten und Ecken sowie die Position der Mitte eindeutig dargestellt werden.

Basisalgorithmus

Das Lösen eines 4x4x4-Rubikwürfels durch Erkundung ist nicht so einfach. Auf jeden Fall ist der zu durchsuchende Baum (der Begriff und das Grundwissen dazu sind im Artikel [hier] zusammengefasst (https://qiita.com/Nyanyan_Cube/items/60f3699db96dba4a4bf5)) zu groß. Daher wird häufig ein Algorithmus verwendet. Alle Materialien, die ich vorgestellt und implementiert habe, basieren auf einem Algorithmus namens ** Tsais Algorithmus **. Lassen Sie uns den Ablauf erklären. Wenn geschrieben steht, dass "X" -Drehung verwendet wird, beispielsweise in "Zu verwendende Drehung", gibt es zwei Arten von Drehungen, die tatsächlich verwendet werden: "X, X" Und wenn es heißt, `X2``` Rotation zu verwenden, wird tatsächlich nur` X2``` verwendet. Ich denke, es gibt Wörter und Ausdrücke, die ich nicht verstehe. Ich werde jede Phase im nächsten Artikel ausführlich erläutern. Bitte sagen Sie hier "Hmm".

Zusammenfassung

In diesem Artikel gab ich eine kurze Erklärung der Kenntnisse, die zum Schreiben eines Programms zum Lösen eines 4x4x4-Rubinwürfels erforderlich sind, und eine Übersicht über das Lösen eines 4x4x4-Rubikwürfels.