Springerproblem

Aufgabenstellung

Ein Springer soll einen Weg über ein Schachfeld (mit n*n Feldern) finden, wobei er jedes Feld jeweils einmal besucht.

Zugmöglichkeiten des Springers

Ein Springer besitzt im Schachspiel einen definierten Spielschritt. Er kann sich von seinem Ausgangsfeld 2 Felder in eine beliebige Richtung nach vorne und 1 Feld nach links oder rechts bewegen. Je nachdem wo der Springer nun sitzt, hat er variierende Sprungmöglichkeiten. Befindet er sich in der Mitte des Spielfeldes, so hat er bei einer optimalen Situation maximal 8 Zielfelder die er betreten kann. Mit dieser Anzahl von Sprungmöglichkeiten ist er in der Lage jedes Feld des Schachbretts zu betreten.
Ein Lösungsvorschlag für das Springerproblem, könnte das Bild auf der rechten Seite darstellen.

Lösungsansatz

Vorgehensweise

Meinen Lösungsversuch möchte ich an einem 4x4Feld erläutern und in einzelnen Schritten den Ablauf erklären.

• Anhand der Ausgangsposition des Springers kann man zunächst eine Liste seiner möglichen Züge feststellen. Sitzt der Springer auf dem Feld (2|3) so hat er die Auswahl von 4 Zielfeldern((1|1), (3|1), (4|2) und (4|4)), die er bei seinem nächsten Zug betreten kann. [zur Veranschaulichung siehe Bild 1]

• Die erste Zielposition aus der erstellten Liste wird gewählt und überprüft, ob sie frei ist. Da die Stelle nicht besetzt ist, zieht der Springer auf das Feld (1|1). Das schon besuchte Feld wird, um es sich zu merken, rosa gekennzeichnet. [Bild 2]

• Da die Felder des Schachbretts noch nicht alle besucht worden sind, wird das Spiel fortgesetzt. Mittels dem neuen - aktuellen - Ausgangspunktes wird eine neue Liste der Zugmöglichkeiten((2|3),(3|2)) bestimmt. [Bild 3]

• Da das Zielfeld mit den Koordinaten (2|3) schon besucht worden ist, wird die nächste Zugmöglichkeit aus der Liste gewählt und überprüft. Dieses Feld ist frei und der Springer nimmt dort seinen neuen Platz ein. [Bild 4]

• Nun wird wieder zuerst geprüft ob das Spiel weiterlaufen muss, danach werden die Zugmöglichkeiten, die sich aus dem neuen Ausgangspunkt ergeben, aufgelistet. [Bild 5]

• Die Zugmöglichkeit auf das Feld (1|1) ist belegt und kann nicht ausgeführt werden. Als neuen Ausgangspunkt wählen wir beispielsweiße nun das Feld (4|4) und platzieren dort unseren Springer. [Bild 6]

• Nach der Überprüfung, ob das Spiel weiterläuft und der Auflistung der (wo-)möglichen Zielfeldern, stellt man fest, dass der Springer von diesem Punkt aus nicht weiterziehen kann - seine 2 Zielfelder((2|3) und (3|2)) sind schon belegt. [Bild7]

• Der Spieler muss die Figur also auf die vorherige Ausgangssituation [siehe Bild 5] zurücksetzten. Der Punkt (4|4) wird aus der Liste der möglichen Züge gelöscht, da er nicht erfolgreich war. [Bild 8]

• Nun wird der Springer auf das Feld(2|4)gesetzt. [Bild 9]

Das Spiel läuft solange weiter, bis alle Felder des Schachbrettes besucht worden sind, oder das Programm/der Spieler feststellt, dass es keine Lösung gibt.

Zusammenfassend kann man das Lösungsverfahren in 5 Schritte einteilen:

1	Auflisten der möglichen Spielzüge
2	Wählen der ersten/nächsten Zielkoordinaten
3	Wenn der Zug annehmbar ist, setzte Springer dorthin - Weiter bei 1
4	Wenn der Platz nicht annehmbar ist (nicht frei, oder außerhalb des Spielbrettes) - Weiter bei 2
5	Wiederholen, bis alle Felder besucht worden sind oder es keine Lösung gibt

---

Backtracking

Bei unserem Springeroblem hat die Figur auf dem Schachspiel 8 verschiedene Zugmöglichkeiten, im nächsten Zug besitzt der Springer wieder 8 Möglichkeiten , im nächsten wieder 8, und so weiter. Natürlich können diese 8 Zielfelder nicht immer alle ausgenutzt werden, da sie entweder schon besucht worden sind oder Zielfelder außerhalb des Schachbrettes liegen. Im Prinzip aber lässt sich somit ein Lösungsbaum auflisten, bei dem jeder Zug neue Möglichkeiten aufwirft. Es gilt nun, den Baum Ast zu Ast durchzugehen und die Lösung zu finden. Führt ein Ast nicht zur Lösung, so muss dieser zurückgegangen werden und ein anderer wird überprüft.

