Türme von Hanoi spielen und lösen

Die Türme von Hanoi sind ein Denkspiel für eine Person. Auf einem Brett stehen drei Stäbe, auf dem linken steckt ein Turm aus gelochten Scheiben, die nach oben immer kleiner werden. Dieser Ausgangsstab heißt A, der Zielstab rechts C und der Hilfsstab in der Mitte B. Der ganze Turm soll auf den Zielstab, ohne dass je eine größere Scheibe auf einer kleineren liegt.

Drei Spielregeln gelten für jeden Zug, im Browser genauso wie mit Holzscheiben auf dem Tisch.

• Pro Zug wird genau eine Scheibe bewegt.
• Bewegt werden darf nur die oberste Scheibe eines Stabs.
• Eine Scheibe kommt auf einen leeren Stab oder auf eine größere Scheibe, nie auf eine kleinere.

Ein Zug ist hier das Umsetzen einer Scheibe von einem Stab auf einen anderen. Das Digitale Wörterbuch der deutschen Sprache verzeichnet Zug im Sinn des Setzens einer Spielfigur, mit Wendungen wie einen Zug tun und einen Zug zurücknehmen. Beides gibt es auch hier.

Wer einen Stab antippt oder anklickt, hebt dessen oberste Scheibe an; ein zweites Antippen auf einem anderen Stab legt sie dort ab. Scheiben lassen sich auch mit dem Finger oder der Maus hinüberziehen. Mit der Tastatur wählt Tab einen Stab, eine Zahl oder ein Buchstabe hebt an und legt ab, Escape legt die Scheibe zurück, und die Pfeiltasten wechseln den Stab.

Einen verbotenen Zug führt das Spiel nicht aus. Die Meldung sagt, warum, etwa „Scheibe 2 darf nicht auf Scheibe 1“, und das Brett wackelt kurz, außer wenn das Gerät reduzierte Bewegung verlangt. Drei Zähler laufen mit: die Züge, die Mindestzahl ab dem Start dieses Spiels und die Zeit, die mit dem ersten Zug beginnt und stoppt, sobald der Turm steht. „Rückgängig“ nimmt beliebig viele Züge zurück, jeder davon zählt im Ergebnis mit.

Das erste Spiel beginnt mit 4 Scheiben auf drei Stäben, die kürzeste Lösung hat 15 Züge. Mit vier Stäben endet die Auswahl bei 8 Scheiben. Der Tipp durchsucht dann jede der 4ⁿ möglichen Stellungen, und mit mehr Scheiben würde das auf einem Handy zu lange dauern. Am Ende stehen Züge und Mindestzahl, die Zeit auf Zehntelsekunden, Tipps und zurückgenommene Züge, dazu „Ergebnis kopieren“, „Noch einmal spielen“ und ein Versuch mit einer Scheibe mehr.

Mindestens 2ⁿ - 1 Züge bei n Scheiben, also 31 bei fünf und 1.023 bei zehn Scheiben. Wer ohne Pause einen Zug pro Sekunde schafft, braucht für zehn Scheiben 17 min 3 s.

Auf drei Stäben hängt die Mindestzahl der Züge nur von der Zahl der Scheiben ab. Beginnt das Spiel mit dem vollen Turm, sind es für n Scheiben 2ⁿ - 1. Weniger geht nicht: Die unterste Scheibe kann erst ziehen, wenn alle kleineren auf dem dritten Stab warten, und danach müssen sie wieder auf sie. Jede weitere Scheibe verdoppelt die Zahl und fügt einen Zug hinzu, wie schon Édouard Lucas schrieb. Aus 7 Zügen bei drei Scheiben werden 15 bei vier und 31 bei fünf. Lucas' Originalspiel von 1883 hatte 8 Scheiben, was 255 Züge ergibt; im Sekundentakt sind das 4 Minuten und 15 Sekunden, nach seiner eigenen Angabe mehr als vier Minuten.

