Türme von Hanoi: Lösung, Formel 2^n - 1 und die Mathematik dahinter

Von Dawid Siedlarz · · 8 Min. Lesezeit

Türme von Hanoi kostenlos spielen →

Kurz gesagt: Die Türme von Hanoi mit n Scheiben und drei Stäben brauchen mindestens 2n − 1 Züge: 7 bei 3 Scheiben, 15 bei 4, 31 bei 5, 127 bei 7. Zur Lösung setzen Sie die oberen n − 1 Scheiben auf den freien Stab, die größte Scheibe auf den Zielstab und dann die n − 1 Scheiben darauf, also dasselbe Rätsel noch einmal, nur kleiner. Die schnelle Regel: Die kleinste Scheibe zieht jeden zweiten Zug, immer in dieselbe Richtung, dazwischen macht man den einzigen anderen erlaubten Zug. Erfunden hat das Rätsel Édouard Lucas im Jahr 1883.

Die Türme von Hanoi sehen aus wie Spielzeug: drei Stäbe und ein Stapel Scheiben, die nach oben kleiner werden. Der ganze Stapel soll auf einen anderen Stab, Scheibe für Scheibe, ohne je eine größere auf eine kleinere zu legen. Mit 3 Scheiben dauert das eine Minute. Mit 7 braucht es Konzentration. Mit 64 würde es die Sonne überdauern. Hinter diesem einfachen Rätsel stecken eines der saubersten Beispiele für Rekursion in der Mathematik, ein versteckter Binärzähler und ein Fraktal. Zuerst die Lösung, dann die Mathematik.

Die Regeln

  1. Es gibt drei Stäbe. Alle Scheiben liegen zu Beginn auf einem Stab, die größte unten.
  2. Es wird immer nur eine Scheibe bewegt: die oberste Scheibe eines Stabs auf einen anderen Stab.
  3. Eine Scheibe darf nie auf einer kleineren liegen.
  4. Gelöst ist das Rätsel, wenn der ganze Turm in derselben Reihenfolge auf dem Zielstab steht.

In unserem Spiel Türme von Hanoi beginnt der Turm auf dem linken Stab und muss auf den rechten. „Leicht“ hat 3 Scheiben, „Mittel“ 5 und „Schwer“ 7. Es gibt kein Zeitlimit, und das Spiel zeigt neben Ihrer Zugzahl die kleinstmögliche an.

Die Lösung mit 3 Scheiben, Zug für Zug

Nennen wir die Stäbe A (Start, links), B (Mitte) und C (Ziel, rechts) und die Scheiben 1 (klein), 2 (mittel) und 3 (groß). Die kürzeste Lösung hat 7 Züge:

ZugScheibeVon → nachDanach (A | B | C)
11A → C3 2 | – | 1
22A → B3 | 2 | 1
31C → B3 | 2 1 | –
43A → C– | 2 1 | 3
51B → A1 | 2 | 3
62B → C1 | – | 3 2
71A → C– | – | 3 2 1

Achten Sie auf die Struktur. Die Züge 1 bis 3 bringen einen Zwei-Scheiben-Turm von A nach B. Zug 4 bewegt die große Scheibe. Die Züge 5 bis 7 setzen den Zwei-Scheiben-Turm von B darauf. Darin liegt das ganze Geheimnis.

Zwei Wege für jeden Turm

1. Die rekursive Methode (in Türmen denken)

Um einen Turm aus n Scheiben vom Start- auf den Zielstab zu bringen:

  1. Setzen Sie die oberen n − 1 Scheiben vom Start auf den freien Stab (der Zielstab dient als Hilfsstab).
  2. Setzen Sie die größte Scheibe vom Start auf das Ziel.
  3. Setzen Sie die n − 1 Scheiben vom freien Stab auf das Ziel (der Start dient als Hilfsstab).