Dieses Verfahren nach dem Prinzip von Versuch und Irrtum nennt man Backtracking. Kommt dieses Verfahren in einem Arbeitsschritt nicht mehr weiter, so werden einzelne Ablaufschritte rückgängig gemacht und andere Lösungswege durchgetestet.

Das Problem, dass dieses Verfahren mit sich bringt, ist, dass bei großen Datenmengen, die getestet und ausgewertet werden sollen, eine große Zeitdauer in Anspruch genommen wird. Das heißt im Bezug auf das Springerproblem: je größer das Schachbrett gewählt ist, desto größer ist die Anzahl von möglichen Zugvariationen und damit nimmt auch die Rechendauer zu.

Programmierung

Ausgangssituation

Zunächst müssen wir Die Ausgangssituation/Grundlage des Springerproblems definieren.

• Wie groß ist das Feld?
• Wo liegt meine Startposition?
• Wie kann ich die 8 Koordianten für die Zielfelder errechnen?
• Wie speicher ich das alles ab?

Dies sind nun Fragen die uns beschäftigen.

Das Schachbrett besteht immer aus N*N Feldern. Also ist N eine Variable die sowohl die Anzahl der Felder in einer Reihe und auch die Anzahl der Felder in einer Spalte angibt. Diese Tabelle die sich grundlegend ergibt speichern wir in einem zweidimensionalen Array namens Felder. die xWerte und die yWerte für die Errechnung der Zielfelder werden in einem eindimensionalen Array gespeichert. Diese 2 Arrays müssen nur 8 Speicherplätze besitzen, da es auch nur 8 Zugmöglichkeiten des Springers gibt.

var
   N:integer;
   Felder: Array[1..100,1..100] of integer;
   xWerte: Array[1..8] of integer;
   yWerte: Array[1..8] of integer;

Um vom Ausgangsfeld auf eines der Zielfelder zu gelangen, muss man zu der x- und y-Koordinate eine gewisse Anzahl von Feldern dazu addieren bzw abziehen. Beispiel: Unser Springer sitzt auf dem Feld (2|2), so muss zu x+2 und zu y+1 hinzugefügt werden, so dass der Springer auf dem Zielfeld(4|3) seinen Platz einnimmt. In der Prozedur Ausgangssituation werden diese Werte zu den Speicherplätzen von xWerte und yWerte hinzugefügt und für die spätere Verwendung gemerkt.

procedure Ausgangssituation(x,y:integer);
 var i,j: integer;
  begin
  xWerte[1]:= 2;   yWerte[1]:= 1;
  xWerte[2]:= 2;   yWerte[2]:=-1;    //durch diese Wertepaare können
  xWerte[3]:=-2;   yWerte[3]:= 1;    //die nächsten
  xWerte[4]:=-2;   yWerte[4]:=-1;    //Koordinaten festgestellt werden
  xWerte[5]:= 1;   yWerte[5]:= 2;
  xWerte[6]:= 1;   yWerte[6]:=-2;
  xWerte[7]:=-1;   yWerte[7]:= 2;
  xWerte[8]:=-1;   yWerte[8]:=-2;
  end;

Das ist aber noch nicht alles, was in der Prozedur Ausgangssituation alles festgelegt werden muss. Um das Feld in seiner Größe, anzuzeigen fügt man diese Anweisung hinzu:

 Form1.Spielflaeche.ColCount:=N;  
 Form1.Spielflaeche.RowCount:=N;

Die Variable N gibt die Felderlänger pro Zeile und Spalte an. Da nun zu Anfang des Spiels weiterhin noch kein Feld besucht worden ist, müssen alle Felder auf 0 gesetzt werden, das Startfeld auf 1. Wir setzen deshalb das Startfeld auf 1, da dies unsere erste Position auf dem Schachbrett ist.

 for i:=1 to N do
 for j:=1 to N do
  Felder [i,j]:=0;   //Alle Felder werden auf 0 gesetzt;
  Felder [x,y]:=1;   //Startfeld wird auf 1 gesetzt;

---

Laufbahn des Springers