Die Online-Enzyklopädie der Zahlenfolgen OEIS führt die Zahlen der Form 2ⁿ - 1 als Folge A000225 und vermerkt, dass sie manchmal auch Mersenne-Zahlen heißen. Vier dieser Werte prüft die Seite gegen bekannte Antworten, darunter 63 Züge für sechs Scheiben aus dem Online-Labor des Karlsruher Instituts für Technologie.

Mit zwei Regeln, die sich abwechseln. Bei jedem ungeraden Zug zieht die kleinste Scheibe, und zwar immer in dieselbe Richtung reihum über die drei Stäbe. Bei jedem geraden Zug bleibt sie liegen, und zwischen den beiden anderen Stäben ist nur eine Bewegung erlaubt: Die kleinere ihrer obersten Scheiben wechselt auf den anderen Stab.

Die Richtung hängt von der Zahl der Scheiben ab. Bei einer ungeraden Zahl läuft die kleinste Scheibe A, C, B, A und so fort, geht also zuerst auf den Zielstab C. Bei einer geraden Zahl läuft sie A, B, C, A und beginnt auf dem Hilfsstab B. Lucas schreibt diese Regel im 3. Band seiner Récréations mathématiques seinem Neffen Raoul Olive zu, einem Schüler des Lycée Charlemagne.

Mit drei Scheiben geht zuerst Scheibe 1 nach C, dann Scheibe 2 nach B und Scheibe 1 hinterher nach B. Auf dem Hilfsstab steht nun ein Teilturm aus zwei Scheiben. Im 4. Zug wechselt Scheibe 3 von A nach C. Es folgen Scheibe 1 nach A, Scheibe 2 nach C und Scheibe 1 nach C, und nach 7 Zügen steht der Turm komplett auf C.

Für fünf Scheiben sind es 31 Züge. Davon macht Scheibe 1 allein 16, Scheibe 5 nur einen, den 16. Zug. Die ganze Zugfolge, mit Scheibe 1 als kleinster, steht hier Zeile für Zeile.

Diese Regel ist ein iterativer Algorithmus: Sie arbeitet Zug für Zug, ohne auf kleinere Teiltürme zurückzugreifen. Welche Scheibe bei einem Zug dran ist, verrät die Binärdarstellung seiner Nummer: Endet sie auf k Nullen, zieht Scheibe k + 1. Zug 4 lautet binär 100 und bewegt deshalb Scheibe 3. Die ersten acht Züge bewegen so die Scheiben 1, 2, 1, 3, 1, 2, 1, 4. Die OEIS führt diese Folge als A001511, mit einem Kommentar von A. M. Hinz.

Im Spiel zeigt der Bereich „Die Lösung Zug für Zug“ die kürzeste Lösung für den gewählten Turm, nummeriert und in der Form „Scheibe 1: A nach C“. Solange das Spiel ihr folgt, ist der nächste Zug hervorgehoben, und „Zugliste drucken“ bringt nur diese Liste aufs Papier. Mit vier Stäben steht dort die Lösung nach Frame und Stewart; es gibt dann auch andere Lösungen gleicher Länge.

„Das Problem der Türme von Hanoi ist gut geeignet für den Einstieg in rekursive Algorithmen“, heißt es in einem Umsetzungsbeispiel der Hessischen Lehrkräfteakademie zum Kerncurriculum Informatik der gymnasialen Oberstufe. Rekursion bedeutet, dass ein Problem auf ein kleineres Problem derselben Art zurückgeführt wird. Auch die Lernplattform inf-schule des Pädagogischen Landesinstituts Rheinland-Pfalz beginnt das Problemlösen durch Problemreduktion mit diesem Spiel.

Der rekursive Weg führt einen Turm aus n Scheiben auf einen Turm aus n - 1 Scheiben zurück, in drei Schritten.

1. Den Teilturm der n - 1 kleineren Scheiben vom Ausgangsstab auf den Hilfsstab bringen, mit dem Zielstab als Zwischenstation.
2. Die größte Scheibe vom Ausgangsstab auf den Zielstab legen.
3. Den Teilturm vom Hilfsstab auf den Zielstab bringen, oben auf die bereits umgesetzte große Scheibe.

