Blog

Das Springerproblem

Eines der Probleme, das ohne Rekursion nur sehr schwer, mit Rekursion aber recht einfach zu lösen ist, ist das Springerproblem:
Wir haben ein Schachbrett mit n × n Feldern gegeben. Im linken unteren Feld steht ein Springer.

Im Schach darf der Springer den sogenannten „Rösselsprung“ durchführen, d.h. zwei Felder vor oder zurück und gleichzeitig eines zur Seite bzw. ein Feld vor oder zurück und zwei zur Seite machen.

Ziel ist es nun, den Springer durch eine Folge von Rösselsprüngen von seinem Ursprungsfeld über das ganze Brett springen zu lassen, so dass er jedes Feld einmal, keines aber doppelt erreicht.

Aufgabe:

Schreiben Sie ein Programm, das für ein Brett der Größe 8×8 versucht, per Backtracking eine Lösung des Springerproblems zu finden!

Hinweis: Schreiben Sie eine rekursive Funktion  int springer( int zeile, int spalte, int num ), die versucht, einen Springer von der Position (zeile,spalte), die er nach dem num- ten Zug erreicht hat, über das restliche Brett springen zu lassen.
Ist das möglich, gibt die Funktion 1, andernfalls 0 zurück. Und nun liegt die Rekursion auf der Hand!

Verwenden Sie ein zweidimensionales int-Feld von der Größe des Schachbrettes, um zu speichern, welche Felder des Brettes schon erreicht wurden.

Lösung:

hier