Das Springerproblem ist ein kombinatorisches Problem, das darin besteht, für einen Springer auf einem leeren Schachbrett eine Route zu finden, auf der dieser jedes Feld genau einmal besucht. Eine mehrerer möglicher Verallgemeinerungen besteht darin, zweidimensionale Bretter beliebiger Größe n × m oder gar n-dimensionale Bretter zu verwenden. Eine Springertour heißt geschlossen, wenn das Endfeld des Springers einen Springerzug vom Startfeld entfernt ist. Anderenfalls heißt der Weg offen (wie im Diagramm).
Das Springerproblem ist auch unter dem Namen Rösselsprung bekannt. Letzterer Ausdruck bezeichnet allerdings häufiger das Rösselsprungrätsel, bei dem Buchstaben oder Silben in den Feldern des Brettes eingetragen sind, die in der richtigen Reihenfolge durch eine Springertour besucht, einen Lösungssatz oder ein Lösungswort ergeben. Es sei ferner angemerkt, dass das Springerproblem etwas völlig anderes als das Damenproblem ist, doch haben sich die beiden Bezeichnungen historisch eingebürgert.
Geschichte Bearbeiten
Das Problem findet sich in einem Sanskrit-Gedicht von Rudrata aus dem 9. Jahrhundert. Im Westen wird es in einem Codex des 14. Jahrhunderts der Pariser Nationalbibliothek erwähnt. Abraham de Moivre und Pierre Rémond de Montmort gaben Anfang des 18. Jahrhunderts Lösungen an. Der Schweizer Mathematiker Leonhard Euler behandelte das Springerproblem 1759 mathematisch. Seitdem haben sich viele weitere Mathematiker (unter ihnen Legendre und Vandermonde) und unzählige Hobby-Tüftler mit der Materie beschäftigt.
In den 1950er Jahren entwickelte der Apotheker Gerard D’Hooghe einen Automaten, der eine Springerrundreise von einem beliebig vorgegebenen Ausgangsfeld demonstriert. Die Grundlagen für diesen Automaten stellte er 1962 in dem Buch Les Secrets du Cavalier, Le Problème d’Euler dar. Sein sogenannter t’Zeepaard wurde 1960 während der Schacholympiade in Leipzig öffentlich gezeigt.
Mathematische Grundlagen Bearbeiten
Das Springerproblem ist ein Spezialfall des Hamiltonpfadproblems, eines bekannten Problems der Graphentheorie, bei dem in einem Graphen alle Knoten genau einmal besucht werden müssen. Wenn von dem letzten Feld der Zugfolge das erste Feld erreicht werden kann, hat man einen Hamiltonkreis gefunden. Das Hamiltonpfadproblem ist NP-vollständig, ein effizienter Lösungsalgorithmus ist also nicht bekannt und existiert, wie allgemein vermutet wird, auch nicht. Dagegen existieren für das Springerproblem effiziente Algorithmen, die unten vorgestellt werden.
Lösungsverfahren Bearbeiten
Backtracking-Verfahren Bearbeiten
Ein erster Ansatz für einen Algorithmus besteht darin, ein einfaches Backtracking-Verfahren anzuwenden. Hierbei wählt man eine willkürliche Route und nimmt, wenn man in einer Sackgasse angelangt ist, den jeweils letzten Zug zurück und wählt stattdessen einen alternativen Zug aus. Dieser Algorithmus findet auf jeden Fall eine Lösung, sofern eine existiert, er ist jedoch sehr langsam. Auf größeren Brettern kann ein Mensch durch geschicktes Ausprobieren innerhalb viel kürzerer Zeit eine Lösung finden, als dass der einfache Backtracking-Algorithmus zum Ziel kommt.
Das folgende Computerprogramm in der Programmiersprache C++ findet eine Lösung des Springerproblem mit Hilfe eines rekursiven Algorithmus, der Backtracking verwendet. Wenn eine gefundene Tour alle Felder des Schachbretts durchläuft, wird die Lösung ausgegeben und das Programm beendet.
#include <iostream> #include <sstream> using namespace std; const int n = 8; // Konstante für die Anzahl der Felder pro Seite // Gibt die Züge der Springertour auf der Konsole aus string knightsTourToString(int knightsTour[n][n]) { stringstream text; int weight = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { text << knightsTour[i][j] << "\t"; } text << endl; } return text.str(); // Typumwandlung von stringstream nach string } // Diese rekursive Methode bestimmt eine Springertour und gibt true zurück, wenn gefunden, sonst false bool getKnightsTourRecursive(int x, int y, int moveNumber, int knightsTour[n][n], int xMove[n], int yMove[n]) { if (moveNumber == n * n) // Wenn alle Felder besucht sind, wird true zurückgegeben { return true; } // Prüft die möglichen Züge des Springers für das aktuelle Feld mit den Koordinaten x, y for (int i = 0; i < 8; i++) { // Bestimmt die Koordinaten des nächsten Felds int nextX = x + xMove[i]; int nextY = y + yMove[i]; if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && knightsTour[nextX][nextY] == -1) // Wenn das nächste Feld innerhalb des Schachbretts liegt und noch nicht besucht wurde { knightsTour[nextX][nextY] = moveNumber; // Setzt die Zugnummer für das nächste Feld if (getKnightsTourRecursive(nextX, nextY, moveNumber + 1, knightsTour, xMove, yMove)) // Rekursiver Aufruf der Methode für den nächsten Zug { return true; // Wenn Springertour gefunden } else { knightsTour[nextX][nextY] = -1; // Wenn keine Springertour gefunden wurde, wird der Zug rückgängig gemacht } } } return false; // Wenn keine Springertour gefunden } // Diese Methode bestimmt eine Springertour mithilfe von Backtracking und gibt true zurück, wenn vorhanden, sonst false bool getKnightsTour(int knightsTour[n][n]) { // Initialisiert die Felder des Schachbretts for (int i = 0; i < n; i++) // Diese beiden for-Schleifen durchlaufen alle Felder des Schachbretts { for (int j = 0; j < n; j++) { knightsTour[i][j] = -1; } } // Diese Arrays definieren die möglichen Züge des Springers int xMoves[8] = { 2, 1, -1, -2, -2, -1, 1, 2 }; // Array für die Änderung der x-Koordinate int yMoves[8] = { 1, 2, 2, 1, -1, -2, -2, -1 }; // Array für die Änderung der y-Koordinate knightsTour[0][0] = 0; // Initialisiert das Startfeld links oben return getKnightsTourRecursive(0, 0, 1, knightsTour, xMoves, yMoves); // Aufruf der Methode } // Hauptmethode, die das Programm ausführt int main() { int knightsTour[n][n]; // Deklariert ein zweidimensionales Array für die Felder des Schachbretts if (getKnightsTour(knightsTour)) // Aufruf der Methode { cout << knightsTourToString(knightsTour); // Ausgabe auf der Konsole } else { cout << "Es gibt keine Springertour." << endl; // Ausgabe auf der Konsole } } Warnsdorfregel Bearbeiten
Im Jahr 1823 schlug H. C. von Warnsdorf eine heuristische Regel vor, die das Finden einer Lösung stark vereinfacht. Nach der Warnsdorfregel zieht der Springer immer auf das Feld, von dem aus er für seinen nächsten Zug am wenigsten freie (d. h. noch nicht besuchte) Felder zur Verfügung hat. Diese Regel ist unmittelbar einleuchtend; sie verhindert beispielsweise, dass eines der beiden Felder, die der Springer von einer Ecke aus erreichen kann, frühzeitig besucht wird, so dass er später nicht mehr aus der Ecke entkommen könnte. Die Warnsdorfsregel gibt keine Anweisung, was zu tun ist, wenn es mehrere Felder gibt, von denen es gleich wenige im nächsten Zug erreichbare Felder gibt.
Die Warnsdorfregel kann, auch wenn eine Lösung existiert, nicht garantieren, dass diese gefunden wird, und in der Tat gerät der Springer für große Bretter zunehmend oft in eine Sackgasse. Selbst auf einem Schachbrett (n = 8) kann der Algorithmus scheitern, wenn man unter mehreren möglichen Alternativen die falschen auswählt, dies ist allerdings sehr unwahrscheinlich.
Hier ansetzend wurden verbesserte Heuristiken entwickelt, unter anderem ein Algorithmus von Squirrel, der recht komplizierte Entscheidungsregeln für den Fall mehrerer nach der Warnsdorfregel gleichwertiger Alternativen angibt, jedoch anscheinend für alle Bretter größer als n = 75 in linearer Zeit eine Lösung findet (der formale Korrektheitsbeweis ist bisher nur für n = 7 mod 8 geführt). Die Verbindung von Warnsdorfregel und Backtracking-Verfahren ist möglich, führt aber bei großen Brettern wiederum zu exponentiell anwachsender Laufzeit.
Teile-und-herrsche-Verfahren Bearbeiten
Im Rahmen einer Arbeit für Jugend forscht entwickelte eine Gruppe verschiedene Algorithmen, mit denen für beliebig große Felder eine Lösung in einer Laufzeitkomplexität von gefunden werden kann. In ihrem 1994 veröffentlichten Aufsatz stellten sie ein Verfahren vor (das Teile-und-herrsche-Verfahren), bei dem sie beliebige Schachbretter in kleinere Teilrechtecke mit Größen von 5 × 5 bis 9 × 9 aufteilen, für die spezielle Lösungen existieren.
Schwenksches Theorem Bearbeiten
Für jedes Brett, mit , , gibt es eine geschlossene Springertour, es sei denn, einer der folgenden drei Fälle liegt vor:
Ein Beweis lässt sich anhand der in der oben genannten Jugend-forscht-Arbeit dargestellten Algorithmen herleiten. Unter den genannten Bedingungen können beliebige Start- und Zielfelder gewählt werden, also auch solche, bei denen von dem Zielfeld wieder auf das Startfeld gesprungen und damit die Springertour geschlossen werden kann.
1. Fall Bearbeiten
Man stelle sich vor, die Felder seien schachbrettartig schwarzweiß gefärbt. Start- und Endfeld müssen bei einem geschlossenen Weg verschiedene Farben haben. Da der Springer nach jedem Zug seine Feldfarbe wechselt, muss er auf seinem Weg genauso viel weiße wie schwarze Felder überschreiten, also eine gerade Zahl an Feldern.
2. Fall Bearbeiten
Ist oder , so kann der Springer offensichtlich nicht jedes Feld erreichen (es sei denn im trivialen Fall des 1 × 1-Bretts).
Ist , so sei die Menge der weißen Felder, die Menge der schwarzen Felder, die Menge der Randfelder an den beiden gegenüberliegenden längeren Brettkanten und die Menge aller Felder, die nicht zu gehörten, sprich . hat gleich viele Elemente wie .
In jedem Zug ändert der Springer die Feldfarbe und die Feldart zwischen und . Letzteres folgt aus folgender Überlegung: Von einem Randfeld (Menge ) kann der Springer nur auf ein Feld in der Mitte gelangen (Menge ). Würde der Springer nun einen Zug innerhalb von ausführen (was möglich ist), würde er mehr Felder von besuchen als von , was zu keiner Lösung führen kann, weil die beiden Mengen gleich viele Felder umfassen.
Ohne Einschränkung ist das Anfangsfeld ein Element aus und . Vertausche hierfür notfalls die Rollen von und und die Rollen von und .
Im nächsten Zug ist die Feldfarbe Element aus und , dann wieder aus und und so weiter.
Dies zeigt zum einen, dass die gleichen Elemente wie hat, und zum anderen, dass die gleichen Elemente wie hat, somit und , was offensichtlich nicht stimmt.
3. Fall Bearbeiten
Auf den Brettern 3 × 4, 3 × 6 und 3 × 8 lässt sich kein geschlossener Weg finden.
Wege für die Brettgrößen 3 × 10, 3 × 12, 3 × 14 usw. sind möglich, wobei sich das Lösungsmuster wiederholt.
Kombinatorik Bearbeiten
Die Anzahl der Lösungen für ein -Schachbrett steigt schneller als exponentiell mit . Für ist die Anzahl der möglichen Touren bekannt:
| Anzahl der möglichen Springertouren | ||
|---|---|---|
| n | alle gerichteten Springertouren | geschlossene ungerichtete Springertouren |
| 1 | 1 | 0 |
| 2 | 0 | 0 |
| 3 | 0 | 0 |
| 4 | 0 | 0 |
| 5 | 1728 | 0 |
| 6 | 6637920 | 9862 |
| 7 | 165575218320 | 0 |
| 8 | 19591828170979904 | 13267364410532 |
Auf Brettern mit einer ungeraden Anzahl Feldern gibt es aus Paritätsgründen keine geschlossene Tour (siehe 1. Fall von Schwenksches Theorem).
Siehe auch Bearbeiten
Einzelnachweise Bearbeiten
- (Memento vom 21. Januar 2012 im Internet Archive)
- Wilhelm Ahrens Mathematische Unterhaltungen und Spiele, Teubner 1901, S. 165. Er zitiert A. von der Linde Geschichte und Literatur des Schachspiels, Berlin 1874, Band 2, S. 101. Siehe auch W. W. Rouse Ball Mathematical recreations and essays, 4. Auflage. Macmillan 1905, S. 158ff, Online bei Gutenberg
- GeeksforGeeks: The Knight’s tour problem | Backtracking-1
- Axel Conrad, Tanja Hindrichs, Hussein Morsy, Ingo Wegener: Solution of the Knight’s Hamiltonian Path Problem on Chessboards. Discrete Applied Mathematics, Volume 50, Issue 2, May 1994, Pages 125-134.
- Eine kurze Reise durch die Welt des Springers
- Folge A165134 in OEIS
- Wolfram MathWorld: Knight Graph
Literatur Bearbeiten
- Douglas Squirrel, Paul Cull: A Warnsdorff-Rule Algorithm for Knight’s Tours on Square Chessboards. Oregon State REU Program, 1996. (Beschreibung einer Erweiterung der Warnsdorfregel, die das Springerproblem in linearer Zeit löst)
- Allen J. Schwenk: Which Rectangular Chessboards Have a Knight's Tour?, Mathematics Magazine 64 (1991) p. 325-332. doi:10.1080/0025570X.1991.11977627
Weblinks Bearbeiten
- Ausführliche Seite mit einer optimalen Lösung
- (Memento vom 2. August 2012 im Internet Archive)