Türme-von-Hanoi-Rechner

Wie lang das wirklich ist

Die Zahlen oben sind exakt, und für sich genommen lehren sie fast nichts: Jenseits einiger Milliarden sieht eine sehr große Zahl aus wie die nächste. Was die Rechnung wirklich tut, sieht man leichter, als man es sagt. Weil jede zusätzliche Scheibe die Arbeit verdoppelt, ist ein Lineal mit gleichmäßig verteilten Scheiben ein Lineal mit sich vervielfachenden Zeitspannen — und der ganze Weg von einer Kaffeepause (zehn Scheiben, siebzehn Minuten) bis zum Alter des Universums (neunundfünfzig Scheiben) sind am Ende etwa fünfzig Schritte.

• 1 Scheibe — 1 Zug — 1 Sekunde: die erste Größe, die eine Sekunde erreicht.
• 6 Scheiben — 63 Züge — 1 Minute: die erste Größe, die eine Minute erreicht.
• 12 Scheiben — 4.095 Züge — 1 Stunde: die erste Größe, die eine Stunde erreicht.
• 17 Scheiben — 131.071 Züge — 1 Tag: die erste Größe, die ein Tag erreicht.
• 25 Scheiben — 33.554.431 Züge — 1 Jahr: die erste Größe, die ein Jahr erreicht.
• 32 Scheiben — 4.294.967.295 Züge — 136 Jahre: die erste Größe, die ein Menschenleben erreicht.
• 38 Scheiben — 274.877.906.943 Züge — 8,71 Tausend Jahre: die erste Größe, die die gesamte überlieferte Geschichte erreicht.
• 59 Scheiben — 576.460.752.303.423.487 Züge — 18,3 Milliarden Jahre: die erste Größe, die das Alter des Universums erreicht.

Der schattierte Abschnitt links ist alles, was Sie hier wirklich spielen können. Elf Scheiben sind eine lange Sitzung; fünfundzwanzig sind ein Jahr ununterbrochener Züge; neunundfünfzig übertreffen das Alter des Universums. An den Regeln ändert sich entlang dieser Achse nichts — nur die Zahl wächst.

Die Formel

Ein perfektes Spiel mit n Scheiben braucht genau 2ⁿ − 1 Züge — die Formel der Türme von Hanoi, oft als 2^n − 1 geschrieben, wo keine Hochzahlen zur Hand sind. Das ist nicht das Beste, was jemand geschafft hat, sondern eine bewiesene Untergrenze. Damit die größte Scheibe überhaupt ziehen kann, müssen alle kleineren aus dem Weg auf den Hilfsturm gestapelt sein, und sobald sie drüben ist, müssen sie alle wieder obenauf. Zwei vollständige Umschichtungen von n − 1 Scheiben, plus ein Zug:

T(n) = 2·T(n − 1) + 1, ausgehend von T(0) = 0 — keine Scheiben, keine Züge.

1. 1Die n−1 Scheiben darüber auf den Hilfsturm legen. Nichts anderes geht, solange sie im Weg liegen.

2. 2Die größte Scheibe ist jetzt frei, und ihr Zielturm ist leer. Sie wechselt mit einem einzigen Zug – dem einzigen, den diese Phase braucht.

3. 3Den Stapel aus n−1 Scheiben darauf wieder aufbauen. Das ist dasselbe Problem mit einer Scheibe weniger, bis hinunter zu einer einzelnen Scheibe, die sich in einem Zug bewegt.

Ausgerollt ergibt das 1, 3, 7, 15, 31, 63 — jede Zahl das Doppelte der vorigen plus eins, also die Folge der Zahlen, die eins unter einer Zweierpotenz liegen. Jede Scheibe mehr macht die Arbeit etwas mehr als doppelt so groß, und deshalb reicht das Rätsel in weniger als fünfzig Schritten von einer Kaffeepause bis über das Alter des Universums hinaus.

Dieselbe Rekursionsgleichung ist der Grund für den Ruf des Rätsels in Informatikvorlesungen. Weil sich die Arbeit mit jeder Scheibe verdoppelt, läuft die rekursive Lösung in O(2ⁿ) Zeit — dahinter versteckt sich kein klügerer Algorithmus, denn die Zugzahl selbst ist exponentiell und jeder Zug muss ausgegeben werden. Was sie nicht kostet, ist Speicher: Die Rekursion steigt immer nur um eine Scheibe ab und hält daher O(n) Stapelrahmen — einen je Scheibe plus einen für den Basisfall: sechzehn für das größte Brett hier, fünfundsechzig für die Legende. Die vollständige Herleitung, und warum das keine Rekursionsgleichung für das Master-Theorem ist, steht auf der Seite zum Algorithmus der Türme von Hanoi.

Minimale Zugzahl nach Scheibenzahl

Das sind die Größen, die Sie hier spielen können. Die Schwierigkeitsstufe ist dieselbe, die das Brett neben der Scheibenwahl anzeigt, und jede Scheibenzahl führt zu der Zugliste, die sie löst.

Jenseits des Bretts

Über 15 Scheiben hinaus hört das Rätsel auf, etwas zum Spielen zu sein, und wird etwas zum Rechnen. Die Zahlen bleiben exakt — sie sind nur in einem Menschenleben nicht mehr erreichbar.

Diese Zahlen haben einen Namen

Eine Zahl, die eins unter einer Zweierpotenz liegt, ist eine Mersenne-Zahl, geschrieben M_n = 2ⁿ − 1 — jede Zahl in den Tabellen oben ist also eine, und die Zugzahl eines Spiels der Türme von Hanoi ist nie etwas anderes. Ist eine Mersenne-Zahl zufällig prim, heißt sie Mersenne-Primzahl, und auf genau diesen Zahlen läuft die Suche nach Rekordprimzahlen seit Jahrzehnten, weil sich 2ⁿ − 1 weit billiger auf Primalität prüfen lässt als eine beliebige Zahl dieser Größe.

M_n kann nur prim sein, wenn auch n prim ist, aber das allein genügt nicht — und das Gegenbeispiel ist ein Spiel, das Sie hier spielen können. Elf ist prim; seine 2.047 Züge sind es nicht, denn 2.047 = 23 × 89. Von den Größen auf diesem Brett sind es 3, 5, 7 und 13 Scheiben, deren Zugzahlen prim sind. OEIS A000225 ist die vollständige Folge.

Die Legende der vierundsechzig Scheiben

Das Rätsel kam 1883 in den Handel, und binnen eines Jahres hatte es eine Geschichte: In einem Tempel in Benares bewegen Priester vierundsechzig goldene Scheiben zwischen drei Diamantnadeln, und wenn die letzte Scheibe liegt, endet die Welt. Die Rechnung beruhigt. Vierundsechzig Scheiben brauchen 18.446.744.073.709.551.615 Züge, und bei einem Zug pro Sekunde sind das 585 Milliarden Jahre — etwa vierzigmal das heutige Alter des Universums.

Häufige Fragen

Wie viele Züge braucht man bei den Türmen von Hanoi?

Das Minimum sind 2ⁿ − 1 Züge für n Scheiben. Drei Scheiben brauchen 7, fünf brauchen 31, zehn brauchen 1.023 und zwanzig brauchen 1.048.575. Jede zusätzliche Scheibe macht die Summe etwas mehr als doppelt so groß, denn n Scheiben zu lösen heißt, n − 1 Scheiben zweimal zu lösen, mit einem Zug dazwischen.

Warum lautet die Formel 2ⁿ − 1?

Um n Scheiben zu bewegen, müssen Sie erst die oberen n − 1 aus dem Weg räumen, dann die größte Scheibe einmal bewegen, dann jene n − 1 wieder obenauf bringen. Das ergibt T(n) = 2·T(n−1) + 1 mit T(1) = 1, und ausgerollt 1, 3, 7, 15, 31 — jeweils das Doppelte plus eins, also genau 2ⁿ − 1.

Welche Zeitkomplexität haben die Türme von Hanoi?

O(2ⁿ). Jede Scheibe verdoppelt die Arbeit, also macht die rekursive Lösung 2ⁿ − 1 Züge, und kein Algorithmus kann das unterbieten: Die Züge müssen erzeugt werden, und es sind so viele. Der Platzbedarf ist nur O(n): Die Rekursion steigt Scheibe für Scheibe ab und hält höchstens n + 1 Stapelrahmen gleichzeitig — deshalb würde ein Aufruf mit 64 Scheiben Ihre Geduld weit vor dem Stapel erschöpfen.

Wie lange würden 64 Scheiben dauern?

Vierundsechzig Scheiben brauchen 18.446.744.073.709.551.615 Züge. Bei einem Zug pro Sekunde sind das 585 Milliarden Jahre — weit mehr als das heutige Alter des Universums, und genau darauf zielt die Legende, die dem Rätsel 1884 beigegeben wurde.

Kann eine Lösung je kürzer sein als 2ⁿ − 1?

Nein. 2ⁿ − 1 ist eine bewiesene Untergrenze, kein bloßer Bestwert: Die größte Scheibe muss mindestens einmal ziehen, und bevor sie das kann, müssen alle kleineren weder auf ihr noch auf ihrem Ziel liegen. Das erzwingt die beiden Teilumschichtungen, und das Argument wiederholt sich bis ganz nach unten.

Funktioniert der Rechner für ein halb gelöstes Brett?

Diese Seite nicht — 2ⁿ − 1 setzt voraus, dass alle Scheiben auf einem Turm beginnen. Für die kürzeste Lösung aus einer Stellung, die schon halb fertig ist, nehmen Sie den Löser, der den optimalen Weg aus jeder erlaubten Anordnung berechnet. Den Löser öffnen →