Rösselsprung

Das Problem kann dadurch eingeschränkt werden, dass verlangt wird, dass eine solche Reise geschlossen ist, d.h. vom letzten Feld seiner Reise muss der Springer in einem Zug wieder sein Ausgangsfeld erreichen können.

Man mag denken, dass dieses Problem durch Computer gelöst werden kann. Eine einfache Strategie dafür wäre, den Rechner alle möglichen Wege, die der Springer ziehen kann, prüfen zu lassen. Viele dieser Wege enden natürlich in einer Sackgasse - der Springer kann zu keinem nächsten Feld gelangen, ohne über ein schon besuchtes zu ziehen. In dieser Situation muß man einen Schritt zurückgehen und ein anderes, noch unbesuchtes Feld nehmen. Wenn sich alle möglichen Felder als Sackgassen herausstellen, dann muss man ein weiteres Feld zurückgehen. Diese Strategie wird „Backtracking" - Zurückziehen genannt.

Auf einem normalen 8*8 Brett ist das Problem überraschend groß; so groß dass mit simpler Zählung, selbst mit den heutigen schnellen Rechnern keine Lösung erreichbar ist. Das Problem muss also in einer anderen Art und Weise angepackt werden.

1995 schrieben Martin Löbbing und Ingo Wegener einen Artikel mit der ansprechenden Überschrift: "The Number of Knight's Tours equals 33,439,123,484,294 -- Counting with Binary Decision Diagrams" („Die Zahl der Springer Reisen ist gleich 33 439 123 484 294 - gezählt durch binäre Entscheidungsdiagramme.") Sie gelangten zu diesem Ergebnis, indem sie 20 Sun Workstations vier Monate arbeiten liessen (die tatsächliche CPU Zeit war geringer).

Am 18. Februar 1997 veröffentlichte Brendan McKay sein die vorherige Arbeit korrigierendes Resultat: 13 267 364 410 532. Er nutzte hierzu ein anderes Verfahren und splittete das Schachbrett in zwei gleiche Hälften. [4]

Um eine Idee von der Größe dieser Zahlen zu erhalten, betrachte man einen Computer (266 MHz PC), der pro Minute 1 Million Touren bearbeiten kann. Das scheint sehr schnell zu sein, aber der Computer muss trotzdem über 9213 Tage und Nächte laufen (also über 25 Jahre), um die Rösselsprung-Touren, die McKay errechnet hat, zu finden.

• Das Java Applet auf dieser Seite benutzt die Backtracking Strategie, unterstützt von einer Anzahl von Algorithmen, die früh solche Suchen abbrechen, die in Sackgassen enden. (Ohne sie würde eine reine Backtracking Strategie 3 420 271 572 Züge erfordern, um die erste Tour zu vervollständigen - was für den Betrachter ziemlich langweilig wäre. Jetzt gelangt man mit 94 Zügen zum Ziel). Klicke mit der linken Maustaste auf das Schachbrett, um Zug für Zug vorzugehen. Benutze die rechte Maustaste, um sofort eine vollständige Reise zu erhalten.

2. In seinem schönen Artikel "THE KNIGHT'S TOUR"    gibt Mark R. Keen einen guten und detailreichen Überblick über die Geschichte des Problems.

3. George Peter Jelliss hat eine vollständige Geschichte/Bibliographie des Problems zusammengestellt: Knight's Tour Notes.

4. In the Electronic Journal of Combinatorics, Volume 3,(no 1) findet man beide Artikel in postscript Format; direkt lesbar unter der Adresse sind ein Abstract und Kommentare. (Martin Löbbing und Ingo Wegener haben später ihre fehlerhafte Berechnung noch einmal durchlaufen lassen - siehe ihre „Kommentare" - und das Ergebnis von McKay bestätigt. Ein gemeinsamer Artikel darüber muss noch geschrieben werden (private Korrespondenz mit McKay)).

5. In Japan wird das Problem mit der Hilfe von Neuronalen Netzwerken behandelt. Hier ist ein Applet, das Takayuki Saito erstellte: Neural Network Demonstration for Knight's Tour Problems.
Es ist sehr faszinierend, obwohl es die Tendenz hat, verschiedene unabhängige Reisen auf dem gleichen Brett zu erstellen, anstatt eine zusammenhängende. Vielleicht eine Folge der benutzten Technik.