Das Springerproblem

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. Das Problem ist auch auf Bretter beliebiger Größe und sogar auf mehrdimensionale Bretter verallgemeinerbar. Eine Springertour heißt geschlossen, wenn das Endfeld des Springers einen Springerzug vom Startfeld entfernt ist. Anderenfalls heißt der Weg offen.

Die erste überlieferte Lösung stammt von dem französischen Mathematiker Abraham de Moivre (1667 - 1754). Seine Tour endete allerdings noch weit entfernt von der Ausgangsposition. Der ebenfalls französische Mathematiker Adrien-Marie Legendre (1707-1783) fand schließlich eine geschlossene Springertour, bei der der Springer am Schluss auf einem Feld steht, das nur einen Zug vom Startfeld entfernt ist. Und der Schweizer Leonard Euler (1707-1783) fand eine Tour, in der der Springer erst die eine Hälfte des Schachbretts durchwandert und dann die zweite. Euler war der Erste, der einen mathematischen Aufsatz verfasste, in dem die Springertour analysiert wird.

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 (nichtdeterministisch in Polynomialzeit). Dies bedeutet umgangssprachlich, dass es sich vermutlich nicht effizient lösen lässt. Für das Springerproblem dagegen gibt es inzwischen effiziente Algorithmen, wie z.B. das Backtracking-Verfahren. Hierbei wählt man zunächst eine willkürliche Route. Wenn man in einer Sackgasse landet, nimmt man den jeweils letzten Zug zurück und wählt einen alternativen Zug aus.