Türme von Hanoi

So werden die Türme von Hanoi gespielt

Das Rätsel besteht aus drei Stäben und einem Stapel unterschiedlich großer Scheiben, die auf dem ersten Stab liegen, die größte unten, die kleinste oben. Dein Ziel ist es, den ganzen Stapel auf den dritten Stab zu versetzen. Es gibt nur zwei Regeln:

1. Du darfst immer nur eine Scheibe bewegen, und zwar die oberste eines Stapels.
2. Eine Scheibe darf nie auf einer kleineren liegen.

Tippe auf einen Stab, um seine oberste Scheibe anzuheben, und dann auf den Stab, auf den sie soll. Tippst du noch einmal auf denselben Stab, legst du sie zurück. Der Zugzähler zeigt, wie viele Züge du gemacht hast, und die kürzestmögliche Anzahl für deinen Turm. Schaffst du es in genau so vielen, hast du die perfekte Lösung gefunden.

Die kürzeste Lösung: 2ⁿ − 1 Züge

Das Rätsel hat eine wunderschöne rekursive Lösung. Um einen Turm aus n Scheiben von Stab 1 auf Stab 3 zu versetzen:

1. Versetze die oberen n − 1 Scheiben aus dem Weg auf Stab 2.
2. Versetze die größte Scheibe auf Stab 3.
3. Versetze die n − 1 Scheiben von Stab 2 auf Stab 3, oben auf die größte.

Schritt 1 und 3 sind dasselbe Rätsel mit einer Scheibe weniger. Mit jeder zusätzlichen Scheibe verdoppelt sich die Zahl der Züge also, plus eins: 1, 3, 7, 15, 31, 63, 127, 255. Allgemein braucht ein Turm aus n Scheiben 2ⁿ − 1 Züge, und keine Lösung kann kürzer sein. Tippe auf Lösung zeigen, um sie ablaufen zu sehen.

Eine Regel, die du ohne Nachdenken befolgen kannst

Es gibt auch eine einfache Schritt-für-Schritt-Methode. Wechsle zwischen zwei Arten von Zügen ab:

• Ungerade Züge: Versetze die kleinste Scheibe einen Stab weiter, immer in dieselbe Richtung. Bei einer geraden Anzahl Scheiben wandert sie 1 → 2 → 3 → 1, bei einer ungeraden 1 → 3 → 2 → 1.
• Gerade Züge: Mach den einzigen erlaubten Zug, an dem die kleinste Scheibe nicht beteiligt ist. Es gibt immer genau einen.

Befolgst du diese beiden Regeln, bist du jedes Mal mit der Mindestzahl an Zügen fertig. Es gibt sogar eine Verbindung zum Zählen im Binärsystem: Bei Zug Nummer m bestimmt die Zahl, wie oft 2 in m aufgeht, welche Scheibe sich bewegt. Die kleinste Scheibe bewegt sich bei jedem ungeraden Zug, die zweite bei den Zügen 2, 6, 10 und so weiter.

Geschichte und Legende

Die Türme von Hanoi wurden vom französischen Mathematiker Édouard Lucas erfunden und 1883 als Spielzeug verkauft, unter dem verspielten Namen „N. Claus de Siam“, einem Anagramm von „Lucas d'Amiens“. Dazu gehörte eine Legende: In einem großen Tempel versetzen Priester nach genau diesen Regeln einen Turm aus 64 goldenen Scheiben, und wenn sie fertig sind, geht die Welt unter.

Die Welt ist noch eine Weile sicher. Ein Turm aus 64 Scheiben braucht 2⁶⁴ − 1 Züge, etwas mehr als 18 Trillionen. Bei einem Zug pro Sekunde und ohne einen einzigen Fehler würde das rund 585 Milliarden Jahre dauern, ein Vielfaches des heutigen Alters des Universums. Heute ist das Rätsel ein Lieblingsbeispiel, um Rekursion in Mathematik und Programmierung zu erklären, und in der Psychologie wird es zur Untersuchung des Planens eingesetzt.

Häufige Fragen

Wie viele Züge braucht man mindestens?

Für einen Turm aus n Scheiben sind es mindestens 2ⁿ − 1 Züge: 7 bei 3 Scheiben, 15 bei 4, 31 bei 5, 63 bei 6, 127 bei 7 und 255 bei 8.

Muss der Turm auf den dritten Stab?

Ja, hier ist Stab 3 rechts das Ziel. Der mittlere Stab ist dein Hilfsstab. Die kürzeste Lösung ist in beide Richtungen gleich lang.

Zählt Rückgängig als Zug?

Nein. Rückgängig nimmt deinen letzten Zug zurück und senkt den Zugzähler um eins, du kannst also ohne Strafe ausprobieren.

Was bedeutet der Rekord?

Dein Rekord ist der größte Turm, den du gelöst hast. Fang mit 3 oder 4 Scheiben an und arbeite dich hoch. 8 Scheiben in 255 Zügen oder mehr sind ein echter Test für Geduld und Planung.

Ist es kostenlos?

Ja, komplett kostenlos und ohne Anmeldung. Dein Fortschritt wird in deinem Browser auf deinem eigenen Gerät gespeichert.