Wir betrachten folgendes Geduldsspiel:
Das Spielbrett enthält 8 rote und 8 grüne Steine. Ein Feld in der Mitte ist frei.
Ziel des Spiels ist es die grünen und roten Steine auszutauschen.
Folgende horizontalen und vertikalen Züge sind dabei möglich:
- Ein zum leeren Feld angrenzender Stein darf in das leere Feld verschoben werden.
- Ein Stein darf über einen anderen Stein (egal welche Farbe) in das leere Feld springen.
Hier drei gültige aufeinanderfolgende Spielzüge:
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Implementieren Sie ein Programm mit rekursivem Backtracking, das eine Lösung für dieses Problem findet. Beachten Sie, das ein Hin- und Herschieben von Steinen zu unendlichen Zugfolgen führt. Dies kann durch beschränkte Tiefensuche gelöst werden: Bei 50 Zügen wird die Suche abgebrochen (es gibt Lösungen mit weniger Zügen).
Das Spiel habe ich hier gefunden. Dort kann man es mit einem JavaScript-Programm spielen. Den Ursprung des Spiels habe ich leider nicht herausgefunden.
