Ein Springer soll nach den normalen Regeln dafür, wie er im Schach zieht, auf einem n*n großen Spielfeld von beliebiger Startposition so springen, dass er jede Position genau einmal - nicht mehr und nicht weniger - berührt.
Wieso n*n? Ein Schachfeld hat genau 8*8 Felder! - Richtig, aber auf einem 8*8 großen Feld werden die Zeiten für das Finden einer einzigen Lösung sehr, sehr groß. Es gibt dann nämlich 8^64 Möglichkeiten, die der Computer durchrechnen muss (8 Möglichkeiten zu springen, dies bei jedem Zug bis das Brett voll ist; also 8^Anzahl der Positionen auf dem Brett = 8^64). Man nimmt darum generell ein n*n großes Feld, damit man auch funktionierende Ergebnisse beobachten kann.
Im Beispielprogramm wurden für n Werte von 4 bis Acht möglich gemacht. Jeder kann sich sehr schnell überlegen, dass es für ein 1*1 großes Feld genau eine recht uninteressant zu berechnende Lösung gibt, für das 2*2 Feld gibt es keine, genausowenig wie für das 3*3 große Feld (Der Springer startet entweder in der Mitte und kann sich von dort nirgendwohin bewegen, oder er wird die Mitte von irgendwo anders her niemals erreichen). Für das 4*4 große Feld ist es unmöglich im Kopf nachzuvollziehen, ob es eine Lösung gibt. Wie das Programm nachher zeigt, gibt es keine.
Doch nun zur Funktionsweise von Backtrackingalgorithmen: Der Trick ist, jede Möglichkeit, die es gibt, mit Hilfe einer rekursiven Funktion oder Prozedur (in diesem Fall Prozedur) durchzurechnen und sich die letztendlich funktionierenden Lösungen zu merken.
In diesem Fall sähe das so aus: Ich suche mir eine Startposition für den Springer. Von da aus gehe ich der Reihe nach alle 8 Möglichkeiten ab, die der Springer setzen kann. Von jenen angegangenen Möglichkeiten gehe ich ebenfalls jeweils 8 Möglichkeiten und so weiter. Jedesmal markiere ich dabei die Position, an der ich schon gewesen bin, damit ich nicht doppelt auf diese setzen kann. Wenn ich nun alle Möglichkeiten von einer Position aus versucht habe, so nehme ich den letzen Zug wieder zurück (ich lösche die Markierung), egal ob ich eine Lösung gefunden habe oder nicht. Auf diese Art und Weise werden wirklich alle Zugmöglichkeiten, die es gibt, ausprobiert und alle Lösungen werden gefunden.
Dieses an sich sehr simple Verfahren lässt sich für viele Probleme verwenden, beispielsweise auch die Wegsuche aus einem Labyrinth (Probiere alle Wege aus; bei Sackgasse geh zurück zum letzten Knoten und probier anderen Weg bis der Ausgang gefunden wurde). Es bildet auch die Grundlage für einfache künstliche Intelligenzen die mit dem sogenannten Alpha-Beta-Schnitt arbeiten.
History
25.06.2003 Hinzugefügt
Autor: Benjamin Schröder <Benny_auf_vbInside.de>