Schritt 1 und 3 sind dasselbe Rätsel mit einer Scheibe weniger, also wendet man darauf wieder dieselben drei Schritte an, und so weiter bis zu einer einzigen Scheibe, die man einfach bewegt. Deshalb sind die Türme von Hanoi das klassische erste Beispiel für Rekursion in Programmierkursen: eine Funktion, die ein Problem löst, indem sie sich selbst für eine kleinere Version aufruft. Es ist auch der beste Weg, jede Stellung zu verstehen: Fragen Sie, welche größte Scheibe noch nicht am Ziel ist; alles darüber muss auf den dritten Stab.

2. Die iterative Methode (ohne Planen)

  1. Bei jedem ungeraden Zug (1., 3., 5. …) bewegen Sie die kleinste Scheibe einen Stab weiter, immer in dieselbe Richtung. Bei ungerader Scheibenzahl lautet die Richtung A → C → B → A (Start, Ziel, Mitte), bei gerader A → B → C → A.
  2. Bei jedem geraden Zug machen Sie den einzigen erlaubten Zug, der die kleinste Scheibe nicht berührt. Es gibt immer genau einen.

Wer diese zwei Regeln befolgt, ist ohne Vorausdenken in der kleinstmöglichen Zugzahl fertig. So lösen die meisten Menschen 7 Scheiben. Die rekursive Methode erklärt, warum es funktioniert.

Warum das Minimum 2n − 1 ist

Sei T(n) die kleinste Zugzahl für n Scheiben. Die größte Scheibe muss mindestens einmal ziehen. In diesem Moment muss sie allein auf ihrem Stab liegen und der Zielstab leer sein, also liegen alle anderen n − 1 Scheiben auf dem dritten Stab: Das kostete mindestens T(n − 1) Züge. Danach müssen diese Scheiben noch auf sie: wieder mindestens T(n − 1) Züge. Also gilt

T(n) = 2 × T(n − 1) + 1 mit T(1) = 1.

Das ergibt 1, 3, 7, 15, 31, 63, 127 … und jede Zahl ist um eins kleiner als eine Zweierpotenz: T(n) = 2n − 1. Die rekursive Methode erreicht genau diese Zahl und ist damit optimal; die kürzeste Lösung ist sogar eindeutig: Es gibt nur einen Weg, es in 2n − 1 Zügen zu schaffen.

Wie schnell das wächst

ScheibenKleinste ZugzahlBei einem Zug pro Sekunde
377 Sekunden
41515 Sekunden
531etwa eine halbe Minute
663etwa 1 Minute
7127etwa 2 Minuten
8255etwa 4 Minuten
101.023etwa 17 Minuten
201.048.575etwa 12 Tage
324.294.967.295etwa 136 Jahre
6418.446.744.073.709.551.615etwa 585 Milliarden Jahre

Jede zusätzliche Scheibe verdoppelt die Arbeit. So sieht exponentielles Wachstum aus, und deshalb wird es mit diesem Rätsel unterrichtet.

Versteckte Muster

Welche Scheibe wann zieht: ein Binärzähler

In der kürzesten Lösung zieht Scheibe k (von der kleinsten aus gezählt) genau 2n−k-mal. Die kleinste Scheibe macht die Hälfte aller Züge (aufgerundet), die größte zieht einmal, genau in der Mitte: nach 3 Zügen bei 3 Scheiben, nach 15 bei 5, nach 63 bei 7.

Es gibt eine noch elegantere Regel. Schreiben Sie die Zugnummer binär und zählen Sie die Nullen am Ende: Zug 1 ist 1 (keine Null, Scheibe 1), Zug 2 ist 10 (eine Null, Scheibe 2), Zug 3 ist 11 (Scheibe 1), Zug 4 ist 100 (zwei Nullen, Scheibe 3). Es zieht immer die Scheibe mit der Nummer „Anzahl der Endnullen plus eins“. Die Lösung ist also buchstäblich ein Binärzähler von 0 bis 2n − 1, und schon die Zugnummer verrät, welche Scheibe dran ist. Dieselbe Folge (1, 2, 1, 3, 1, 2, 1 …) ist die Reihenfolge, in der sich die Bits im Gray-Code ändern, einer Binärzählweise, bei der sich pro Schritt nur ein Bit ändert.

