Grafische Lösung

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, Schachbretter der Größe n x n zu verwenden.

Geschichte

Schon lange beschäftigen sich Menschen mit dem Springerproblem. Der Schweizer Mathematiker Leonhard Euler führte das Problem 1758 ein. Seitdem haben sich unzählige Hobby-Tüftler und auch viele Mathematiker, unter ihnen Legendre und Vandermonde , mit dem Springerproblem beschäftigt.

In den 1950er Jahren hat der Apotheker Gerard D'Hooghe einen Automaten entwickelt, der eine Springerrundreise von einem beliebig vorgegebenen Ausgangsfeld demonstriert. Die Grundlagen für diesen Automat hat er 1962 in dem Buch Les Secrets du Cavalier, Le Problème d'Euler dargestellt. Dieser sogenannte t'Zeepaard wurde 1960 während der Schacholympiade in Leipzig öffentlich gezeigt.

Mathematische Grundlagen

Das Springerproblem ist ein Spezialfall des Hamiltonpfadproblems , einem bekannten Problem 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

Backtracking-Verfahren

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.

Warnsdorffregel

Im Jahr 1823 schlug H. C. Warnsdorff eine heuristische Regel vor, die das Finden einer Lösung stark vereinfacht. Nach der Wansdorffregel 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 der Springer später nicht mehr aus der Ecke entkommen kann. Die Warnsdorffsregel 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 Warnsdorffregel 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 et al., der recht komplizierte Entscheidungsregeln für den Fall mehrerer nach der Warnsdorffregel 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 Warnsdorffregel und Backtracking-Verfahren ist möglich, führt aber bei großen Brettern wiederum zu exponentiell anwachsender Laufzeit.

Teile und Herrsche

Im Rahmen einer Arbeit für Jugend Forscht entwickelte eine Gruppe um Axel Conrad einen Algorithmus, mit dem für beliebig große Felder eine Lösung in linearer Zeit gefunden werden kann. In ihrem 1994 in der Zeitschrift Discrete Applied Mathematics 50/1994 veröffentlichten Aufsatz stellten sie ein Verfahren vor, bei dem sie beliebige Schachbretter aufteilen in kleinere Teilrechtecke mit Größen von 5x5 bis 9x9, für die spezielle Lösungen existieren.

Sonstiges

Das Springerproblem ist auch unter dem Namen Rösselsprung bekannt. Letzterer Ausdruck bezeichnet allerdings häufiger ein Rä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.

Literatur

• Squirrel, Douglas, Cull: A Warnsdorff-Rule Algorithm for Knight's Tours on Square Chessboards. Oregon State REU Program, 1996 - Beschreibung einer Erweiterung der Warnsdorffregel, die das Springerproblem in linearer Zeit löst

Weblinks

• Ausführliche Seite mit einer optimalen Lösung
• Seite zur Warnsdorffregel, inklusive Applet zum Ausprobieren