Schritt eins und drei sind dieselbe Aufgabe mit einer Scheibe weniger, nur mit vertauschten Rollen der Stäbe. Sie lösen sich auf dieselbe Weise, bis ein Turm aus einer einzigen Scheibe übrig ist, der in einem Zug umzieht. Robert Sedgewick und Kevin Wayne von der Princeton University nutzen das Spiel in ihrem Kapitel über Rekursion als Beispiel.

Für die Zahl der Züge z(n) ergibt sich die Rekursionsgleichung z(n) = 2 · z(n - 1) + 1 mit z(1) = 1. Kürzer geht es nicht, wie das Plus Magazine der University of Cambridge begründet: Die größte Scheibe muss mindestens einmal ziehen, und vorher müssen alle anderen auf dem dritten Stab stehen. Danach müssen sie wieder auf sie. Wegräumen und Zurückholen kosten je mindestens z(n - 1) Züge.

Ein Problem des Monats im Mathematikzirkel des Hamburger Bildungsservers beweist z(n) = 2ⁿ - 1 durch vollständige Induktion. Der Induktionsanfang ist z(1) = 2¹ - 1 = 1, der Induktionsschritt rechnet 2 · (2ⁿ - 1) + 1 = 2ⁿ⁺¹ - 1.

Die Zahl der Züge wächst also exponentiell. In der kürzesten Lösung zieht jede Scheibe doppelt so oft wie die nächstgrößere: Bei fünf Scheiben sind es 16-mal, 8-mal, 4-mal, 2-mal und 1-mal, von der kleinsten bis zur größten. Bei 64 Scheiben hat die Mindestzahl bereits 20 Stellen.

Statt mit einem vollen Turm kann jedes Spiel auch aus einer zufälligen Stellung beginnen. Jede Scheibe liegt dann auf irgendeinem Stab, auf jedem Stab der Größe nach geordnet, und alle Scheiben sollen zu einem Turm auf dem Zielstab zusammenfinden.

Alle Verteilungen sind gleich wahrscheinlich, mit einer Ausnahme: Die größte Scheibe liegt nie schon auf dem Zielstab, sie muss also mindestens einmal ziehen. Deshalb braucht jede Zufallsstellung mindestens 2ⁿ⁻¹ und höchstens 2ⁿ - 1 Züge, bei 4 Scheiben also 8 bis 15. Im Schnitt aller erlaubten Startstellungen sind es 12,7, nach eigener Rechnung dieser Seite.

Gelost wird erst, wenn jemand auf „Zufällige Stellung auslosen“ tippt. Danach steht die Stellung im Link der Seite, sodass ein geteilter Link dieselbe Ausgangslage öffnet. Partien aus einer zufälligen Stellung zählen nie als Bestwert.

Insgesamt können n Scheiben bei drei Stäben 3ⁿ verschiedene Stellungen einnehmen, bei fünf Scheiben 243, bei zehn schon 59.049. Verbindet man jede Stellung mit allen, die ein einziger Zug erreicht, gleicht dieser Zustandsgraph mit jeder Scheibe mehr dem Sierpiński-Dreieck. Das zeigen das Plus Magazine und das Buch von Hinz, Klavžar und Petr.

Darf auch die größte Scheibe überall liegen, ist die Stellung also völlig zufällig, braucht der Turm im Schnitt zwei Drittel von 2ⁿ - 1 Zügen. Bei fünf Scheiben sind das 20,7. Auch diese Zahl stammt aus einer vollständigen Zählung dieser Seite über alle Stellungen.

„Tipp“ zeigt von jeder Stellung aus den nächsten Zug eines kürzesten Wegs zum Ziel. Beide Stäbe leuchten auf, und die Meldung lautet etwa „Tipp: Scheibe 2 von A nach C“. Jeder Tipp wird im Ergebnis gezählt.

„Lösen“ übergibt an den automatischen Löser, der vom aktuellen Stand aus fertig spielt. Zwischen zwei Zügen wartet er je nach Tempo 0,9, 0,45, 0,16 oder 0,045 Sekunden. Er lässt sich anhalten, Zug um Zug weiterschalten oder mit „Selbst weiterspielen“ an jeder Stelle zurückgeben. Folgt ein Spiel vom vollen Turm aus noch der Zugliste, setzt der Löser genau diese Liste fort.