Ein Fraktal: das Sierpiński-Dreieck

Jede Scheibe kann auf jedem der drei Stäbe liegen, und die Reihenfolge auf einem Stab ist vorgegeben (die größte unten), also gibt es genau 3n erlaubte Stellungen: 27 bei 3 Scheiben, 2.187 bei 7. Zeichnet man jede Stellung als Punkt und verbindet zwei Punkte, wenn ein erlaubter Zug von der einen zur anderen führt, entsteht ein Dreieck aus drei kleineren Dreiecken, die wiederum aus drei kleineren bestehen: eine Form des Sierpiński-Dreiecks. Die drei Ecken sind die Stellungen mit dem ganzen Turm auf einem Stab, und die kürzeste Lösung läuft geradewegs an einer Seite entlang.

Unsere drei Stufen sind Primzahlen

Zahlen der Form 2n − 1 heißen Mersenne-Zahlen. Manche sind Primzahlen, und das gilt für die Mindestzugzahlen aller drei Stufen unseres Spiels: 7, 31 und 127. Die letzte führt zurück zum Erfinder des Rätsels: 1876 bewies Édouard Lucas, dass 2127 − 1, eine 39-stellige Zahl, eine Primzahl ist. Sie blieb 75 Jahre lang, bis 1951, die größte bekannte Primzahl, und der auf seiner Methode beruhende Lucas-Lehmer-Test wird bis heute für die Suche nach Rekord-Primzahlen verwendet.

Vier Stäbe: ein viel schwierigeres Problem

Mit einem vierten Stab lässt sich der Turm viel schneller umsetzen, weil es mehr Ablageplätze gibt. Die Variante mit vier Stäben veröffentlichte Henry Dudeney 1907 in The Canterbury Puzzles als „The Reve's Puzzle“. 1941 gaben J. S. Frame und B. M. Stewart unabhängig voneinander eine Methode an: einige obere Scheiben mit allen vier Stäben auf einen freien Stab setzen, den Rest mit den drei übrigen Stäben umsetzen und dann die erste Gruppe wieder obenauf. Die beste Aufteilung ergibt diese Zugzahlen:

Scheiben3 Stäbe4 Stäbe (Frame-Stewart)
375
4159
53113
66317
712725
825533
101.02349

Über 70 Jahre lang konnte niemand beweisen, dass diese Methode für vier Stäbe die bestmögliche ist. Erst Thierry Bousch gelang der Beweis 2014. Für fünf und mehr Stäbe ist die Frage weiterhin offen, bemerkenswert für ein Rätsel, das 1883 als Spielzeug verkauft wurde.

Geschichte: Lucas, ein Pseudonym und eine Legende

Das Rätsel erschien 1883 in Paris, angeblich von „Professor N. Claus de Siam“ vom „Kollegium Li-Sou-Stian“. Beides sind Anagramme: N. Claus de Siam ist Lucas d'Amiens, und Li-Sou-Stian ist Saint Louis, das Lycée Saint-Louis, an dem Édouard Lucas Mathematik unterrichtete. Lucas (1842–1891) ist auch für die Lucas-Zahlen bekannt, eine Verwandte der Fibonacci-Folge, und für eine vierbändige Sammlung mathematischer Unterhaltungen.

Zum Rätsel gehörte eine Legende: In einem großen Tempel setzen Priester einen Turm aus 64 goldenen Scheiben zwischen drei Diamantnadeln um, nach denselben zwei Regeln, und wenn sie fertig sind, geht die Welt unter. Wie die Tabelle oben zeigt, bräuchten sie selbst bei einem Zug pro Sekunde und ohne Fehler etwa 585 Milliarden Jahre, mehr als das 40-Fache des Alters des Universums. Die Legende gehörte wie der Name Hanoi zu Lucas' exotischer Verpackung und ist keine alte Überlieferung.

