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

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
2. Algorithmus (dieser Artikel)
3. Implementierung

Worüber in diesem Artikel gesprochen werden soll

In diesem Artikel werde ich den Tsai-Algorithmus, über den ich im vorherigen Artikel gesprochen habe, ausführlich erläutern.

Tatsächliches Scramble

Aus Gründen der Übersichtlichkeit werden in diesem Artikel echte Verschlüsselungen verwendet. Das verwendete Scramble (weiße Seite ist U-Seite, grüne Seite ist F-Seite),

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

ist. Wenn Sie einen 4x4x4 Rubic Cube haben, lesen Sie ihn bitte beim Drehen. Der Zustand des Würfels ist wie auf dem Foto gezeigt. Wenn Sie ein Bild von Würfeln in einer Reihe sehen, stellen Sie es sich als Ausrichtung dieses Fotos vor.

Phase 0

In Phase 0 gehen Sie wie folgt vor: ** Bringen Sie alle Mittelteile der R-Seite und der L-Seite zur R-Seite oder zur L-Seite ** Führen Sie im vorherigen Scramble beispielsweise die folgenden Schritte aus. rw l' uw r' rw d fw Der Zustand nach dem Wenden ist wie auf dem Foto gezeigt.

Sie können sehen, dass in den vier Zentren auf der R- und L-Seite nur Rot oder Orange vorhanden sind. Das ist es, was wir für diese Zeit anstreben. Im fertigen Zustand werden rote und orangefarbene Teile auf der R-Seite bzw. der L-Seite gesammelt (je nach Ausrichtung ist Weiß der Einfachheit halber natürlich die U-Seite und Grün die F-Seite). In dieser Phase gibt es keine Einschränkungen für die verwendete Drehung, und Sie können sie frei drehen. Die verwendeten Rotationen sind wie folgt (alle Arten von Rotationen). r, r2, rw, rw2, l, l2, u, u2, uw, uw2, d, d2, f, f2, fw, fw2, b, b2

Phase 1

In Phase 1 gehen Sie wie folgt vor: ** 1. Bringen Sie alle Mittelteile der F-Seite und der B-Seite zur F-Seite oder zur B-Seite ** ** 2. Trennen Sie die obere und die untere Kante ** ** 3. Machen Sie den mittleren Zustand der R- und L-Seite zu einem der 12 Zustände, die in Zukunft verarbeitet werden können ** ** 4. OLL-Parität beseitigen ** Es gibt viele. Lassen Sie uns vorerst das Beispiel-Scramble verwenden. Das Verfahren ist wie folgt. Drehen Sie diesen Schritt, nachdem Phase 0 beendet ist. l2 d2 f rw f2 r2 b2 rw

Auf den ersten Blick denke ich, dass die Zentren der F- und B-Seite sowie der U- und D-Seite auf die gleiche Weise wie in Phase 0 erfasst werden. Dies ist das erste Ziel, das erreicht wird. Zweitens können hohe und niedrige Kanten etwas verwirrend sein. Es geht bergab, aber wenn es wie auf dem Bild aussieht, koppeln (kleben) Sie diese beiden Kanten, ohne die 90-Grad-Drehung der inneren Schicht (`Uw, Rw, Fw```) zu verwenden. Zustand) Kann nicht. In zukünftigen Operationen werden wir die Verwendung der 180-Grad-Drehung nur für die Drehung der inneren Schicht einschränken, sodass wir sie in einen Zustand bringen, in dem sie auch dann gelöst werden kann. Im Bild befinden sich die Kanten mit demselben Farbpaar auf derselben Seite und in der Reihe. Das ist eine schlechte Situation. Ich möchte diese Situation vermeiden. Die dritte ist die Einschränkung, dass die Drehung von "R, L" in Zukunft nicht mehr verwendet wird (dh, sie wird beim Drehen der R- oder L-Oberfläche um 180 Grad gedreht). Wenn Sie die beiden Rotationsarten `R, Lnicht verwenden, kann die Mitte ein Schachbrettmuster aufweisen, wie auf dem Foto gezeigt, oder es kann nur eine Farbe von Angesicht zu Angesicht gemischt werden. Ich kann mich nicht ausrichten. Vermeiden Sie diese Situation. Das vierte ist die Vermeidung der OLL-Parität, ein Phänomen, das 4x4x4 eigen ist. Um die OLL-Parität zu beseitigen, muss die innere Schicht unbedingt um 90 Grad gedreht werden. Daher wird an dieser Stelle die OLL-Parität vermieden. Insbesondere wird die Anzahl der invertierten EO (Kantenorientierung) gezählt, und wenn es ungerade ist, wird beurteilt, dass es eine OLL-Parität gibt, und wenn es gerade ist, wird beurteilt, dass es keine gibt. Die in Phase 1 verwendete Rotation ist wie folgt.r, r2, rw, rw2, l, l2, u, u2, uw2, d, d2, f, f2, fw2, b, b2```