Um den Ablauf des Programms programmieren zu können, nehmen wir das oben erwähnte Schema als Hilfe zur Hand. Um die Koordinaten des Zielzuges anzugeben wählen wir die Variablen a und b. Zudem brauchen wir noch eine weitere Variable, Variable w. Mit ihrer Hilfe können wir die 8 Zugmöglichkeiten errechnen.
Das Schema packen wir in eine while-Schleife, die solange durchlaufen werden soll, solange w<8 ist, also die Zielzüge noch nicht alle ausgetestet wurden und vor allem erfolgreich=false ist. Erfolgreich ist eine Variable, die überprüfen soll, ob das Spiel gelöst wurde, das heißt, ob alle Felder besucht worden sind.
Wir starten die Prozedur SucheWeg indem wir erstmal alle benötigten Variablen aufzählen. Weiterhin wird der Prozedur die Werte des Zählers, welcher die Züge zählt und anfangs auf 1 steht und die x- und y-Werte des Startfeldes mitgegeben.

procedure SucheWeg(zaehler,x,y:integer);
var w,a,b:integer;   //Zielkoordinaten(a/b)geben den nächsten Zug an
                   //w zählt die möglichen Züge (von 8)
    erfolgreich:boolean //überprüft ob das Spiel gelöst worden ist
begin
 w:=0;                 //w wird auf 0 gesetzt
 erfolgreich:=false;  //Das Spiel ist noch nicht gelöst

Nun folgt die While-Schleife, die ich Schritt für Schritt erklären möchte. Zunächst soll die Variable w, die bisher noch auf 0 stand, auf 1 erhöht werden. Danach können Die Zielkoordinaten (a|b) für den nächsten Zug ermittelt werden, indem mit der Ausgangsposition (x|y) und unserer Errechnungsdaten aus xWerte und yWerte die nächsten Zielkoordianten bestimmt werden.

while (erfolgreich=false) and (w<8) do
 begin
   w:=w+1;
   a:=x+xWerte[w];  //die nächste x-Koordinate wird ermittelt
                   //Bsp: wenn w=1 + x=1 dann ist a=1+-2 => 0
   b:=y+yWerte[w];  //die nächste y-Koordinate wird ermittelt
                   //Bsp: wenn w=1 und y=1 dann ist b=1+1=2

Jetzt ist es ganz wichtig, dass man überprüft, ob die errechneten Were a und b in den Grenzen des Schachfeldes liegen. Errechnet man beispielsweise in einem 6x6 Feld, dass a=3 und b=7 ist, so würde zwar a innerhalb des Schachbrettes liegen, aber nicht b.

  if (1<=a) and
     (a<=N) and   
     (1<=b) and   
     (b<=N)  

Ist die Bedingung erfüllt, überprüft man danach, ob dieses Feld schon besucht worden ist, beziehungsweiße auf 0 steht, denn wir haben in der Ausgangssituation festgelegt, dass alle Felder, außer dem Startfeld auf 0 gesetzt sind.

then  
 if (Felder[a,b]=0) 

Ist dieses Zielfeld noch nicht besetzt gewesen, so nimmt der Springer nun dort seinen neuen Platz ein. Das Feld wird markiert, indem man dort die 0 mit der Zahl, die der Zähler gerade trägt, ersetzt. Konnten die oberen beiden Bedingungen nicht erfüllt werden, so wird die while-Schleife ein nächstes Mal, mit neuen Zielkoordinaten, durchlaufen. Konnte aber das Zielfeld besetzt werden, wird im nächsten Schritt geprüft, ob das Spiel weiterlaufen muss. Dies testet man, indem man die Zähler-Zahl mit der Anzahl der Felder vergleicht. Denn der Springer muss ja alle Felder einmal besucht haben. Ist dies nicht gegeben, so wird die Prozedur SucheWeg wieder gestartet und der Zähler wird um 1 erhöht. Diesen Aufruf durch sich selbst nennt man auch Rekursion. Hat der Springer schon alle Felder besucht, so wird Erfolgreich auf true gesetzt und die Prozedur ist beendet.

then
  begin
    Felder[a,b]:=Zaehler;
      if Zaehler<(N*N)   //prüfen ob das Spiel fertig ist
        then
         begin
           SucheWeg(Zaehler+1,a,b);  //Rekursion
         end
        else
         erfolgreich:=true;  //Spiel gelöst
   end;
 end;
end;

---

Das Programm

Anmerken muss ich, dass meiner Version zur korrekten Lösung ein Programmschritt fehlt, ich ihn aber leider nicht gefunden habe. Der Fehler liegt darin, dass das Programm nicht erkennt, wenn es in eine Sackgasse gelaufen ist und nach dem Prinzip des Backtrackings Ablaufschritte rückgängig machen müsste, um auf einen anderem Weg zur Lösung zu kommen. Trotzdem hier nun meine aktuelle Version: Datei:USpringerproblem.zip