Ziel des hier gezeigten Schiebespiels ist es den 2x2-großen Stein mittig an den unteren Rand zu schieben.
Beim Schiebespiel werden in der Regel flache Steine entlang bestimmter Routen (in der Regel auf einem Brett) hin- und hergeschoben, bis ein gewisser Endzustand erreicht ist.
Das bekannteste Schiebespiel ist wohl das 15-Puzzle. Im Gegensatz zu anderen mechanischen Geduldspielen verbietet ein Schiebespiel das Hochheben der Spielsteine vom Brett. Diese Eigenschaft unterscheidet Schiebepuzzles
von Zusammensetzspielen. Daher ist das Finden von Zugpfaden, die sich durch jede Bewegung im zweidimensionalen Raum eröffnen, wichtige Bestandteile beim Lösen eines Schiebespiels.
(Quelle engl. Wikipedia)
Ziel des hier gezeigten Schiebespiels ist es den 2x2-großen Stein mittig an den unteren Rand zu schieben.
Der hier verwendete Algorithmus basiert auf den in der Graphen-Theory wohlbekannten
Dijkstra-Algorithmus.
In der Mathematik sowie in der Informatik versteht man unter einem Graphen eine Menge von Knoten und Kanten. Die Kanten verbinden dabei Paare von Knoten.
Jedem Knoten und jeder Kante ist ein einzelner Wert oder eine ganze Reihe von Eigenschaften zugeordnet. In unserem Fall stellt jeder Knoten einen eindeutigen Zustand dar,
während die Kanten jeweils zwei Zustände verbinden, die durch Verschieben eines einzelnen Steines über die Distanz eines Feldes ineinander umgewandelt werden können.
Das Schiebespiel im obigen Bild hat 65880 eindeutige Zustände. Eindeutig ist hier so gemeint, dass z.B. die Vertauschung der Steine 9 und 10 den Zustand nicht ändert.
Zum Finden einer Lösung sind folgende drei Schritte durchzuführen:
• Finden aller eindeutigen Zustände und diese in einer Liste von Knoten abspeichern
• Finden aller verbundenen Zustände und Abspeichern in einer Liste von Kanten
• Finden des kürzesten Weges zwischen dem Anfangs-und Endzustand mittels Dijkstra-Algorithmus
Das folgende Bild zeigt den Dialog zur Definition von Anfangs- und Endzustand.
Das Schiebespiel kann manuell gelöst werden, ...
... aber auch automatisch mithilfe des oben beschriebenen Algorithmus.
Exe-Datei und Standardproblemstellungen:
SlidingGame_Executable_ver1.0.zip (Version 1.0, 1. Jan 2019, Win10, DirectX 11)
Quellcode:
GitHub repositories Traga 2 and weaselLibrary
Dokumentation:
Lösung des Schiebespiels.pdf (1. Dez 2009)