Türme von Hanoi
Versetze den ganzen Turm von Stab A auf Stab C, immer nur eine Scheibe auf einmal, und lege nie eine größere Scheibe auf eine kleinere. Zieh eine Scheibe oder klicke auf zwei Stäbe und sieh dann, wie nah du an die minimale Zugzahl gekommen bist.
Zuletzt aktualisiert:
Zieh eine Scheibe oder klicke auf einen Stab und dann auf einen anderen.
Gelöst!
Anleitung: Türme von Hanoi
- Wähle die Anzahl der Scheiben (3 ist leicht, 8 braucht 255 Züge) und klicke auf Neues Spiel.
- Verschiebe eine Scheibe, indem du sie auf einen anderen Stab ziehst, oder klicke auf den Stab, von dem du nehmen willst, und dann auf den Stab, auf den sie soll. Die Tasten 1, 2 und 3 funktionieren auch.
- Halte dich an die eine Regel: Eine Scheibe darf nur auf einen leeren Stab oder auf eine größere Scheibe.
- Baue den Turm auf Stab C neu auf. Deine Zugzahl wird mit dem kleinstmöglichen Wert 2ⁿ − 1 verglichen.
- Du kommst nicht weiter? Klicke auf Tipp für den besten nächsten Zug, auf Rückgängig, um einen Zug zurückzunehmen, oder auf Lösen, um dir die optimale Lösung ab deiner aktuellen Stellung anzusehen.
Minimale Züge für jede Scheibenanzahl
Die wenigsten Züge, um einen Turm aus n Scheiben zu versetzen, sind 2n − 1. Das ergibt sich aus der Rekursion T(n) = 2·T(n − 1) + 1 mit T(1) = 1: Du räumst den kleineren Turm aus dem Weg, bewegst die größte Scheibe einmal und setzt den kleineren Turm wieder obendrauf.
| Scheiben | Minimale Züge (2n − 1) | Züge der kleinsten Scheibe | Züge der größten Scheibe |
|---|---|---|---|
| 3 | 7 | 4 | 1 |
| 4 | 15 | 8 | 1 |
| 5 | 31 | 16 | 1 |
| 6 | 63 | 32 | 1 |
| 7 | 127 | 64 | 1 |
| 8 | 255 | 128 | 1 |
| 10 | 1,023 | 512 | 1 |
| 64 | 18,446,744,073,709,551,615 | 263 | 1 |
In einer optimalen Lösung bewegt sich Scheibe k (gezählt ab der kleinsten, k = 1) genau 2n − k Mal, deshalb bewegt sich die kleinste Scheibe bei jedem zweiten Zug.
So löst du die Türme von Hanoi
Die rekursive Methode
- Versetze die oberen n − 1 Scheiben vom Startstab auf den freien Stab (mit dem Zielstab als Hilfe).
- Versetze die größte Scheibe vom Startstab auf den Zielstab.
- Versetze die n − 1 Scheiben vom freien Stab auf den Zielstab (mit dem Startstab als Hilfe).
Die Schritte 1 und 3 sind jeweils dasselbe Rätsel mit einer Scheibe weniger, also wiederholst du die Idee, bis nur noch eine Scheibe übrig ist. Das ist ein klassisches erstes Beispiel für Rekursion in der Informatik.
Das einfache Muster zum Merken
- Wechsle die Züge ab. Bei ungeraden Zügen (1., 3., 5. …) bewegst du die kleinste Scheibe. Bei geraden Zügen machst du den einzigen erlaubten Zug, an dem die kleinste Scheibe nicht beteiligt ist.
- Lass die kleinste Scheibe immer in dieselbe Richtung wandern. Bei einer ungeraden Scheibenanzahl kreist sie A → C → B → A …; bei einer geraden A → B → C → A ….
- Scheiben auf demselben Stab wechseln die Parität. In einer optimalen Lösung landet eine ungerade nummerierte Scheibe nie direkt auf einer anderen ungeraden, und eine gerade nie auf einer geraden.
Tastatursteuerung
| Taste | Aktion |
|---|---|
| 1, 2, 3 (oder A, B, C) | Von diesem Stab aufnehmen / auf ihn ablegen |
| Esc | Angehobene Scheibe zurücklegen |
| Strg + Z | Letzten Zug rückgängig machen |
| Tab, dann Eingabe | Stab fokussieren und auswählen |
Häufige Fragen
Was sind die Regeln der Türme von Hanoi?
Alle Scheiben liegen zu Beginn auf einem Stab gestapelt, die größte ganz unten. Du musst den ganzen Stapel auf einen anderen Stab versetzen, dabei immer nur eine Scheibe auf einmal bewegen (die oberste Scheibe eines Stabs) und nie eine größere Scheibe auf eine kleinere legen.
Wie viele Züge braucht man mindestens?
Das Minimum für n Scheiben ist 2^n − 1. Das sind 7 Züge für 3 Scheiben, 15 für 4, 31 für 5, 63 für 6, 127 für 7 und 255 für 8. Jede weitere Scheibe verdoppelt die Züge und fügt einen hinzu.
Was ist der Trick beim Lösen?
Denk rekursiv: Um n Scheiben auf einen Zielstab zu versetzen, versetzt du zuerst die oberen n − 1 Scheiben auf den freien Stab, dann die größte Scheibe auf das Ziel und dann die n − 1 Scheiben obendrauf. Ein praktisches Muster: Die kleinste Scheibe bewegt sich bei jedem zweiten Zug, immer in dieselbe Richtung um die Stäbe herum.
In welche Richtung sollte die kleinste Scheibe zuerst ziehen?
Bei einer ungeraden Anzahl von Scheiben setzt du die kleinste Scheibe zuerst direkt auf den Zielstab (A nach C). Bei einer geraden Anzahl setzt du sie zuerst auf den mittleren Stab (A nach B). Wenn du dich daran hältst, ist die optimale Lösung leicht zu finden.
Kann der Löser ein bereits begonnenes Spiel beenden?
Ja. Klicke jederzeit auf Lösen, und er berechnet die kürzeste Zugfolge von deiner aktuellen Stellung bis zu einem vollständigen Turm auf Stab C und spielt sie animiert ab. Du kannst ihn jederzeit stoppen.
Wie lange würden 64 Scheiben dauern?
In der Legende vom Tempelrätsel versetzen Mönche 64 goldene Scheiben. Dafür braucht es 2^64 − 1, also etwa 18.4 Trillionen Züge. Bei einem Zug pro Sekunde würde das rund 585 Milliarden Jahre dauern.
Werden alle Tools auf FreeToolCabin auf Qualität und Genauigkeit getestet?
Ja. Jedes Tool auf der Website durchläuft automatische Tests in echten Browsern, die prüfen, ob das Ergebnis stimmt und keine Fehler auftreten. Wenn du einen Fehler findest oder einen Vorschlag hast, schreib uns an [email protected] – wir sehen es uns an.