Phase 2

In Phase 2 gehen Sie wie folgt vor: ** 1. Machen Sie eine "Reihe" in der Mitte der Seite (`` `F, R, B, LSeite) ** ** 2. Koppeln Sie die Kanten an den Seiten ** Führen Sie im Beispiel-Scramble die folgenden Schritte aus.d l2 uw2 rw2 d f' uw2 b```

Das erste Ziel ist die Einschränkung, in Zukunft keine `F, F''-Rotation mehr zu verwenden. Machen Sie das Muster der Seitenmitte ausgerichtet oder vertikal in derselben Farbe. Das zweite Ziel besteht einfach darin, die seitlich angeordneten Kanten (`FR, BR, BL, FLKanten) zu koppeln. Wenn Sie sich das Bild ansehen, können Sie sehen, dass die Kanten an dieser Position ausgerichtet sind. Die in Phase 2 verwendete Rotation ist wie folgt.r2, rw2, l2, u, u2, uw2, d, d2, f, f2, fw2, b, b2```

Phase 3

In Phase 3 gehen Sie wie folgt vor: ** 1. Schließe 6 Zentren ab ** ** 2. Pair die restlichen Kanten ** ** 3. PLL-Parität beseitigen ** Führen Sie im Beispiel-Scramble die folgenden Schritte aus. l2 u l2 u rw2 d fw2 l2 u b2 rw2 Auf einen Blick sehen Sie, dass das Puzzle "3x3" ist. Dies wird als "Reduzierung" der Speed Cube-Terminologie bezeichnet. Erstens ist das Zentrum fertig. Zweitens ist die gesamte Kantenpaarung abgeschlossen. Der dritte ist auf den ersten Blick nicht ersichtlich. Der Zustand der PLL-Parität, bei dem es sich um einen Zweipunktaustausch von Kanten handelt, kann nicht aufgelöst werden, ohne die innere Schicht zu drehen. In Zukunft werden wir Rätsel nur durch Drehen der äußeren Schicht anordnen, sodass die PLL-Parität beseitigt wird. Die in Phase 3 verwendete Rotation ist wie folgt. r2, rw2, l2, u, u2, uw2, d, d2, f2, fw2, b2

Phase 4

In Phase 4 werden Sie: ** 1. Bringen Sie die Aufkleber, die sich auf der U- und D-Seite befinden sollten, auf die U- oder D-Seite ** ** 2. Eliminiere EO ** Führen Sie im Beispiel-Scramble die folgenden Schritte aus. d l' f' d r' l' u2 f' d r b Auf einen Blick sehen Sie, dass es auf der U- und D-Seite nur Weiß (die Farbe, die schließlich zur U-Seite kommt) und Gelb (die Farbe, die schließlich zur D-Seite kommt) gibt. Dies ist das erste Ziel, das erreicht wird. Das zweite ist die Beseitigung von EO. Von nun an wird in der letzten Phase, Phase 5, keine R-, L-, F-, B-Drehung mehr verwendet (beim Drehen dieser Flächen immer eine Drehung um 180 Grad). Die Kantenumkehr (EO) kann ohne die 90-Grad-Drehung zweier orthogonaler Ebenen nicht beseitigt werden. Daher wird EO jetzt eliminiert. Die in Phase 4 verwendete Rotation ist wie folgt. r, l, u, u2, d, d2, f, b

Phase 5

Dies ist die letzte Phase. In Phase 5 schließen Sie das ** Puzzle ** ab. Führen Sie im Beispiel-Scramble die folgenden Schritte aus. u r2 u l2 u2 l2 b2 u f2 u2 l2 b2 u' Sie können sehen, dass die Rätsel abgeschlossen sind. Die in Phase 5 verwendete Rotation ist wie folgt. r2, l2, u, u2, d, d2, f2, b2

Zusammenfassung

In diesem Artikel habe ich einen Algorithmus für einen Computer vorgestellt, mit dem ein 4x4x4-Rubikwürfel basierend auf Tsais Algorithmus gelöst werden kann. Im nächsten Artikel werde ich einige allgemeine Richtlinien für die tatsächliche Implementierung und Tipps zur Implementierung vorstellen.