Erfunden hat das Spiel der französische Mathematiker Édouard Lucas, der es 1883 als „la Tour d'Hanoï, véritable casse-tête annamite“ herausbrachte. Angeblich hatte es ein „professeur N. Claus (de Siam), mandarin du collège Li-Sou-Stian“ aus Tonkin mitgebracht. So zitieren Allardice und Fraser eine Notiz im Journal des Débats vom 27. Dezember 1883.

Der Name ist ein Versteckspiel. Nach MacTutor, dem Geschichtsarchiv der University of St Andrews, ergibt N. Claus de Siam umgestellt Lucas d'Amiens. Li-Sou-Stian steht für Saint Louis, das Lycée, an dem Lucas unterrichtete. Lucas selbst schrieb, das Spiel sei nicht aus Tonkin gekommen, was auch immer der Prospekt behaupte; Spiel und Legende seien in der Pariser Rue Monge entstanden. In einem späteren Buch nannte Lucas selbst 1884 als Jahr.

Das Originalspiel bestand aus 8 in der Mitte durchbohrten Holzscheiben auf einem von drei Stiften, die auf einem Brettchen steckten. So beschreibt es Lucas im 3. Band seiner Récréations mathématiques von 1893. Mit der Stadt Hanoi verbindet das Spiel also nur sein Name.

Die Legende lag schon dem Spiel von 1883 bei. Im großen Tempel von Benares in Indien, so erzählt sie, setzen Priester, die Brahmanen, Tag und Nacht den heiligen Turm des Brahma um. Er besteht aus 64 Scheiben aus reinem Gold auf drei Diamantnadeln. Sie bewegen immer nur eine Scheibe und legen nie eine größere auf eine kleinere. Ist der Turm versetzt, stürzen Turm und Brahmanen ein, und es folgt der Weltuntergang.

Es ist Lucas' eigene Legende, eine erfundene Geschichte und keine alte Überlieferung. Ein Arbeitsblatt aus dem Online-Labor der Didaktik der Mathematik am Karlsruher Institut für Technologie hält knapp fest, „Lucas erfand eine Geschichte dazu“. Henri de Parville erzählte sie in der Zeitschrift La Nature nach, wie W. W. Rouse Ball in seinen Mathematical Recreations and Essays festhält.

Lucas beschrieb auch ein Papierspiel, das in Deutschland als Käsekästchen bekannt ist: 1883 als „le jeu de l'École Polytechnique“ und 1889 als „La Pipopipette“.

In der Psychologie dienen Turmaufgaben dazu, Planung und Problemlösen zu untersuchen. Das Plus Magazine bringt den Reiz auf eine Formel: Bei solchen Aufgaben könne man Menschen beim Denken zusehen.

Tim Shallice beschrieb in den Philosophical Transactions of the Royal Society eine Aufgabe, mit der sich Störungen des Planens untersuchen lassen. Eine Studie der Erasmus-Universität Rotterdam nennt den Turm von London ein weit verbreitetes Instrument, um die Fähigkeit zur Planung zu erfassen. Eine Metaanalyse von Sullivan, Riccio und Castillo prüft Turmaufgaben als Maß exekutiver Funktionen bei Erwachsenen.

Im deutschsprachigen Raum vertreibt der Hogrefe Verlag mit dem TL-D eine deutsche Version des Turms von London von Tucha und Lange, für Kinder und Jugendliche sowie für Erwachsene. Abgegeben wird sie nur gegen den Nachweis einer fachlichen Qualifikation.

Das Spiel auf dieser Seite ist ein Rätsel und kein Messinstrument. Züge, Zeit und Bestwerte dienen dem eigenen Vergleich und sagen nichts über Intelligenz, Konzentration oder eine Diagnose. Ein anderes bekanntes Experiment aus der Psychologie gibt es hier zum Ausprobieren: den Stroop-Test mit deutschen Farbwörtern.