ein Schieberätsel

Eine Beschreibung der Aufgabe befindet sich auf der Startseite. Das Applet simuliert das Schieberätsel, wobei man den Anfangs- und Endzustand durch einfügen und löschen von Steinen beschreiben kann. Zur Spezifikation des Endzustandes genügt es eine Teilmenge der Steine anzugeben. Die restlichen Steine sind dann beliebig.

Nun kann eine Lösung berechnet werden. Wenn der Algorithmus stoppt, hat er entweder eine optimale Lösung gefunden, welche dann in einzelnen Schritten betrachtet werden kann, oder es gibt keine Lösung.

Es ist auch möglich, selbst nach einem Lösungsweg zu suchen.

Zur Lösungsidee: Das Applet betrachtet die Menge aller Zustände als Knoten in einem Graphen. Der Lösungsalgorithmus basiert im Wesentlichen auf dem Dijkstra-Algorithmus. Da alle Kanten (Spielzüge) das Gewicht eins haben, kann dieser noch erheblich vereinfacht werden.

Das Programm wird unter der GNU General Puplic License veröffentlicht. Die benutzten Bibliotheken verwenden die GNU Lesser General Public License. Der Quelltext kann ebenfalls heruntergeladen werden.

DateiBeschreibung
movepuzzle.jar das komplette Paket (jar-Dateien sind einfache zip-Dateien) enthält alle zum Ausführen benötigten Dateien inklusive Quelltext

Das Programm hat irgendwo noch einen kleinen Fehler. In bestimmten Zuständen findet es weniger Zugmöglichkeiten als es finden sollte. Um diesen Fehler kümmere ich mich später.


Erstellt von Markus Durzinsky, aktualisiert 2003-12-31
Für Fragen, Probleme oder Anregungen stehe ich gerne zur Verfügung