Türme von Hanoi
Drei Stäbe und ein Kegel aus Scheiben, die größte unten. Bringen Sie den ganzen Turm auf den rechten Stab. Sie dürfen immer nur eine Scheibe bewegen, und eine größere Scheibe darf nie auf einer kleineren liegen. Die kürzeste Lösung braucht 2ⁿ − 1 Züge: 1, 3, 7, 15, 31 und so weiter. Bewegen Sie jeweils eine Scheibe auf eine größere Scheibe oder einen leeren Stab. Am Ende soll der ganze Turm auf dem rechten Stab stehen. Die kürzeste Lösung braucht 2ⁿ − 1 Züge. Ziehen Sie eine Scheibe, oder klicken Sie auf einen Stab und dann auf einen anderen.
Wie es funktioniert
- Öffnen Sie diese Seite. Auf dem Startstab liegen vier Scheiben. Fünfzehn Züge sind das Minimum.
- Ziehen Sie die oberste Scheibe auf einen anderen Stab, oder klicken Sie auf einen Stab und dann auf den gewünschten. Eine größere Scheibe auf einer kleineren wird abgelehnt.
- Drücken Sie auf Lösen, um eine kürzeste Lösung anzusehen, oder gehen Sie sie mit Schritt durch. Speichern Sie dann ein PNG.
Eine Scheibe, und nie eine größere auf einer kleineren
Ein Zug nimmt die oberste Scheibe eines Stabs und legt sie auf einen anderen Stab oder auf einen leeren Stab. Eine andere Art von Zug gibt es nicht. Die Scheibe, die Sie ablegen, muss kleiner sein als die, auf der sie landet. Mit diesen Regeln bleiben die Scheiben auf jedem Stab sortiert, die größte unten.
2ⁿ − 1 Züge, nicht weniger
Um n Scheiben zu versetzen, schaffen Sie zuerst die n − 1 Scheiben über der größten aus dem Weg, bewegen die größte Scheibe einmal und versetzen dann die n − 1 Scheiben auf sie. Brauchen n − 1 Scheiben T Züge, brauchen n Scheiben 2T + 1. Das ergibt 2ⁿ − 1: 1, 3, 7, 15, 31. Acht Scheiben, der größte Turm hier, brauchen 255 Züge.
Dasselbe Rätsel, eine Scheibe kleiner
Bringen Sie die oberen n − 1 Scheiben auf den Hilfsstab. Bringen Sie die größte Scheibe zum Ziel. Bringen Sie die n − 1 Scheiben vom Hilfsstab auf das Ziel. Jede dieser kleineren Aufgaben ist wieder dasselbe Rätsel. Schritt und Lösen spielen einen kürzesten Weg ab. Bei einem perfekten Turm ist es diese Rekursion. Bei einem durcheinandergebrachten Brett ist es trotzdem ein kürzester Weg, gefunden durch Absuchen der erlaubten Stellungen.
Häufig gestellte Fragen
Was sind die Regeln der Türme von Hanoi?
Bewegen Sie immer nur eine Scheibe. Nehmen Sie die oberste Scheibe eines Stabs und legen Sie sie auf einen anderen Stab. Legen Sie nie eine größere Scheibe auf eine kleinere.
Wie viele Züge braucht die kürzeste Lösung?
2ⁿ − 1. Eine Scheibe braucht 1 Zug, zwei Scheiben 3, drei 7, vier 15 und fünf 31.
Wer hat die Türme von Hanoi erfunden?
Édouard Lucas stellte das Rätsel 1883 vor. Die Geschichte von Priestern, die 64 goldene Scheiben versetzen, ist die Legende, die er dazu erzählte.
Kann ich mir die Lösung ansehen?
Ja. Schritt spielt einen Zug einer kürzesten Lösung ab. Lösen spielt den Rest ab. „3 Scheiben ansehen“ zeigt die klassische rekursive Strategie von Anfang an.
Verwandte Tools
Türme von Hanoi
Die Türme von Hanoi: drei Stäbe, immer nur eine Scheibe und nie eine größere auf einer kleineren. Die kürzeste Lösung hat 2ⁿ−1 Züge. Édouard Lucas stellte das Rätsel 1883 vor.
Springerproblem
Springen Sie mit dem Springer genau einmal auf jedes Feld des Bretts. Spielen Sie selbst mit Warnsdorff-Hinweisen, oder sehen Sie zu, wie Lösen eine offene oder geschlossene Tour vollendet. Speichern Sie den Weg als PNG.
Acht Damen
Setzen Sie acht Damen so auf ein Schachbrett, dass keine eine andere angreift. Probieren Sie es selbst, sehen Sie zu, wie die Backtracking-Suche Schritt für Schritt eine Lösung findet, und gehen Sie alle 92 Lösungen durch.
15-Puzzle
Spielen Sie das klassische 15-Puzzle, das Schiebepuzzle mit Holzsteinen, im Browser auf 3×3, 4×4 oder 5×5. Mischen Sie, schieben Sie ganze Reihen auf einmal, probieren Sie Sam Loyds unmögliches 14-15, oder sehen Sie zu, wie Lösen es zu Ende bringt.
Buffons Nadel
Lassen Sie im Browser Nadeln auf einen Boden mit Linien fallen. Zählen Sie die Kreuzungen und sehen Sie zu, wie Buffons Experiment von 1777 π schätzt.
Multiplikationskreise
Verbinden Sie jede Zahl auf einem Kreis mit ihrem Vielfachen. Zeichnen Sie eine Einmaleinsreihe, eine Kardioide oder ein Fadenbild auf Papier, mit Kreide oder auf Holz.
Die Collatz-Vermutung
Erkunden Sie das Collatz-3n+1-Problem im Browser. Verfolgen Sie Hagelkorn-Folgen, lassen Sie einen geometrischen Collatz-Baum wachsen und zoomen Sie in das kontinuierliche Collatz-Fraktal.
Langtons Ameise
Starten Sie Langtons Ameise im Browser. Sehen Sie Symmetrie, Chaos und die 104-Schritte-Autobahn, und probieren Sie dann mehrfarbige Regeln, mehrere Ameisen, ein Sechseckgitter und Turmiten.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor