Vorüberlegung zur Lösung des Problems

Das Springer-Problem „Knight Moves“ ist ein Problem dass nicht in polynomialer Zeit mit einem nicht deterministischem Algorithmus lösbar ist. Versucht man z.b. alle Zugmöglichkeiten durch Permutation zu erzeugen, um eine Lösung zu finden, so ergeben sich bereits bei einem 5x5 Feld (5*5)! = 25! Ca. 1.6*10²⁵ Möglichkeiten. Ein Rechner würde demzufolge für dieses Problem, bei einer Geschwindigkeit von z.b. 1 Milliarde Permutationen pro Sekunde, knapp 500 Millionen Jahre rechnen. Eine bessere Lösung stellt das Backtracking dar. Doch auch durch das Backtracking erhöht sich der Rechenaufwand exponentiell zur Größe des Feldes. Um das Problem schneller lösen zu können, währe es demnach sinnvoll sich eine Heuristik zu überlegen, die die Wahl der Züge entsprechend einschränkt. In einem Artikel der c’t wurde eine Heuristik vorgestellt, die eine existierende Lösung von einer Startposition aus sogar Backtracking frei findet(gezeigt bis zu einem Feld der Größe 53). Diese Heuristik, die immer den Zug als nächstes wählt, der die wenigsten Nachfolgezugmöglichkeiten aufweist, verwende ich auch in meinem Programm.

Das Programm benötigt, um das Problem lösen zu können, folgende Regeln:

Eine Regel, die alle möglichen Züge von einer Stellung aus, in einer Liste zurückliefert.

Eine Regel, die aus einer Liste der möglichen Züge den besten Zug aussucht.

Eine Regel, die den besten Zug in die Liste der besuchten Züge einfügt, bis es keine freien Stellen mehr gibt.

Beschreibung des Algorithmus und der Prolog-Regeln

regel_move(VFeld,AFeld):-

Die Regel regel_move liefert zur Position VFeld einen möglichen Zug, die ein Springer laut Schachregeln machen kann, in der Rückgabevariablen AFeld zurück. Dabei werden die Grenzen des Feldes nicht beachtet, genauso wenig wie die bereits besuchten Felder.

poss_move(N,Feld,ErgL,RL):-

Die Regel poss_move überprüft, ob der von der Regel regel_move zurückgegebene Zug, innerhalb der Grenzen des Brettes(N) liegt und nicht in der Liste, der bereits besuchten Felder(ErgL) vorhanden ist. Ist der Zug in den Grenzen des Feldes und noch nicht „besucht“ so wird dieser in der Rückgabevariablen RL zurückgeliefert. Alle Möglichen durch regel_move generierbaren und durch pos_move zugelassenen Züge, die von dem „Feld“ erreicht werden können, werden in dieser Regel in einer Liste gespeichert und in der Rückgabevariablen RL zurückgeliefert. (Die Regel bedient sich der Hilfe der Prolog-Regel „bagof“)

best_move(_,[],_,BZug):- BZug=[].

best_move(_,[Zug|[]],_,BZug):- BZug=Zug.

best_move(N,[Zug|T],ErgListe,BZug):-

Die Regel liefert den Besten Zug, laut Heuristik, aus der Liste der Züge zurück, die die Regel als Parameter übergeben bekommt. Es werde 3 Fälle unterschieden. 1 Fall : die Liste der Züge ist leer, der BZug ist dann =[]. 2 Fall : Die Liste der Züge enthält nur einen Zug, dann ist dieser automatisch auch der Beste der möglichen Züge. 3 Fall : die Liste der Züge enthält mindestens 2 Züge, in diesem Fall wird rekursiv der Beste Zug von Tail ermittelt([Zug|T]). Der so zurückgelieferte Zug2 wird mit dem Kopf der Liste „Zug“ aus ([Zug|T]) verglichen und der bessere der beiden als BZug zurückgeliefert. Dabei werden mit Hilfe der Regel all_possible_moves die Listen der Nachfolger zu den Beiden Zügen bestimmt und die Längen der beiden miteinander verglichen.(Regel listlen aus dem Script). Der Zug bei dem die Liste der Nachfolgezüge die kleinere ist, ist somit der bessere.

save_move(N,Start,ErgListe,RergListe):-

Die Regel fügt der ErgListe, die als Parameter übergeben wurde, den besten Nachfolgezug, der von dem Feld(Start) aus erreicht werden kann, hinzu und ruft sich rekursiv auf mit der so aktualisierten ErgListe und dem besten Nachfolger als „Start“ wieder auf. Liefert die Regel best_move, dessen Hilfe sich die Regel bedient, eine „[]“ als besten Nachfolger zurück, wird die Rekursion abgebrochen und die so entstandene ErgListe als RergListe zurückgeliefert.

start(N,Spalten,StartZ):-

Wie man dem Namen der Regel schon entnehmen kann, ist das die Start-Regel des Programms. Diese ruft als erstes die Regel save_move auf. Ist die Länge der Ergebnisliste von save_move = NxN, so wird die Ergebnisliste mit Hilfe der Regel rev, aus dem Script, invertiert und mit Hilfe der Regel zael formatiert ausgegeben. Ferner überprüft die Regel ob der Startzustand und die Brettgröße zulässig sind.

zael(N,[H|[]],_,_):-

zael(N,[H|T],N2,N3):-

Die Regel gibt die als Parameter Übergebene Liste formatiert aus. Jeder Zug wird dabei nummeriert und in N2 Spalten ausgegeben. Dabei werden zwei Fälle unterschieden. 1Fall :

Die Liste die als Parameter übergeben wurde enthält genau 1 Element => Ausgabe des Elements. 2 Fall die Liste enthält mindestens 2 Elemente, Ausgabe des ersten Elements und Aufruf der Regel rekursiv mit dem Rest der Liste.

Das von SWI-Prolog produzierte Ergebnisausdruck

?- start(6,4,[1,1]). 1 [1, 1] 2 [2, 3] 3 [1, 5] 4 [3, 6] 5 [5, 5] 6 [6, 3] 7 [5, 1] 8 [3, 2] 9 [1, 3] 10 [2, 1] 11 [4, 2] 12 [6, 1] 13 [5, 3] 14 [6, 5] 15 [4, 6] 16 [3, 4] 17 [2, 6] 18 [1, 4] 19 [2, 2] 20 [4, 1] 21 [6, 2] 22 [5, 4] 23 [6, 6] 24 [4, 5] 25 [6, 4] 26 [5, 6] 27 [4, 4] 28 [2, 5] 29 [3, 3] 30 [5, 2] 31 [3, 1] 32 [1, 2] 33 [2, 4] 34 [1, 6] 35 [3, 5] 36 [4, 3]

Zur Überprüfung des Ergebnisses habe ich den Weg des Springers bildlich veranschaulicht. Aus dem Bild kann man erkennen, dass der Springer von der Startposition 1,1 alle Felder genau einmal besucht und auf dem Feld 4,3 seinen Letzten Zug hat.