Die Türme von Hanoi

„Die Türme von Hanoi“ ist ein klassisches mathematisches Rätsel, das aus drei Stäben und einem Satz Scheiben unterschiedlicher Größe besteht. Zu Beginn sind alle Scheiben auf einem Stab in absteigender Reihenfolge ihrer Größe gestapelt, wobei die größte unten und die kleinste oben liegt. Das Ziel besteht darin, den gesamten Stapel auf einen anderen Pfahl zu verschieben, wobei strenge Regeln für das Verschieben der Scheiben einzuhalten sind. Die Mindestanzahl an Zügen, die zur Lösung eines Rätsels mit N Scheiben erforderlich ist, beträgt 2^N – 1.

Regeln

1. Drei Stifte (oder Türme) werden nebeneinander aufgestellt.
2. Auf einem Stift sind mehrere Scheiben unterschiedlicher Größe gestapelt, geordnet von der größten (unten) zur kleinsten (oben).
3. Es darf jeweils nur eine Scheibe bewegt werden.
4. Jeder Zug besteht darin, die oberste Scheibe von einem Stab zu nehmen und sie auf einen anderen Stab zu legen.
5. Eine größere Scheibe darf niemals auf eine kleinere Scheibe gelegt werden.
6. Das Ziel ist es, den gesamten Stapel vom Startstab auf den Zielstab zu verschieben.

Strategien

• Rekursiver Ansatz: Um N Scheiben von Stab A auf Stab C zu verschieben und dabei Stab B als Hilfsstab zu nutzen: Verschiebe zunächst die obersten N-1 Scheiben von A nach B, dann die größte Scheibe von A nach C und schließlich die N-1 Scheiben von B nach C.
• Iteratives Muster: Bei ungeraden Zügen wird die kleinste Scheibe verschoben. Bei geraden Zügen wird der einzige zulässige Zug ausgeführt, bei dem die kleinste Scheibe nicht beteiligt ist. Die kleinste Scheibe bewegt sich immer in derselben Drehrichtung (A→B→C→A bei einer ungeraden Anzahl von Scheiben, A→C→B→A bei einer geraden).
• Binäre Zählung: Die Abfolge der Züge entspricht der binären Zählung. Die im Schritt K zu verschiebende Scheibe wird durch die Position des niedrigstwertigen gesetzten Bits in der binären Darstellung von K bestimmt.
• Klein anfangen: Übe zunächst mit 3 Scheiben (7 Züge), bevor du dich an größere Zahlen wagst. Das Muster wird intuitiv verständlich, sobald man sieht, wie es sich wiederholt.
• Frame-Stewart-Algorithmus: Für Varianten mit mehr als 3 Stiften liefert der Frame-Stewart-Algorithmus vermutete optimale Lösungen, wobei die Optimalität bisher nur für 4 Stifte bewiesen wurde.

Das Puzzle „Die Türme von Hanoi“ wurde 1883 vom französischen Mathematiker Edouard Lucas erfunden, der es unter dem Pseudonym „Professor N. Claus de Siam“ (ein Anagramm von „Lucas d’Amiens“) veröffentlichte. Das Rätsel wurde als Spielzeug verkauft, begleitet von einer Legende, wonach Brahmanenpriester in einem Tempel in Benares (Varanasi), Indien, an einer Version mit 64 goldenen Scheiben auf diamantenen Nadeln arbeiteten. Der Legende zufolge würde die Welt untergehen, sobald die Priester das Rätsel gelöst hätten. Bei einer optimalen Geschwindigkeit von einem Zug pro Sekunde würde die Version mit 64 Scheiben 2^64 – 1 Züge erfordern – also etwa 585 Milliarden Jahre, was weit länger ist als das geschätzte Alter des Universums.

Das Rätsel wurde schnell zu einem festen Bestandteil der Freizeitmathematik. Es war eines der ersten Rätsel, das mithilfe des damals aufkommenden Konzepts der Rekursion gründlich analysiert wurde, und es ist nach wie vor eines der wichtigsten Beispiele in der Informatikausbildung für die Vermittlung rekursiver Algorithmen, mathematischer Induktion und algorithmischer Komplexität.

Über seine Rolle als Lehrmittel hinaus weist das Rätsel der Türme von Hanoi tiefe Verbindungen zu anderen Bereichen der Mathematik auf. Der Zustandsraum des Rätsels bildet einen Sierpinski-Dreieck-Graphen, wodurch es mit der fraktalen Geometrie in Verbindung steht. Das Rätsel findet zudem Anwendung bei Backup-Rotationsschemata (der „Turm von Hanoi“-Backup-Strategie), bei Gray-Codes und bei der Analyse bestimmter Sortieralgorithmen.

Zu den Varianten des Puzzles gehören das Frame-Stewart-Problem (mit 4 oder mehr Stiften), farbige Varianten, bei denen die Scheiben in einer bestimmten Anordnung enden müssen, sowie zweifarbige Versionen, bei denen zwei miteinander verflochtene Scheibengruppen voneinander getrennt werden müssen. Das Rätsel wurde in zahlreiche Videospiele adaptiert und taucht als wiederkehrendes Rätselelement in Abenteuerspielen, Rollenspielen und Rätselsammlungen auf. Es spielte eine herausragende Rolle in der „Doctor Who“-Episode „The Celestial Toymaker“ aus dem Jahr 1966 und tauchte in Filmen wie „Rise of the Planet of the Apes“ (2011) als Test der kognitiven Fähigkeiten auf.