Rekursion - Programmieren Spielend Gelernt mit dem Java-Hamster-Modell - page 335

}
}
boolean gipfelErreicht() {
return vornFrei();
}
void klettereStufeHoch() {
linksUm();
vor();
rechtsUm();
vor();
}
void klettereStufeHinunter() {
vor();
rechtsUm();
vor();
linksUm();
}
void rechtsUm() {
kehrt();
linksUm();
}
void kehrt() {
linksUm();
linksUm();
}
17.8.3 Beispielprogramm 3
Aufgabe:
Der Hamster soll das bekannte Springerproblem lösen: Der Hamster steht irgendwo mit 25 Körnern
imMaul auf einem Schachbrett-Feld mit fünf Zeilen und fünf Spalten (ohne innere Mauern und ohne
Körner auf den Kacheln). Er soll entsprechend der Bewegungsmöglichkeiten eines Springers beim
Schachspiel versuchen, nacheinander alle Felder des Schachbretts mit genau einem Korn zu beset-
zen, ohne dabei zwischendurch auf ein bereits besetztes Feld zu springen. Abbildung 17.5 skizziert
die möglichen Züge eines Springers beim Schachspiel.
Lösungsidee:
Der Hamster löst das Springerproblem mit Hilfe des Backtracking-Verfahrens. Dazu hüpft er von
seinem Ausgangsfeld zu einem zulässigen Zielfeld. Von dort aus begibt er sich auf ein weiteres
bislang noch unberührtes Feld usw. Im Allgemeinen wird der Hamster nicht direkt eine Lösung des
Problems finden, sondern irgendwann auf ein Feld geraten, von dem aus kein weiteres unberührtes
Feld mehr angesprungen werden kann, d.h. er ist in eine Sackgasse geraten. In diesem Fall nimmt
der Hamster so viele Züge zurück, bis er wieder einen anderen zulässigen Zug machen kann.