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

Bei dem Spiel geht es darum, einen Stapel mit n Scheiben komplett von einem Feld (Turm) auf
ein anderes Feld zu verschieben. Ein drittes Feld dient als Hilfsfeld. Anfangs liegen alle Scheiben
übereinander auf einem Feld. Sie sind der Größe nach geordnet. Die größte Scheibe liegt unten und
die kleinste oben. Ein Spielzug sieht nun so aus, dass die oberste Scheibe eines beliebigen Feldes
auf eines der beiden anderen Felder gelegt werden muss. Das geht allerdings nur dann, wenn dort
nicht schon eine kleinere Scheibe liegt.
Übertragen wir das Problem in die Hamster-Welt. Das Territorium besteht aus einer beliebigen An-
zahl an Zeilen und exakt drei Spalten, die die Felder repräsentieren. Es gibt keine Mauern im Ter-
ritorium. Die Scheiben werden durch Körnerhaufen mit unterschiedlicher Anzahl an Körnern er-
setzt. Anfangs liegt auf der untersten Kachel der ersten Spalte der größte Körnerhaufen, darüber der
zweitgrößte, usw. Ganz oben auf dem Turm sitzt der Hamster mit Blickrichtung Ost (siehe bspw.
Abbildung 17.12 (links)). Bei einem Spielzug muss der Hamster den obersten Körnerhaufen einer
der drei Spalten komplett fressen und ihn auf der untersten freien Kachel einer der beiden anderen
Spalten wieder ablegen, vorausgesetzt, darunter liegt nicht bereits ein kleinerer Körnerhaufen. Ziel
ist es, auf diese Art und Weise den kompletten Körnerturm von der ersten in die dritte Spalte zu
transportieren (siehe Abbildung 17.12 (rechts)). Abbildung 17.12 (Mitte) skizziert einen gültigen
Zwischenzustand. Finden Sie einen Algorithmus, der den Hamster das Problem für einen beliebig
hohen Anfangsturm lösen lässt.

1 1

2 2

3 1 3

4 2 4

5 3 4 5 5

Abbildung 17.12: Typische Hamster-Landschaft zu Aufgabe 10

Hinweis: Es gibt einen recht einfachen rekursiven Algorithmus zur Lösung des Problems. Wählen
Sie jedoch keine zu hohen Türme. Denn für einen Turm, der aus n Körnerhaufen besteht, beträgt die
minimale Anzahl an Zügen 2 n -1. Bei einem Turm mit 8 Körnerhaufen sind dies bspw. 255 Züge, bei
einem Turm mit 64 Körnerhaufen jedoch 18.446.744.073.709.551.615 Züge. Wenn der Hamster für
jeden Spielzug eine Sekunde benötigen würde, bräuchte er insgesamt über 584 Milliarden Jahre.