Die gewöhnlichen Türme von Hanoi haben drei Stäbe. Was passiert, wenn man einen Stab hinzufügt und vier hat? Die Regeln bleiben gleich: pro Zug eine Scheibe, nie eine große Scheibe auf eine kleinere, und der Turm kommt auf einen anderen Stab.

Ein Stab mehr, und die Zugzahl sinkt stark

Weil es einen Ablageplatz mehr gibt, ist das Beiseiteräumen der Scheiben viel leichter. Vergleicht man die Mindestzahl der Züge, wächst der Unterschied mit der Scheibenzahl.

ScheibenzahlMit drei StäbenMit vier Stäben
3 Scheiben7 Züge5 Züge
4 Scheiben15 Züge9 Züge
5 Scheiben31 Züge13 Züge
6 Scheiben63 Züge17 Züge
7 Scheiben127 Züge25 Züge
8 Scheiben255 Züge33 Züge
10 Scheiben1.023 Züge49 Züge
64 Scheibenetwa 18,4 Trillionen Züge18.433 Züge

Mit drei Stäben brauchen 64 Scheiben selbst bei einem Zug pro Sekunde etwa 584,5 Milliarden Jahre (Wie lange dauern 64 Scheiben?). Mit vier Stäben sind es 18.433 Züge, bei einem Zug pro Sekunde etwa 5 Stunden. Hätten die Mönche der Legende einen Stab hinzugefügt, wäre die Welt noch am selben Tag untergegangen.

Dudeneys „Käse-Rätsel“

Die Türme von Hanoi mit vier Stäben machte der englische Rätselautor Henry Dudeney bekannt. In seinem Buch „The Canterbury Puzzles“ von 1907 stellte er sie als „Reve’s Puzzle“ vor. Ein „Reve“ ist der Verwalter eines Gutshofs.

In Dudeneys Aufgabe werden statt der Scheiben 8 verschieden große Käse zwischen vier Hockern bewegt. Ein großer Käse darf nicht auf einem kleineren liegen. Die Lösung hat 33 Züge, genau wie bei 8 Scheiben in der Tabelle oben.

Das Verfahren von Frame und Stewart

Wie man mit vier Stäben mit wenigen Zügen auskommt, veröffentlichten 1941 J. S. Frame und B. M. Stewart unabhängig voneinander mit demselben Gedanken. Um einen Turm aus n Scheiben zu bewegen, teilt man ihn in drei Schritte auf:

  1. Die oberen k Scheiben mit allen vier Stäben auf einen Stab bewegen, der nicht der Zielstab ist.
  2. Die übrigen n − k Scheiben auf den Zielstab bewegen, nur mit drei Stäben und ohne den Stab mit den k Scheiben (2ⁿ⁻ᵏ − 1 Züge).
  3. Die k Scheiben aus Schritt 1 mit allen vier Stäben auf den Zielstab bewegen.

Schritt 1 und 3 sind kleinere Fassungen desselben Problems, also lässt sich der Gedanke der Rekursion nutzen (Artikel zum Algorithmus). Dann wählt man nur noch, wie viele Scheiben (k) oben bleiben, damit es am wenigsten Züge werden. Bei 8 Scheiben sind es am wenigsten, wenn man zuerst die oberen 4 oder 5 beiseiteräumt, nämlich 33 Züge.

Fast 100 Jahre unbewiesen: das „Mindeste“

Dass das Verfahren von Frame und Stewart mit wenigen Zügen auskommt, war bekannt. Ob es wirklich kein besseres Verfahren gibt, konnte aber lange niemand beweisen.

Bei drei Stäben lässt sich die Mindestzahl der Züge aus einer einzigen Tatsache sofort beweisen: Im Moment, in dem die größte Scheibe bewegt wird, müssen alle anderen auf einem Stab zusammen liegen (Formel für die Mindestzahl der Züge). Bei vier Stäben dürfen die anderen Scheiben in diesem Moment beliebig auf die zwei übrigen Stäbe verteilt sein, und so wächst die Zahl der denkbaren Zugfolgen schlagartig.

Mit dem Computer prüfte man alle Anordnungen und bestätigte, dass dieses Verfahren bis etwa 30 Scheiben das kürzeste ist. Und rund 100 Jahre nach Dudeneys Aufgabe bewies der französische Mathematiker Thierry Bousch 2014, dass das Verfahren von Frame und Stewart bei jeder Scheibenzahl das kürzeste ist. Für fünf oder mehr Stäbe gilt das bis heute als unbewiesen.

Selbst ausprobieren

Die Türme von Hanoi mit vier Stäben kannst du nach der Bastelanleitung aus dem Artikel zum Selbermachen bauen, wenn du vier Kreise als Ablageplätze zeichnest. Probiere aus, ob du 3 Scheiben in 5 Zügen und 4 Scheiben in 9 Zügen bewegen kannst. Den Unterschied zu drei Stäben spürst du dabei selbst.