Türme von Hanoi

Was sind die Türme von Hanoi?

Die Türme von Hanoi sind das Geduldspiel, das der französische Mathematiker Édouard Lucas 1883 in Paris herausbrachte, unter dem erfundenen Namen „Professor N. Claus de Siam“, einem Anagramm von „Lucas d'Amiens“. Es bestand aus einem Holzsockel mit drei Stäben und einem Turm aus acht Scheiben, und dazu gab es eine Geschichte: In einem großen Tempel versetzen Priester einen Turm aus 64 goldenen Scheiben von einer Diamantnadel auf eine andere, immer nur eine Scheibe und nie eine größere auf eine kleinere, und wenn sie fertig sind, geht die Welt unter. Perfekt gespielt brauchen 64 Scheiben 2^64 - 1 Züge, über 18 Trillionen: bei einem Zug pro Sekunde rund 585 Milliarden Jahre.

Die Regeln passen in eine Zeile: Versetze den ganzen Turm auf den Zielstab, immer nur eine Scheibe, und leg nie eine größere Scheibe auf eine kleinere. Ein Turm aus n Scheiben auf drei Stäben braucht mindestens 2^n - 1 Züge, jede weitere Scheibe verdoppelt also die Arbeit: 4 Scheiben brauchen 15 Züge, 6 brauchen 63, 8 brauchen 255.

Hier hat die leichte Stufe 4 Scheiben auf drei Stäben, die mittlere 6 Scheiben, und die schwere ist die Variante mit vier Stäben, die Henry Dudeney 1907 in The Canterbury Puzzles als „The Reve's Puzzle“ stellte: acht verschieden große Käselaibe auf vier Schemeln. Ein vierter Stab macht den Weg viel kürzer, 33 Züge für acht Scheiben, aber auch viel schwerer zu durchschauen. Außerdem gibt es jeden Tag einen Turm des Tages: sechs Scheiben, verstreut auf drei Stäbe, für alle dieselben, die du auf dem Stab mit der goldenen Kappe sammeln musst.

So wird gespielt

Bring alle Scheiben auf den Stab mit der goldenen Kappe.

• Tippe auf einen Stab, um seine oberste Scheibe anzuheben: Sie schwebt über dem Stab. Tippe auf einen anderen Stab, um sie dort abzulegen, oder auf ihren eigenen, um sie zurückzulegen.
• Zieh eine Scheibe mit dem Finger auf einen anderen Stab und lass los.
• Auf der Tastatur wählen die Tasten 1 bis 4 die Stäbe, die Pfeiltasten wechseln zwischen ihnen, und Escape legt eine angehobene Scheibe zurück.
• Die eine Regel. Eine Scheibe darf nur auf einen leeren Stab oder auf eine größere Scheibe. Versuchst du es anders, schüttelt die Scheibe den Kopf, und die kleinere Scheibe im Weg leuchtet auf.
• Sterne. Drei für die kleinste Zahl von Zügen, die der Turm braucht, zwei bei bis zu etwa einem Viertel mehr, sonst einer. Die Sterne oben zeigen, wie viele du von hier aus noch holen kannst.
• Rückgängig gibt es auf der leichten Stufe; es nimmt deinen letzten Zug zurück und aus der Zählung. Die Uhr läuft weiter.
• Tipp. Hebt die Scheibe an, die ein kürzester Weg als Nächstes bewegt, und lässt den Stab leuchten, auf den sie gehört, für 20 Sekunden auf deine Wertung.
• Wertung. Deine Zeit ab dem ersten Zug, plus 5 Sekunden für jeden Zug über dem Minimum und 20 Sekunden für jeden Tipp. Weniger ist besser.

Strategietipps

1. Denk in Türmen, nicht in Scheiben. Um einen Turm aus sechs zu versetzen, bringst du zuerst die fünf über der größten Scheibe auf den dritten Stab, dann geht die größte in einem Zug hinüber, und die fünf folgen ihr. Jeder kleinere Turm wandert genauso.
2. Die kleinste Scheibe zieht jedes zweite Mal. In einer perfekten Lösung auf drei Stäben ist jeder zweite Zug die kleinste Scheibe, und sie wandert immer in dieselbe Richtung reihum. Der Zug dazwischen ist der einzige erlaubte, der sie nicht berührt.
3. Gerade oder ungerade entscheidet den ersten Zug. Bei einer geraden Zahl von Scheiben geht die kleinste zuerst auf den mittleren Stab, bei einer ungeraden direkt aufs Ziel.
4. Verstreute Türme: fang bei der größten an. Such die größte Scheibe, die noch nicht auf dem Ziel liegt. Alles Kleinere muss sich erst auf dem dritten Stab sammeln, bevor sie ziehen kann, und ab da ist es wieder ein gewöhnlicher Turm.
5. Vier Stäbe: teil den Turm. Stell die oberen vier oder fünf Scheiben mit allen vier Stäben beiseite, bring den Rest mit den drei noch freien Stäben hinüber und hol dann den oberen Teil nach. Das ist das Verfahren von Frame und Stewart, und für vier Stäbe ist bewiesen, dass es das kürzeste ist.

Häufige Fragen

Sind die Türme von Hanoi kostenlos?

Ja. Wie jedes Spiel auf Play läuft es kostenlos im Browser, ohne Download und ohne Konto.

Was ist die kleinste Zahl von Zügen?

Für n Scheiben auf drei Stäben 2^n - 1: 15 für vier Scheiben, 63 für sechs. Die Zahl oben über dem Brett ist das Minimum für den Turm vor dir, gefunden durch eine Suche über alle Stellungen, und stimmt daher auch für den verstreuten Turm des Tages.

Warum hat die schwere Stufe vier Stäbe?

Acht Scheiben auf drei Stäben brauchen 255 Züge, und wenn du das Verfahren kennst, ist das eher ein langer Spaziergang als ein Rätsel. Mit vier Stäben brauchen dieselben acht Scheiben nur 33 Züge, aber der kürzeste Weg ist viel schwerer zu finden. J. S. Frame und B. M. Stewart beschrieben das Verfahren 1941, und Thierry Bousch bewies 2014, dass es für vier Stäbe keinen kürzeren Weg gibt.

Was macht der Tipp?

Er hebt die Scheibe an, die ein kürzester Weg als Nächstes bewegt, egal wie deine Scheiben gerade liegen, und lässt den Stab leuchten, auf den sie gehört. Tippe auf den leuchtenden Stab, um den Zug zu machen. Jeder Tipp kostet 20 Sekunden.

Was ist der Turm des Tages?

Jeden Tag bekommen alle dieselben sechs Scheiben, verstreut auf drei Stäbe, mit demselben Zielstab, auf dem kürzesten Weg 40 bis 58 Züge vom Ziel entfernt, sodass sich die Zeiten in der Tageswertung direkt vergleichen lassen.