Türme von Hanoi - Erläuterungen

Zielgerichtet spielen

Herausforderung ist, den Überblick zu behalten, so dass die Zwischenschritte das Spiel wirklich weiter bringen. Bei wenigen Scheiben ist dies einfach, ab n=4/5 wird es schon etwas kniffliger. Die folgende Abbildung zeigt den Zwischenstand für 4 Scheiben nach 5 Zügen: (1AB, 2AC, 1BC, 3AB, 1CA)

Der Turm von 1-3 muss erst auf dem Hilfsbauplatz aufgebaut werden, dann die Scheibe 4 auf den Zielbauplatz versetzt und nachfolgend der Turm von 1-3 ebenfalls dort aufgebaut werden.

In der Ausgangssituation und immer, wenn man die Scheibe 1 wieder setzt (was ausgesprochen oft der Fall ist ;-) ) ist immer die Frage, welches der richtige Bauplatz ist. Es gibt begabte Leute, die dies intuitiv richtig machen, andere (so wie ich) brauchen dafür eine Regel: Wenn n ungerade ist, kommt die 1 auf den Zielbauplatz, sonst auf den Hilfsbauplatz. Also für n=4 zu Beginn die 1 von A nach B setzen.  In Zwischensituationen hilft die Regel auch, den Überblick zu behalten, nur wechseln jeweils Ausgangsbauplatz (wo die 1 dann aktuell steht), Zielbauplatz (wo der Teilturm aktuell hin muss) und Hilfsbauplatz.

Zurück zum Programm - zurück zum Spiel

Wie arbeitet das Programm?

Wie kann man das am elegantesten für einen Computer programmieren? Die Strategie des Spiels ist, immer zunächst den Turm von 1 bis n-1 auf den Hilfsbauplatz B zu versetzen, dann die größte Scheibe (n) von A nach C , und dann wiederum den Teilturm bis n-1 von B nach C.

Wie mache ich die Zwischenschritte, um den Turm bis n-1 auf den Hilfsbauplatz zu setzen?

Nun, ganz einfach, zunächst den Turm bis n-2 auf den Zielbauplatz, dann Scheibe n-1 auf den Hilfsbauplatz, dann den Turm bis n-2 auf den Hilfsbauplatz.

Aha... Und wie geht das für n-3? Bei großen n bin ich ja noch lange nicht fertig!

Naja, immer so weiter. Wir nehmen einfach an, wir können das schon für n-1 und zählen n runter bis 1. 1 können wir versetzen, fertig. In Pseudocode geschrieben:

Funktion Hanoi (n, Quelle, Ziel, Hilfe) {
    wenn n=1 {
        setze 1 von Quelle auf Ziel;
    }
    sonst {
        Hanoi (n-1, Quelle, Hilfe, Ziel);
        setze n von Quelle auf Ziel;
        Hanoi (n-1, Hilfe, Ziel, Quelle);
   }

Dabei ruft die Funktion Hanoi() sich selbst immer wieder auf, das nennt man Rekursion. Um erfolgreich zu sein, muss dies terminieren, also irgendwann zuende sein. Da n herunter gezählt wird, ist das der Fall, man muss nur dafür sorgen, dass n eine natürliche Zahl ungleich Null ist.

Wie viele Züge brauche ich?

Es fällt auf, dass man bei wenigen Scheiben relativ schnell fertig wird, aber schon bei 4-5 Scheiben wird es langwierig, und man hat das Gefühl, dasselbe in grün immer wieder zu machen: Die Zahl der erforderlichen Züge wächst exponentiell, genau beträgt sie bei n Scheiben 2ⁿ - 1 Züge. Bei 10 Scheiben sind das immerhin schon 1.023 Züge! Bei jedem zweiten Zug wird die Scheibe 1 bewegt, bei jedem vierten die Scheibe 2 usw. Da kann man schon mal den Überblick verlieren.

Warum sind es so viele Züge, wie beweist man das? In der Mathematik gibt es das Prinzip der vollständigen Induktion, das umgekehrt zur Rekursion funktioniert.

Für n=1 brauche ich einen Zug (1AC). Angenommen, ich brauche für n-1 Scheiben 2^n-1 - 1 Züge. Dann brauche ich für n Scheiben 2*(2^n-1 - 1) + 1  Züge. (Ein Mal den Turm bis n-1 auf den Hilfsplatz, n auf den Zielplatz, dann den Turm bis n-1 auf den Zielplatz).

2*(2^n-1 - 1) + 1 = 2*2^n-1 - 2 + 1 = 2ⁿ - 1

D.h. die Formel ist bewiesen für alle n, denn sie gilt für n=1 und unter der Voraussetzung, dass sie für alle n-1 (ab n=2) gilt, gilt sie auch für n. :-)

Zurück zum Programm - zurück zum Spiel

Wie arbeiten die Tipps?

Die Tipps kann man im Prinzip mit der normalen Hanoi-Funktion erzeugen und dann jeweils die Züge des Benutzers damit vergleichen. Wenn der Zug im Sinne der Tipps richtig ist, wird normal gezogen, sonst eine Meldung gezeigt. Man kann sich dann entschließen, trotzdem den Zug zu setzen. In diesem Fall werden die Tipps abgestellt.

Hier sollte aber das An- und Abstellen der Tipps flexibel erfolgen können, d.h. zu jedem Zeitpunkt im Spiel. Außerdem sollte man sich entschließen können, einen Tipp zu ignorieren und hinterher die Tipps wieder anzustellen. Dann braucht man eine allgemeinere Hanoi-Funktion, die nicht nur aus dem Startzustand, sondern aus beliebigen Zwischenzuständen funktioniert. Hierbei muss dann die aktuell zu setzende Scheibe gesucht und eine Fallunterscheidung gemacht werden:

• Liegt die Scheibe n schon auf dem Zielbauplatz, wird nur noch der Turm von (n-1) nachgezogen.
• Liegt sie noch auf dem Startbauplatz, wird wie bei Hanoi() rekursiv weiter gearbeitet, d.h. Turm bis (n-1) wegräumen, Scheibe setzen, Turm bis (n-1) nachziehen.
• Liegt die Scheibe n auf dem Hilfsbauplatz, hat man sich "verspielt", dann muss erstmal der Turm darüber auf den Startbauplatz geräumt werden, die Scheibe auf das Ziel gesetzt und schließlich der Turm (n-1) nachgezogen.

Dafür wird im Hintergrund ein Spielfeld aufgebaut, da die erweiterte Funktion jeweils den aktuellen Spielzustand analysieren muss.