Zug für Zug durch das Dreieck

Hanoi// als Fraktal

Züge 0
Zustände 81
Tiefe —
3D — Turm
Zustandsgraph — Sierpiński-Dreieck (T: ein/aus)
HANOITURM UND DREIECK WERDEN AUFGEBAUT

Geschichte

Édouard Lucas, französischer Mathematiker, veröffentlichte das Spiel 1883 — unter dem Decknamen „Prof. Claus" von der „Universität Li-Sou-Stian" (Anagramme von Lucas / Saint-Louis). Das ursprüngliche Spiel hatte 8 Scheiben.

Die Legende (Marketing von 1883)

Lucas erzählte: Im großen Tempel zu Benares versetzen Mönche einen Turm aus 64 goldenen Scheiben. Sobald sie fertig sind, zerfällt der Tempel — das Ende der Welt. Die Rechnung dahinter: 264 − 1 = 18 446 744 073 709 551 615 Züge — bei einem Zug pro Sekunde rund 585 Milliarden Jahre.

Warum 2n − 1?

Um den größten Stein zu bewegen, muss der Stapel darüber erst beiseite (Rekursion). n Scheiben = den (n−1)-Stapel zweimal bewegen plus einen Zug: (2n−1−1) + 1 + (2n−1−1) = 2n−1. Es gibt für jede Ausgangsstellung nur einen kürzesten Weg — den findet der Solver hier.

Der Trick zum Selberlösen

Der iterative Algorithmus: Versetze die kleinste Scheibe bei jedem zweiten Zug, und zwar immer zyklisch in dieselbe Richtung (n ungerade: Zielstab, n gerade: Zwischenstab). Danach gibt es nur einen legalen Zug — versetze ihn. Fertig ist die optimale Folge.

Das Fraktal (der Teil rechts)

Jede der 3n Stellungen ist ein Knoten, jeder legale Zug eine Kante: kn = 3/2 · (3n − 1) Kanten (bei n=4: 120). Der Graph ist der „Spielbaum"; sein Durchmesser ist 2n−1 — von jeder Stellung zu jeder anderen reichen maximal so viele Züge. Mit jeder Scheibe wächst der Graph um Faktor 3, das gezeichnete Dreieck aber nur um Faktor 2 — die normierte Folge konvergiert gegen das Sierpiński-Dreieck, ein Fraktal der Hausdorff-Dimension log 3/log 2 ≈ 1,585.

Quelle: Wikipedia, „Türme von Hanoi" · Konzept & Code: Dirk · Mathematik: Frame · v1.2 · 2026

✦

Weg gefunden.

Der kürzeste Pfad durchs Dreieck ist komplett.

Was hier passiert

  1. Drei Stäbe, ein Regelwerk. Scheiben liegen gestapelt; gezogen wird immer die oberste Scheibe eines Stabs, und niemals liegt eine größere auf einer kleineren. Das ist der ganze Spielraum — der Rest ist Mathematik.
  2. Jede Anordnung = ein Punkt. Beantworte für jede der n Scheiben nur, auf welchem Stab sie liegt. Bei 3 Stäben gibt es für jede Scheibe 3 Antworten — also genau 3n mögliche Zustände (81 bei n = 4, 2 187 bei n = 7).
  3. Jeder Zug = eine Linie. Von jedem Punkt führen genau 3 Linien zu den Zuständen, die in einem Zug erreichbar sind. Verbinde alle: das Dreieck mit den ausgesparten Dreiecken — das Sierpiński-Dreieck — entsteht. Es ist nicht dekoriert: es ist der vollständige Lösungsweg-Raum des Puzzles.
  4. Lösen = Wegsuche. Die Kürzeste-Weg-Suche (Breitensuche) läuft beidseitig vom verhunzten Zustand und vom Ziel gleichzeitig und leuchtet den Pfad als Lichtspur. Gelöster Turm = gefundener Weg durchs Dreieck.

Weitersagen-Formel: „Die Zahl der Zustände ist 3n, jeder ist ein Punkt, jeder Zug eine Linie — der komplette Zug-Graph ist das Sierpiński-Dreieck, und Lösen ist der kürzeste Weg durchs Dreieck. Der kürzeste Weg braucht stets 2n − 1 Züge."

Tastatur

1 2 3Peg wählen — erster Tipp Quelle, zweiter Tipp Ziel
NScramble (zufällige Züge ab aktuellem Zustand)
EnterSolve — bidirektionaler BFS, Pfad als Lichtspur
SpacePfad-Wiedergabe Play / Pause
AReset auf Startzustand
TFraktal-Panel ein-/ausblenden
/Diese Hilfe
EscHilfe schließen / Peg-Wahl abbrechen

Konzept & Code: Dirk · Mathematik: Frame · Installation v1.2 · 2026