Algorithmen

Der Zauberwürfel

Zauberwürfel stellen viele Menschen vor eine Herrausforderung. Ihn per Zufall zu lösen ist nahezu unmöglich, aufgrund der horrenden Anzahl an möglichen Kombinationen. Insgesamt sind es 43.252.003.274.489.856.000^1 mögliche Kombinationen. Um den Würfel dennoch in einer endlichern Zeit fertig zu stellen, benötigt man Algorithmen, die einen kürtzeren Lösungsweg bieten.

Schicht um Schicht^2

Dieser wohl bekannteste Algorythmus ist insbesondere für anfänger geeignet und und chronlogogisch so aufgebauut, dass auch ein Mensch mit geringem interlektuellem Aufwand in der Lage ist einen Zaberwürfel zu lösen, wenn er sechs siumple Zugfolgen beherscht.

Note

Die exakten Zugfolgen werden hier nicht näher behandelt, da diese in zahlreicher Ausführung im Internet zu finden sind.

1. Zu Beginn wird der Würfel in die Konfiguration des weißen Kreuzes gebracht. Hier sind der Mittelpunkt und die angrenzenden Kanten weiß.
2. Dieses kleine weiße Kreuz wird nun zum großen weißen Kreuz erweitert, indem die Mittelpunkte der Seitenflächen so gedreht werden, dass sie zu den darüberliegenden Kanten passen.
3. Als nächstes werden die oberen Ecken des Würfels gelöst. Dazu werde die Ecken auf der unteren Ebene, gegenüber ihrer eigentlichen Position plaziert und mithilfe eines Algorithmus, der maximal fünf Mal ausgeführt wird, in Position gebracht.
4. Für den weiteren Verlauf des Lösens wird der Würfel umgedreht, sodass die gelöste weiße Seite nach unten zeigt.
5. Nun werden die Kanten der mittleren Ebene in Position gebracht. Für diesen Schritt wird eine Kante über dem gleichfarbigen Mittelpunkt platziert. Abhängig von der anderen Farbe der Kante, die auf der oberen Seite liegt, wird einer von zwei Algorithmen angewendet, um die Kante rechts oder links vom Mittelpunkt zu platzieren.
6. Ähnlich, wie zu Beginn wird nun ein gelbes Kreuz erstellt. Hierfür muss eine gelbe kante nach vorne zeigen. Welche Kante das ist hängt von der Konfiguration der weiteren gelben Quadrate ab. Aus dieser Position wird ein weiterer Algorithmus ein bis drei Mal ausgeführt.
7. Nun müssen die Ecken noch an ihre richtigen Positionen bewegt werden. Auch hier existiert ein fixes Schema, welche Ecken vorne liegen müssen. Daraufhin wird wiederum ein weiterer Algorithmus ausgeführt.
8. Wenn alle Ecken an den richtigen Positionen sind, werden diese mithilfe des Algorithmus aus Punkt 3 solange gedreht, bis der Würfel gelöst ist.

Dieser Algorithmus ist sehr einfach in der Anwendung, benötigt zum Lösen jedoch ca. 90 Züge.

Iterative Deeping A*^3

Neben jenen Algorithmen, die für Menschen verständlich sind, existieren auch solche, die ausschließlich komplexe Computerprogramme lösen könne. Der Iterative Deeping A* (kurz IDA*) gehört ebenfalls dazu. Er basiert auf einem Spielbaum, der theoretisch alle möglichen Kombinationen beinhaltet. Dieser Spielbaum wird dabei nach einem Schema abgesucht, das eine Kombination eines Tiefensuchalgorithmus und Heuristiken verwendet. Er basiert auf Prinzipien der Grafentheorie, verwendet somit Knoten und Kanten, denen jewails Kosten zugewiesen sind. Zudem arbeitet er iterativ, entdeckt also nicht den gesamten Graph mit einem Mal, sondern beginnt regelmäßig beim Startknoten und arbeitet sich langsam durch den gesamten Graphen.

Der Algorithmus geht immer von einem Startknoten aus, von welchem aus er die andern knoten erkundet. Dabei sind jedem Knoten zwei Werte zugewiesen. Die tatsächlichen Kosten g(n) beschreiben dabei den bisherigen Aufwand, die heuristischen Kosten h(n) den prognostizierten Aufwand zum Zielknoten. Die Summer der beiden Werte f(n) dient als Anhaltspunkt, ob ein neuer Knoten besucht wird, oder nicht. Dazu wird ein Schwellenwert festgelegt, der bei jeder Iteration erhöht wird. Ein oten kann nur dann besucht werden, wenn sein F-Score kleiner ist, als der Schwellenwert.
Sind die Scores aller Knoten zu groß beginnt eine neue Iteration.

So wird bei jeder Iteration der Knoten neu entdeckt, der die größte Wahrscheinlichkeit hat, zum Ziel zu führen.