Türme von Hanoi

Türme von Hanoi online spielen

Das Spielfeld oben auf dieser Seite ist ein kostenloses Spiel der Türme von Hanoi, das in Ihrem Browser läuft — nichts herunterzuladen, kein Konto anzulegen. Wählen Sie 3 bis 15 Scheiben und bringen Sie den ganzen Stapel vom linken Turm auf den rechten.

• Handy oder Tablet: Tippen Sie auf einen Turm, um seine oberste Scheibe aufzunehmen, und auf einen anderen, um sie abzulegen.
• Maus: Ziehen Sie eine Scheibe hinüber, oder klicken Sie erst den einen und dann den anderen Turm an.
• Tastatur: ← und → wählen einen Turm, ↑ nimmt auf und ↓ legt ab; 1, 2 und 3 springen direkt zu den Türmen A, B und C, und Esc legt die Scheibe zurück.

Fehler kosten nichts. Rückgängig nimmt Ihren letzten Zug zurück, Zurücksetzen beginnt dieselbe Größe von vorn, und Tipp hebt die Scheibe an, die die kürzeste Lösung als Nächstes bewegen würde, und sagt wohin. Zug spielt ihn für Sie. Wer lieber zusieht, lässt Automatisch lösen das Rätsel von dort aus beenden, wo das Spielfeld gerade steht — nicht nur vom Anfang.

Gezählt wird erst, wenn Sie ziehen. Nach Ihrem ersten Zug zeigt das Panel:

• Ihre Züge, eine Uhr und einen Effizienzwert — Ihre Partie als Prozentsatz einer perfekten;
• ob Sie noch auf dem optimalen Weg sind, oder wie viele Züge Sie davon entfernt sind.

Die Zeitleiste unter dem Spielfeld hält die ganze Partie fest. Gehen Sie zu jeder früheren Stellung zurück, oder spielen Sie sie mit 0,5×, 1×, 2× oder 4× ab; dieselbe Geschwindigkeit bestimmt das Tempo von Automatisch lösen. Der Fokusmodus räumt alles außer den Türmen beiseite, und die Seite merkt sich Ihre zuletzt gespielte Scheibenzahl. Am Ende vergleicht der Ergebnisbildschirm Ihre Züge mit dem Minimum und bietet Ihnen eine Scheibe mehr an.

Das Problem der Türme von Hanoi

Das Problem beginnt mit drei Türmen und einem Stapel unterschiedlich großer Scheiben auf einem davon, die größte unten. Ziel ist es, den ganzen Stapel auf einen anderen Turm zu bringen, unter drei Regeln:

1. Es wird immer nur eine Scheibe bewegt.
2. Nur die oberste Scheibe eines Turms darf bewegt werden.
3. Eine größere Scheibe darf nie auf einer kleineren liegen.

Das ist das ganze Rätsel, und man lernt es in etwa einer Minute. Die dritte Regel macht es schwer: Jede Scheibe muss an einer erlaubten Stelle warten, während die Scheiben unter ihr bewegt werden, und mit nur drei Türmen ist nie viel Platz. Die Spielanleitung zeigt sie in Bildern, mit einem Übungsfeld und einem durchgerechneten Beispiel.

Der französische Mathematiker Édouard Lucas veröffentlichte das Rätsel 1883. Ein Jahr später fügte ein Zeitschriftenartikel die Legende hinzu, für die es berühmt ist: Brahmanenpriester, die vierundsechzig goldene Scheiben umschichten, und das Ende der Welt, wenn sie fertig sind. Bei einem Zug pro Sekunde dauerte das rund 585 Milliarden Jahre.

Minimale Zugzahl und die Formel 2ⁿ − 1

Die kleinstmögliche Zugzahl für Türme von Hanoi mit n Scheiben ist 2ⁿ − 1, oft als 2^n − 1 geschrieben. Drei Scheiben brauchen 7 Züge, vier brauchen 15, und die Türme von Hanoi mit 5 Scheiben brauchen mindestens 31 Züge. Das ist eine bewiesene Untergrenze und kein Rekord: Für keine Größe gibt es eine kürzere Lösung, und es ist die Zahl, an der Sie der Effizienzwert auf dem Spielfeld misst.

