Lösen des Würfels

Der Solver berechnet aus einem Würfel als Input eine Abfolge von Drehungen, die den Würfel lösen.

Das Lösen erfolgt über einen von zwei Algorithmen.

• Selbstgeschriebener beginner solver
• kociemba solver von H. Kociemba

Neben den eigentlichen Lösungsalgorithmen enthält das solver-Modul noch einige Klassen und Funktionen, um den Würfel und dessen Drehungen zu simulieren.

Grundlagen¶

Intern verwendet der Solver eine eigene Repräsentation des Würfels. Diese ist auf das Lösen optimiert und verzichtet auf eine geometrische Darstellung. Stattdessen wird der Würfel in zwei Schritten zu einer flachen Datenstruktur reduziert.

Der Würfel wird während des gesamten Lösevorgangs in der gleichen Position gehalten. Dadurch werden die Farben der Seiten durch Drehungen nicht geändert und die Seiten behalten ihre Farben auch bei Drehungen bei.

Die Seiten und Farben werden abgekürzt:

(U)p, (L)eft, (F)ront, (R)ight, (B)ack, (D)own

(R)ed, (O)range, (B)lue, (Y)ellow, (G)reen, (W)hite

Cubie¶

Die Cubie-Klasse stellt Subwürfel da. Der Würfel besteht insgesamt aus 26 Cubies. Da der innenliegende Subwürfel (Drehkreuz) fürs Lösen nicht relevant ist, wird dieser vernachlässigt.

Ein Cubie speichert die Farben seiner sichtbaren Seiten. Dies sind drei Farben für Ecken, zwei für Kanten und eine für die Flächen in der Mitte. Um die Seite mitzuspeichern, werden die Farben in einem Dictionary gespeichert, wobei die Seite der Schlüssel und die Farbe der Wert ist.

Cube¶

Um den Rubik's Cube abzubilden, wurde die Cube-Klasse geschrieben. Als Repräsentation wurde zunächst eine Liste mit den Farben der einzelnen Seiten gewählt. Da aber für den Beginner-Algorithmus oft nach bestimmten Cubies gesucht wird, wurde die Datenstruktur erweitert. Nun werden die 26 Subwürfel in einem Dictionary gespeichert. Der Schlüssel ist die Position des Cubies auf dem Würfel und der Wert ist der zugehörige Cubie.

Die Position, gleichzeitig auch der Name, der Cubies ist aus den Seiten zusammengesetzt, an denen sie anliegen. Um das Suchen zu erleichtern, sind die Buchstaben der Seiten alphabetisch sortiert. Dadurch kann jederzeit der Name des Cubies aus den Seiten ermittelt werden.

Move¶

Moves bilden Drehungen einzelner Seiten am Würfel ab. Die durch die Drehung verursachten Änderungen am Würfel sind wieder in einem Dictionary gespeichert. Obwohl es drei verschiedene mögliche Drehungen pro Seite gibt, muss nur die einfachste Variante gespeichert werden, da sich die anderen beiden Drehungen aus der einfachen erzeugen lassen. Im Dictionary wird für jede Drehung eine Liste von Tupeln gespeichert. Jedes Tupel enthält dabei die Änderungen für einen Cubie. Während die Cubie-Namen sonst alphabetisch angegeben sind, enthalten sie hier zusätzlich die Information, wie sich die Facelets auf dem Cubie bewegen.

Aus dem Tupel ('FLU', 'FUR') lassen sich somit folgende Informationen ziehen:

• Cubie FLU bewegt sich zu FRU
• Facelet F behält seine Farbe
• Facelet U erhält die Farbe, die vorher L war
• Facelet R erhält die Farbe, die vorher U war

Solver¶

Beginner Solver¶

Der Beginner solver basiert auf dem Beginner Algorithm von ruwix.com.

Die einzelnen Schritte wurden jeweils in eigenen Dateien implementiert und werden von der BeginnerSolver-Klasse nacheinander aufgerufen.

Der Aufbau dieser Dateien ist immer gleich.

Zuerst werden die notwendigen Schritte definiert. Sind diese unabhängig von dem Zustand des Würfels werden sie von einer Liste aufgenommen. Müssen abhängig von der Seite des Würfels unterschiedliche Schritte ausgeführt werden, werden sie als Wert eines Dictionaries gespeichert. Die Seite des Würfels wird dann als Schlüssel verwendet, um die richtigen Bewegungen abzufragen.

Es folgt dann eine solve(cube)-Methode. Diese errechnet aus dem im cube-Parameter übergebenen Würfel die notwendigen Schritte.

Problem der "einfachen" und intuitiven Schritte¶

Die ersten Schritte lassen sich sehr einfach nachvollziehen und in der Regel ohne weitere Anleitung lösen. Daher sind die Algorithmen nur recht spärlich erklärt. Daraus ergab sich zunächst die Fragestellung, wie sich diese einfachen Schritte gut im Code abbilden lassen.

Dieses Problem wurde durch die sowohl mächtigen als auch einfach zu nutzenden Dictionaries gelöst. In den Dictionaries werden Schritte, die anderweitig nur schwer im Code umzusetzen sind, manuell hinterlegt. Fast jeder Schritt des Beginner Solvers enthält ein solches Dictionary, dessen Aufbau auch immer gleich ist. Als Schlüssel agiert eine Position, deren Wert dann die nötigen Schritte enthält, um zu einem verbesserten Zustand des Würfels zu kommen.

Kociemba Solver¶

Der Kociemba Solver wurde aufgrund des Entwicklungsaufwands nicht selber geschrieben, stattdessen wurde eine fertige Python-Implementierung angepasst.

Der Kociemba-Algorithmus, auch Two Phase genannt, arbeitet in zwei Phasen. Zuerst wird in einer Subgruppe eine Lösung gesucht. Im zweiten Schritt wird dann ausgehend von dem Zustand nach dem ersten Schritt die komplette Lösung ermittelt. Iterativ wird solange nach diesem Vorgehen eine Lösung gesucht bis die gewünschten Parameter erreicht sind (Zeit oder maximale Anzahl an Schritten).

Anpassungen¶

Die vorhandene Implementierung war nicht auf die Verwendung als Bibliothek optimiert. Daher war eine kleine Anpassung notwendig. Der vorhandene Solver konnte nicht aus unserem Programm aufgerufen werden, da die Imports absolut angegeben wurden. Nach dem Ändern zu relativen Imports in den relevanten Dateien kann der fertige Solver auch aus unserem Program heraus aufgerufen werden.

Das nächste Kapitel beschreibt, wie aus der nun generierten Lösung die einzelnen Pfade entstehen, die der Roboter schließlich abfährt.