Verwendete Python und eine zweiseitige Breitensuche, um einen 2x2 Zauberwürfel zu lösen.
Inspiriert durch Projekt in MIT 6.006. Einzigartig von Grund auf neu erstellt.
https://youtu.be/ZHxLO6fubaU
Erstellte die Cube-API, den Algorithmus und die GUI von Grund auf. Jede der 6 Seiten hat 4 verschiedene Quadrate, was 24 Quadrate ergibt. Darüber hinaus besteht der Würfel aus insgesamt 8 Eckstücken, die jeweils 3 Ausrichtungen haben und somit zu den 24 Quadraten passen.
Ich habe jeden der 24 Unterabschnitte jeder Seite als Zeichenfolge mit „xyz“ als Format definiert, wobei x die Farbe ist, die direkt gegenüberliegt und y und z im Uhrzeigersinn um den Würfel für diese Ecke verlaufen.
Ich ging um den Würfel herum und ordnete jeder Seite eine feste Zahl zu, die den gelösten Zustand darstellt. Beispielsweise sind 0, 1, 2, 3 die 4 Teile der nach vorne gerichteten weißen Seite, wobei 0 oben links ist und die anderen im Uhrzeigersinn angeordnet sind.
Es gibt 12 Bewegungen, die auf dem Würfel ausgeführt werden können. Rechts, links, oben, unten, vorne, hinten. Jedes davon hat auch seine Bewegungen gegen den Uhrzeigersinn, also 6x2 = 12 Bewegungen. Jede dieser 12 manipuliert die Hälfte des Würfels, also 12 Quadrate. Um diese Bewegungen auszuführen, habe ich Wörterbücher für jedes der 6 im Uhrzeigersinn erstellt, für die sich das Unterquadrat von der ursprünglichen zur folgenden Position dreht. Um die Primzahlen zu erstellen, habe ich einfach die Schlüssel und Werte vertauscht.
Die Lösung dieses Problems ist aufgrund der großen Anzahl möglicher Permutationen des Würfels besonders schwierig. Es gibt 24 Unterquadrate und das ergibt 24P24 = 24!. Dies liegt in der Größenordnung von 10^23. Aufgrund bestimmter Situationen sind es weniger als diese Menge, aber die Zahl ist immer noch enorm.
Um den Baum zu erstellen, müsste ich jeden Zug ausführen und alle Züge aus den Zügen ausführen, was sehr groß wird. 12^Höhe des Baumes. Ich konnte diese Größe begrenzen, indem ich ein Diktat der besuchten Positionen erstellte, sodass die Aktion für zuvor besuchte Permutationen nicht wiederholt wurde.
Ich habe mit der Erstellung eines einseitigen BFS begonnen, aber das würde die Rekursionsgrenze erreichen, da der Verzweigungsbaum zu groß werden würde. Um dies zu beheben, habe ich ein zweiseitiges BFS verwendet, indem ich abwechselnd Zweige von der Start- und Endlösung erstellt habe. Es würde die Bäume erstellen und prüfen, ob die Gegenseite den Punkt bereits gefunden hat. Wenn dies der Fall wäre, würde der Verbindungspunkt zurückgegeben.
Währenddessen speichert jeder Knoten seinen übergeordneten Knoten (für die vordere Verzweigung) oder seinen untergeordneten Knoten (für die hintere Verzweigung). Um die Route zu finden, die es genommen hat, habe ich rekursiv den übergeordneten Knoten vom Verbindungsknoten und dann alle untergeordneten Knoten dieses Punktes gefunden. Dies führte zu einer Reihe von Positionen, die vom Durcheinander bis zur Lösung benötigt wurden.
In diesem Projekt habe ich die Graphentheorie und die Breitensuche angewendet. Ich habe meine Fähigkeiten in Python und Rekursion verbessert. Ich habe auch experimentell herausgefunden, dass die maximalen Züge zum Lösen eines 2x2-Würfels 11 Züge betragen, da ich nie eine Lösung finden konnte, die länger dauerte
Erfahren Sie, wie Sie die tkinter-Bibliothek verwenden, um eine GUI für das Projekt zu erstellen