Die Gleichung hinter der Formel

Die Gleichung folgt unmittelbar aus den Regeln. Bevor die größte Scheibe bewegt werden kann, müssen die n − 1 Scheiben darüber auf dem freien Turm liegen; dann wechselt sie hinüber; dann kommen jene Scheiben wieder obenauf. Schreibt man T(n) für die kleinste Zugzahl, die all das leistet:

T(n) = 2·T(n − 1) + 1, ausgehend von T(0) = 0 — keine Scheiben, keine Züge.

Jede Größe kostet das Doppelte der Größe darunter, plus eins: 1, 3, 7, 15, 31, 63. Jede dieser Zahlen ist eine Zweierpotenz minus eins, und daher kommt die geschlossene Form T(n) = 2ⁿ − 1. Der Beweis, dass 2ⁿ − 1 das Minimum ist, führt beide Hälften der Behauptung aus — warum so viele Züge immer genügen und warum weniger unmöglich sind — und der Rechner für die minimale Zugzahl liefert die genaue Zahl für jede Scheibenzahl bis vierundsechzig.

Minimale Zugzahl nach Scheibenzahl

Jede Größe führt zu ihrer vollständigen Lösung, mit allen Zügen aufgelistet und auf einem Spielfeld gespielt. Die größte Partie hier hat 15 Scheiben, also 32.767 Züge: Jede Scheibe mehr verdoppelt die Länge der Partie, plus einen Zug.

Der Algorithmus der Türme von Hanoi und die Rekursion

Die Gleichung oben ist zugleich der Algorithmus, als Anweisung gelesen. Um n Scheiben von einem Ausgangsturm auf einen Zielturm zu bringen:

1. Bringen Sie n − 1 Scheiben vom Ausgang auf den freien Turm.
2. Bringen Sie die größte Scheibe vom Ausgang auf das Ziel.
3. Bringen Sie die n − 1 Scheiben vom freien Turm auf das Ziel.

Schritt 1 und 3 sind dasselbe Problem mit einer Scheibe weniger, also löst der Algorithmus sie, indem er sich selbst aufruft, und ein Aufruf ohne Scheiben kehrt einfach zurück. Das ist die Rekursion der Türme von Hanoi vollständig, und deshalb benutzt fast jede Informatikvorlesung dieses Rätsel, um Rekursion zu lehren. Der Trick ist, nicht alle Züge auf einmal sehen zu wollen: Vertrauen Sie dem kleineren Aufruf, seine Arbeit zu tun, und die drei Schritte sind die ganze Lösung.

Weil der Algorithmus genau 2ⁿ − 1 Züge macht, ist seine Laufzeit O(2ⁿ), und das kann nichts unterbieten: Jeder dieser Züge muss gemacht werden. Sein Speicherbedarf beträgt dagegen nur O(n). Die Seite zum Algorithmus der Türme von Hanoi führt den Code Zeile für Zeile neben einem laufenden Spielfeld aus und zeichnet dabei den Aufrufbaum, und die iterative Lösung erzeugt dieselben Züge aus zwei Regeln und einer Schleife.

Türme von Hanoi in Python, Java und anderen Sprachen

Die drei Schritte übersetzen sich fast wörtlich in Code. Türme von Hanoi in Python ist eine Funktion aus sieben Zeilen: ein Basisfall für null Scheiben, zwei rekursive Aufrufe und die eine Zeile dazwischen, die einen Zug ausgibt. Türme von Hanoi in Java ist dieselbe Methode in einer Klasse — und die Stelle, an der Sie erfahren, warum die Zahl für vierundsechzig Scheiben nicht in ein long passt. Vollständige Programme gibt es außerdem in C, C++, C# und JavaScript.

Jedes Listing wurde ausgeführt und seine Ausgabe gegen den Löser dieser Website geprüft, und zu jedem gehört eine Erklärung, die sagt, warum jede Zeile da ist, und nicht, was die Syntax tut.

Mehr Möglichkeiten zu spielen und zu lernen

