Türme von Hanoi: Ein Rätsel erklärt die Welt der Algorithmen
Türme von Hanoi: Ein einfaches Puzzle mit großer technischer Bedeutung für Rekursion, Algorithmen und systematisches Denken.
Das Türme-von-Hanoi-Rätsel: Drei Stäbe, mehrere Scheiben – Ziel ist es, den Turm nach festen Regeln von Stab A auf Stab C zu versetzen.
Foto: Smarterpix / markrhiggins
Die Türme von Hanoi gehören zu den Klassikern der mathematischen Rätselwelt. Was auf den ersten Blick wie ein Kinderspiel aussieht, ist in Wahrheit ein Fenster in die Grundlagen der Informatik und Ingenieurwissenschaften. Hinter den simplen Regeln steckt ein mächtiges Prinzip: Rekursion. Wer das versteht, begreift nicht nur, wie ein Rätsel gelöst wird, sondern auch, wie Computer, Robotiksysteme oder selbst Speicherstrukturen funktionieren.
Inhaltsverzeichnis
Ursprung: Eine Legende aus Hanoi
Das bekannte Rätsel „Türme von Hanoi“ geht auf den französischen Mathematiker Édouard Lucas (1842–1891) zurück. Lucas, der für seine Arbeiten zur Zahlentheorie berühmt war, erfand das Spiel im Jahr 1883 und ließ es als Brettspiel unter dem Namen Tour d’Hanoï vermarkten. Um dem eher abstrakten mathematischen Problem einen geheimnisvollen Reiz zu verleihen, erfand Lucas eine Legende, die er dem Spiel beilegte:
In einem sagenumwobenen Tempel in Hanoi, so die Geschichte, stehen drei Stäbe aus reinem Diamant. Auf dem ersten Stab liegen 64 goldene Scheiben, ordentlich nach Größe sortiert, die größte unten, die kleinste ganz oben. Tag und Nacht sollen unermüdliche Priester oder Mönche an dieser Aufgabe arbeiten:
Sie müssen die Scheiben – nach den bekannten Regeln, dass immer nur eine Scheibe bewegt werden darf und niemals eine größere auf einer kleineren liegen darf – von einem Stab auf einen anderen umschichten.
Die Legende steigert die Dramatik, indem sie ein apokalyptisches Ende andeutet: Sobald alle 64 Scheiben ordnungsgemäß umgesetzt sind, endet die Welt.
Die Zahl der Züge ist gewaltig:
264−1=18.446.744.073.709.551.615
In Worten: achtzehn Trillionen, vierhundertsechsundvierzig Trilliarden, siebenhundertvierundvierzig Billionen, dreiundsiebzig Milliarden, siebenhundertneuntausendfünfhunderteinundfünfzigtausendsechshundertfünfzehn.
Selbst wenn die Mönche jede Sekunde eine Scheibe bewegten, wären das rund 585 Milliarden Jahre. Zum Vergleich: Das Universum ist derzeit etwa 13,8 Milliarden Jahre alt.
Die Regeln – und warum sie faszinieren
Das Rätsel besteht aus drei Stäben und n Scheiben. Zu Beginn liegen alle Scheiben geordnet auf Stab A – die größte unten, die kleinste oben. Ziel ist es, den gesamten Turm auf Stab C umzusetzen. Dabei gelten zwei einfache Regeln: Es darf immer nur eine Scheibe pro Zug bewegt werden, und niemals darf eine größere Scheibe auf einer kleineren liegen.
Schon bei wenigen Scheiben steigt die Komplexität rasant:
- 3 Scheiben → 7 Züge
- 4 Scheiben → 15 Züge
- 10 Scheiben → 1.023 Züge
- 20 Scheiben → über 1 Million Züge
Das Spiel ist damit ein perfektes Beispiel für exponentielles Wachstum – eine Art „Mathematik zum Anfassen“.
Der Algorithmus: Rekursion in Reinform
Die Türme von Hanoi sind ein Paradebeispiel für rekursive Algorithmen.
Das Grundprinzip lautet:
- Um n Scheiben zu bewegen, verschiebe zunächst n−1 Scheiben auf den Hilfsstab.
- Dann bewege die größte Scheibe auf das Ziel.
- Anschließend verschiebe die n−1 Scheiben vom Hilfsstab auf das Ziel.
Diese Selbstähnlichkeit – das große Problem in kleinere, gleichartige Teilprobleme zu zerlegen – ist das Herzstück der Rekursion.
Formel für die minimalen Züge:
Z(n)=2n−1
Damit wächst die Zahl der Züge exponentiell mit der Anzahl der Scheiben. Ingenieurinnen und Ingenieure erkennen sofort: Solche Wachstumsraten führen in der Praxis schnell an physikalische oder zeitliche Grenzen.
Beispiel: Drei Scheiben Schritt für Schritt
Ausgangslage: Drei Scheiben auf Stab A. Ziel: Turm vollständig nach C. Hilfsstab: B.
- A → C (Scheibe 1)
- A → B (Scheibe 2)
- C → B (Scheibe 1)
- A → C (Scheibe 3)
- B → A (Scheibe 1)
- B → C (Scheibe 2)
- A → C (Scheibe 1)
Nach 7 Zügen liegt der gesamte Turm korrekt auf Stab C.
Das Muster ist erkennbar: Die kleinste Scheibe bewegt sich bei jedem ungeraden Zug, die größeren folgen in einem klaren Schema.
Minimaler Programmcode (Python-Beispiel)
Das obige Beispiel lässt sich recht einfach programmieren. Schon wenige Zeilen Python reichen, um den gesamten Lösungsweg auszugeben:
Dieses Ergebnis wird ausgegeben:
Praxisnahe Anwendungen
Was wie ein Spiel wirkt, findet überraschend viele Analogien in der Technik:
- Informatik und Softwareentwicklung
Die Türme von Hanoi sind das Standardbeispiel, um Studierenden Rekursion beizubringen. Schon ein paar Zeilen Python- oder C-Code reichen, um den kompletten Lösungsweg automatisch auszugeben. Der Algorithmus ist so schlicht wie elegant.
Darüber hinaus taucht das Prinzip beim Sortieren, bei Dateisystemen oder in Backup-Strategien auf: Daten müssen oft schrittweise umorganisiert werden, wobei Regeln (ähnlich den Spielregeln) beachtet werden müssen.
- Robotik
Industrieroboter, die Bauteile stapeln oder in bestimmter Reihenfolge bewegen, lösen faktisch eine Art Hanoi-Problem. Besonders dann, wenn Platz begrenzt ist und nur bestimmte Bewegungen erlaubt sind. Für Ingenieurinnen und Ingenieure in der Automatisierung ist der Bezug unmittelbar.
- Netzwerke und Speicherarchitektur
Bei der Optimierung von Speichervorgängen oder beim Auslagern von Prozessen (Caching) tauchen ähnliche Strukturen auf. Es geht immer um die Frage: Welche „Scheibe“ (also welcher Prozess oder Speicherblock) darf wohin verschoben werden, ohne dass eine Regel verletzt wird?
- Didaktik der Elektrotechnik
Die exponentielle Wachstumskurve des Rätsels eignet sich hervorragend, um technische Phänomene zu illustrieren – etwa das Laden und Entladen eines Kondensators oder das Wachstum von Schaltungen. Das abstrakte Prinzip wird so anschaulich greifbar.
Ein Beitrag von:
