Springerproblem

Bei diesem kombinatorischen Problem geht es darum, für einen Springer auf einem leeren Schachbrett einen Weg zu finden, auf dem dieser jedes Feld genau einmal besucht. Falls das Endfeld nur einen Springerzug vom Ausgangsfeld entfernt ist, heisst der Weg geschlossen, andernfalls ist er offen. Eine Verallgemeinerung besteht darin, Bretter anderer Formen und Grössen oder n-dimensionale Bretter zu betrachten.

Geschichte

Der Mathematiker Leonhard Euler behandelt diese "kuriose Frage, die keiner Analyse unterworfen worden ist" im Jahre 1759 und stellt sein Lösungsverfahren ausführlich vor. Seither haben sich unzählige Leute, darunter auch viele Mathematiker, mit dem Springerproblem beschäftigt. Es handelt sich aber um ein altes Schachproblem, das in indischen und arabischen Manuskripten des 9. Jahrhunderts bereits beschrieben wird. Während des ganzen Mittelalters und bis heute hat dieses Problem an Interesse nicht verloren.

Mathematik

Für das Springerproblem existieren effiziente Algorithmen: Ein erster Ansatz besteht in der Anwendung eines einfachen Backtracking-Verfahrens. Hierbei wählt man eine willkürliche Route. Wenn man in einer Sackgasse angelangt ist, nimmt man den jeweils letzten Zug zurück und wählt stattdessen einen alternativen Zug. Dieser Algorithmus findet auf jeden Fall eine Lösung, sofern eine existiert, er ist jedoch sehr langsam. Im Jahr 1823 schlägt H.C. Warnsdorff eine Regel vor, nach der der Springer immer auf dasjenige Feld zieht, von dem aus er für seinen nächsten Zug am wenigsten freie, das heisst noch nicht besuchte Felder zur Verfügung hat. Von diesem Ansatz aus werden bessere Methoden entwickelt, bei denen das Spielbrett in kleinere Rechtecke, für die eine Lösung bekannt ist, aufgeteilt wird.