Wenn drei Türme und ein voller Stapel leicht fallen, gibt es mehr zu versuchen:

• Die tägliche Aufgabe — eine durcheinandergebrachte Stellung, für alle dieselbe, neu um Mitternacht UTC. Lösen Sie sie ohne den Löser, um Ihre Serie zu halten.
• Der Löser — jeder Zug der kürzesten Lösung aus jeder erlaubten Stellung, auch aus der, in der Sie auf diesem Spielfeld gerade feststecken.
• Strategien — die eine wiederkehrende Idee hinter jeder Größe, und eine Regel, die den nächsten Zug ohne Vorausplanen verrät.
• Varianten — vier Türme statt drei, ein Ring, in dem Scheiben nur in eine Richtung wandern, zwei Farben zum Sortieren und eine zufällige Ausgangsstellung.
• Für Lehrkräfte — ein Unterrichtsentwurf für 45 Minuten, ein druckbares Arbeitsblatt mit Lösungen und ein Spielfeld zum Einbetten in eine Kursseite.

Häufige Fragen

Was sind die Türme von Hanoi?

Die Türme von Hanoi sind ein Rätsel mit drei Türmen und einem Stapel unterschiedlich großer Scheiben. Man bringt den ganzen Stapel von einem Turm auf einen anderen, immer nur eine Scheibe auf einmal, und eine größere Scheibe darf nie auf einer kleineren liegen. Der französische Mathematiker Édouard Lucas veröffentlichte es 1883.

Kann ich die Türme von Hanoi kostenlos online spielen?

Ja. Das Spielfeld auf dieser Seite ist kostenlos, läuft in jedem modernen Browser auf Handy, Tablet oder Computer und braucht weder Download noch Konto. Die zuletzt gespielte Scheibenzahl und Ihre Rekorde werden in Ihrem eigenen Browser gespeichert, nicht auf einem Server.

Wie viele Züge braucht man bei den Türmen von Hanoi mindestens?

Ein perfektes Spiel mit n Scheiben sind 2ⁿ − 1 Züge. Drei Scheiben brauchen 7, fünf brauchen 31, und 15 Scheiben brauchen 32.767. Eine kürzere Lösung gibt es nicht, diese Zahl ist also eine feste Untergrenze und nicht bloß ein Ziel.

Wie löst man die Türme von Hanoi?

Jede Lösung ist dieselbe wiederholte Idee: Um einen Stapel von n Scheiben ans Ziel zu bringen, schaffen Sie zuerst die oberen n − 1 Scheiben auf den freien Turm aus dem Weg, bringen die größte Scheibe hinüber und holen dann jene n − 1 Scheiben obendrauf. Der kleinere Stapel gehorcht genau derselben Regel, und darum löst eine Methode jede Größe.

Gibt es einen Kniff, den nächsten Zug zu kennen?

Ja. Bewegen Sie bei jedem ungeraden Zug die kleinste Scheibe um einen Turm in eine feste Richtung: nach links bei einer ungeraden Scheibenzahl, nach rechts bei einer geraden, an den Enden umlaufend — bei drei Scheiben springt ihr allererster Zug also von A nach C. Machen Sie bei jedem geraden Zug den einzigen erlaubten Zug, der die kleinste Scheibe nicht berührt. Im Wechsel spielen die beiden ein perfektes Spiel, ganz ohne Planung.

Mit wie vielen Scheiben kann ich hier spielen?

Mit 3 bis 15 Scheiben. Beginnen Sie mit 3, um die Form der Lösung kennenzulernen, und legen Sie dann eine Scheibe nach der anderen dazu — jede zusätzliche Scheibe verdoppelt die Arbeit ungefähr.

Kann ich einen Zug zurücknehmen oder meine Partie noch einmal ansehen?

Ja. Es gibt eine Schaltfläche zum Zurücknehmen, und jede Partie führt außerdem eine vollständige Zeitleiste: Gehen Sie zu jeder früheren Stellung zurück und das Spielfeld zeigt genau diesen Stand, oder spielen Sie Ihre Partie in vier Geschwindigkeiten ab, um zu sehen, wo Sie den optimalen Weg verlassen haben.