Wo die Türme von Hanoi heute verwendet werden

  • Programmierunterricht. Das klassische Übungsbeispiel für Rekursion; die Drei-Schritte-Methode oben wird zu einer Funktion von wenigen Zeilen.
  • Mathematikunterricht. Rekursionsgleichungen, vollständige Induktion, exponentielles Wachstum und Binärzahlen in einem einzigen Rätsel.
  • Psychologie. Turmaufgaben dienen zur Untersuchung von Planen und Problemlösen: wie weit jemand vorausdenkt, bevor er zieht. Eine Variante, der „Turm von London“, 1982 von Tim Shallice eingeführt, wird in der neuropsychologischen Diagnostik verwendet.
  • Datensicherung. Ein „Türme von Hanoi“-Rotationsschema für Sicherungsbänder nutzt dasselbe Muster 1, 2, 1, 3, 1, 2, 1, um zu entscheiden, welches Band überschrieben wird; so sind die letzten Tage dicht und ältere Zeiträume immer lockerer abgedeckt.

Tipps für unser Spiel

  • Beginnen Sie auf „Leicht“ und lösen Sie 3 Scheiben mit der iterativen Regel, bis sie sitzt; wechseln Sie dann bei 5 Scheiben zur rekursiven Methode.
  • Bei ungerader Scheibenzahl (alle unsere Stufen: 3, 5, 7) geht der erste Zug mit der kleinsten Scheibe auf den rechten Stab.
  • Prüfen Sie die Halbzeit: Wenn die größte Scheibe zieht, müssen alle anderen auf dem mittleren Stab liegen.
  • Bewegen Sie die kleinste Scheibe nie zweimal hintereinander; das ist immer ein verschenkter Zug.
  • Die Punktzahl ist 1.000 × kleinste Zugzahl ÷ Ihre Zugzahl, mal 1, 2 oder 4 je nach Stufe, ein perfekter Turm mit 7 Scheiben bringt also 4.000 Punkte. Ein zurückgenommener Zug zählt als Zug.

Wer gern Rätsel löst, bei denen sich vorausschauendes Planen lohnt, sollte auch Kisten schieben (eine Sokoban-Variante) und das Schiebepuzzle ausprobieren.

Häufige Fragen

Wie viele Züge braucht man mindestens für die Türme von Hanoi?

Bei n Scheiben und drei Stäben sind es mindestens 2 hoch n minus 1: 7 Züge für 3 Scheiben, 15 für 4, 31 für 5, 63 für 6 und 127 für 7. Jede weitere Scheibe verdoppelt die Zahl der Züge und addiert eins.

Wie löst man die Türme von Hanoi mit 3 Scheiben?

Mit den Stäben A (Start), B (Mitte) und C (Ziel): kleine Scheibe von A nach C, mittlere von A nach B, kleine von C nach B, große von A nach C, kleine von B nach A, mittlere von B nach C und kleine von A nach C. Das sind 7 Züge, das Minimum.

Was ist der Trick bei den Türmen von Hanoi?

Bewegen Sie bei jedem ungeraden Zug die kleinste Scheibe einen Stab weiter, immer in dieselbe Richtung (bei ungerader Scheibenzahl zuerst zum Zielstab, bei gerader zum mittleren Stab). Machen Sie bei jedem geraden Zug den einzigen erlaubten Zug, der die kleinste Scheibe nicht betrifft.

Wie lange würden 64 Scheiben dauern?

2 hoch 64 minus 1, also 18.446.744.073.709.551.615 Züge. Bei einem Zug pro Sekunde ohne einen einzigen Fehler sind das etwa 585 Milliarden Jahre, rund 40-mal das heutige Alter des Universums.

Wer hat die Türme von Hanoi erfunden?

Der französische Mathematiker Édouard Lucas, der das Spiel 1883 unter dem Pseudonym N. Claus de Siam verkaufte, einem Anagramm von Lucas d'Amiens. Er gab ihm die Legende von Priestern mit, die 64 goldene Scheiben umsetzen, bevor die Welt untergeht.