Turm von Hanoi meistern
Kurzfassung: Der Turm von Hanoi wird durch eine rekursive Regel gelöst: Um n Scheiben auf den Zielpfahl zu verschieben, zuerst n-1 Scheiben auf den mittleren Pfahl verschieben, dann die größte Scheibe auf das Ziel, dann n-1 Scheiben darüber. Diese Regel auf jeder Ebene anwenden und die minimale Zuganzahl wird immer erreicht. Das Minimum ist stets eine Zweierpotenz minus eins: 3 Scheiben brauchen 7 Züge, 4 Scheiben 15, 5 brauchen 31, 6 brauchen 63, 7 brauchen 127.
Was das Spiel ist
Der Turm von Hanoi beginnt mit einem Stapel Scheiben auf dem linken Pfahl, die größte unten, die kleinste oben. Das Ziel: Den gesamten Stapel auf den rechten Pfahl verschieben und dabei zwei Regeln befolgen. Eine Scheibe auf einmal verschieben. Niemals eine größere Scheibe auf eine kleinere legen.
Das ist alles. Keine Timer, kein Zufall, keine versteckten Informationen. Nur Logik und ein Zugbudget.
PlayMemorize skaliert von 3 Scheiben auf 7 Scheiben. Das Zugbudget beginnt über dem optimalen Minimum, sodass Anfänger noch gewinnen können, während sie das Muster lernen; wenn das Level steigt, nähert sich das Budget dem mathematischen Minimum an.
Die minimalen Zugzahlen: 3 Scheiben = 7 Züge, 4 Scheiben = 15 Züge, 5 Scheiben = 31 Züge, 6 Scheiben = 63 Züge, 7 Scheiben = 127 Züge. Jede Stufe erfordert ungefähr doppelt so viele Züge wie die Stufe darunter, plus eins. Das Überschreiten des Zugbudgets endet die Runde als Niederlage.
Der rekursive Algorithmus
Alles beim Turm von Hanoi folgt einem Muster, das auf jeder Skala wiederholt angewendet wird:
Um n Scheiben von Pfahl A nach Pfahl C zu verschieben, mit Pfahl B als temporärem Speicher:
- n-1 Scheiben von A nach B verschieben (mit C als temporär)
- Die größte Scheibe von A nach C verschieben
- n-1 Scheiben von B nach C verschieben (mit A als temporär)
Das ist der vollständige Algorithmus. Auf jeder Ebene des Rätsels führt man diese gleiche Drei-Schritt-Struktur aus. Das Geniale daran ist, dass Schritte 1 und 3 selbst kleinere Instanzen desselben Problems sind, die durch dieselbe Regel gelöst werden.
Den 3-Scheiben-Fall konkret durchgehen. Ziel: alle drei von Pfahl 1 auf Pfahl 3 verschieben.
- Schritt 1 (2 Scheiben von Pfahl 1 auf Pfahl 2): Scheibe 1 auf Pfahl 3, Scheibe 2 auf Pfahl 2, Scheibe 1 auf Pfahl 2.
- Schritt 2 (Scheibe 3 von Pfahl 1 auf Pfahl 3): ein Zug.
- Schritt 3 (2 Scheiben von Pfahl 2 auf Pfahl 3): Scheibe 1 auf Pfahl 1, Scheibe 2 auf Pfahl 3, Scheibe 1 auf Pfahl 3.
Gesamt: 7 Züge. Optimal.
Drei-Phasen-Denken. Bevor eine Scheibe berührt wird, die drei Phasen laut benennen: “n-1 Scheiben in die Mitte leeren; die größte auf das Ziel verschieben; n-1 Scheiben darüber aufbauen.” Auf jeder Rekursionsebene wird diese gleiche Struktur mit einer Scheibe weniger wiederholt. Keine Zugfolge wird auswendig gelernt - ein fraktales Muster wird ausgeführt.
Tipp: Vor jedem Zug fragen: “Was ist die größte Scheibe, die ich gerade verschieben muss?” Alles, was bis zum Verschieben dieser Scheibe getan wird, ist Vorbereitung. Diese Rahmung verhindert ziellose Züge und hält auf dem optimalen Pfad.
Warum die Zuganzahl festgelegt ist
Die minimale Zuganzahl folgt direkt aus dem Algorithmus. Das Lösen von n Scheiben erfordert das Lösen von n-1 Scheiben zweimal (Schritte 1 und 3) plus einen Zug der größten Scheibe (Schritt 2). Also T(n) = 2 mal T(n-1) plus 1. Mit T(1) = 1 ergibt das: 1, 3, 7, 15, 31, 63, 127 für Scheibenzahlen 1 bis 7.
Jede Zahl ist eine Zweierpotenz minus eins. Drei Scheiben: 8 minus 1 = 7. Vier Scheiben: 16 minus 1 = 15. Fünf Scheiben: 32 minus 1 = 31. Sechs Scheiben: 64 minus 1 = 63. Sieben Scheiben: 128 minus 1 = 127.
Das ist kein Zufall - es ist die direkte Folge des Lösens von n-1 Scheiben zweimal jedes Mal, wenn n Scheiben gelöst werden. Wenn man das versteht, hört man auf, Hanoi als ein Rätsel zu betrachten, das man durch Experimentieren knackt, und beginnt es als einen Algorithmus zu sehen, den man ausführt.
Taktiken nach Schwierigkeitsgrad
3 bis 4 Scheiben (Lernen): Auf dieser Stufe ist das Zugbudget komfortabel. Den Fokus darauf legen, jede Scheibe gedanklich zu benennen - “klein,” “mittel,” “groß” - damit nie Verwechslungen entstehen, welche Scheibe angepeilt wird. Die drei Phasen durchgehen, bevor etwas angerührt wird. Nach jedem Spiel die Phasen laut erklären: “Ich habe zwei Scheiben in die Mitte geleert, die große verschoben, oben neu aufgebaut.”
Tipp: Die größte Scheibe sollte pro vollständiger Lösung genau einmal bewegt werden. Wenn der Drang entsteht, sie erneut zu verschieben, stoppen - die Algorithmusstruktur ist zusammengebrochen. Zum Drei-Phasen-Rahmen zurückkehren und identifizieren, wo die Abweichung begann.
5 bis 6 Scheiben (Mittelstufe): Das Zugbudget wird enger. Jeder ziellose Zug kostet. Den rekursiven Algorithmus auf jeder Ebene strikt anwenden. Bei der Rekursion von n auf n-1 Scheiben sollte der mentale Fokus wechseln: Es wird gerade ein kleineres Hanoi-Rätsel mit einer anderen Menge von “Quell-”, “Ziel-” und “Hilfspfählen” gelöst. Verfolgen, welche Rolle jeder Pfahl auf jeder Rekursionsebene spielt.
Der Hilfspfahl-Wechsel. Auf jeder Rekursionsebene ist ein Pfahl die Quelle, einer das Ziel und einer der Hilfspfahl. Diese Rollen rotieren bei der Rekursion. Beim Verschieben von n-1 Scheiben von Pfahl 1 nach Pfahl 2 ist Pfahl 3 der Hilfspfahl. Beim dann folgenden Verschieben von n-2 Scheiben von Pfahl 1 nach Pfahl 3 ist Pfahl 2 der Hilfspfahl. Diesen Wechsel bewusst verfolgen - es ist die häufigste Verwirrungsquelle bei 5 und 6 Scheiben.
7 Scheiben (Herausforderung): Mit 127 Minimalzügen und einem engen Budget kann man nicht Zug für Zug denken. Phase für Phase denken. Vor dem Start die Top-Level-Struktur planen: 6 Scheiben in die Mitte verschieben (63 Züge), die größte Scheibe nach rechts verschieben (1 Zug), 6 Scheiben nach rechts verschieben (63 Züge). Dann jede 6-Scheiben-Phase genauso unterteilen. Diese Top-Down-Planung reduziert die kognitive Last und verhindert den Fehler, den Überblick zu verlieren, in welcher Phase man sich befindet.
Achtung: Bei 7 Scheiben ist der Versuch, die Sequenz Zug für Zug zu memorieren, unzuverlässig und unnötig. Dem Algorithmus vertrauen. Wenn die rekursive Regel an jedem Verzweigungspunkt angewendet wird, ist der richtige Zug immer bestimmt. Zweifel und Zögern sind der Weg, Züge zu verbrauchen und das Budget zu erschöpfen.
Häufige Fehler
Es wie ein Versuch-und-Irrtum-Rätsel behandeln. Zufällige Züge sehen gelegentlich produktiv aus, aber münden in Sackgassen. Hanoi ist ein Algorithmus, kein Rätsel zum Knacken durch Experimentierung. Zufälligkeit vollständig aus dem Denken entfernen.
Den Überblick über Pfahlrollen verlieren. Auf drei identischen Pfählen können “Quelle”, “Ziel” und “Hilfspfahl” verschwimmen, besonders bei höheren Scheibenzahlen. Vor dem Start die Pfähle explizit im Kopf beschriften: LINKS = Start, MITTE = Hilfe, RECHTS = Ziel. Diese Beschriftungen konsistent über jede Rekursionsebene verwenden.
Die größte Scheibe mehr als einmal verschieben. Auf der obersten Rekursionsebene bewegt sich die größte Scheibe genau einmal. Wenn der Drang entsteht, sie erneut zu verschieben, stoppen - die Algorithmusstruktur ist zusammengebrochen. Zum Drei-Phasen-Rahmen zurückkehren und identifizieren, wo die Abweichung begann.
Der Checkpoint der größten Scheibe. Auf jeder Rekursionsebene sollte die n-te Scheibe genau einmal verschoben werden. Nach der ersten Teilphase (n-1 Scheiben auf den Hilfspfahl verschieben) sollte die n-te Scheibe frei und unverschoben sein. Nach Schritt 2 sollte sie auf dem Zielpfahl sein. Wenn nicht, ist vom Algorithmus abgewichen worden.
Züge aufbrauchen. Das passiert nur, wenn dem Algorithmus nicht gefolgt wird oder wenn Züge gemacht und dann gedanklich “rückgängig gemacht” wurden (Meinungsänderung während der Ausführung und anderen Pfad versucht). Dem Algorithmus verpflichten. Er ist optimal - es gibt keinen besseren Pfad.
Achtung: Sobald ein Zug mit dem rekursiven Algorithmus entschieden wurde, diesen ausführen. Das Hinterfragen mitten in der Ausführung führt zu verschwendeten Zügen. Der Algorithmus garantiert Optimalität - darauf vertrauen und ohne Zögern ausführen.
Ein Übungsplan
Woche 1 - Algorithmus-Verinnerlichung (3 Scheiben). Täglich 3-Scheiben-Spiele spielen. Nach jedem Spiel die drei Phasen laut beschreiben. Wiederholen, bis das Muster so vertraut ist, dass die gesamte Lösung erzählt werden kann, bevor der erste Zug gemacht wird.
Woche 2 - Skalierung (4 bis 5 Scheiben). Zu 4-Scheiben-Spielen übergehen. Die Rekursion geht jetzt zwei Ebenen tief. Nach jedem Spiel die Struktur nachverfolgen: “Ich habe bis 3 rekursiert, die große Scheibe verschoben, erneut rekursiert.” Drei bis vier Spiele auf 4 Scheiben spielen, dann zu 5 übergehen.
Woche 3 - Druck (6 Scheiben). Bei 6 Scheiben wird das Zugbudget zur bindenden Einschränkung. Mit dem Algorithmus als einzigem Leitfaden spielen. Anstreben, zwei 6-Scheiben-Spiele innerhalb von fünf Zügen des Minimums (63 Züge) abzuschließen. Die Zugzahl verfolgen und beobachten, wie sie sich im Laufe der Woche Richtung 63 bewegt.
Woche 4 - Beherrschung (7 Scheiben). 7-Scheiben-Rätsel versuchen. Top-Down-Phasenplanung anwenden, bevor eine Scheibe berührt wird. Drei aufeinanderfolgende Gewinne bei 7 Scheiben mit einer Zugzahl nahe 127 signalisiert echte Beherrschung.
Tipp: Ein Protokoll der Zugzahlen pro Scheibenstufe führen. Das Beobachten, wie die Zahl über Sitzungen hinweg zum Minimum sinkt, ist das klarste externe Signal, dass das rekursive Muster verinnerlicht wird. Zugzahlen über 130 für 7 Scheiben bedeuten, dass noch ziellose Züge erscheinen; unter 135 mit Konstanz bedeutet, dass die Struktur solide ist.
Der Turm von Hanoi ist eines der wenigen Spiele, bei denen Beherrschung sowohl absolut als auch messbar ist. Entweder man kennt den rekursiven Algorithmus und führt ihn aus, oder nicht. Wenn man ihn kennt, ergibt sich jede Schwierigkeitsstufe derselben Logik. Verlangsamen, die Phasen benennen, dem Algorithmus vertrauen, und die Lösung ist immer da.
Türme von Hanoi
Der Klassiker · verschiebe den ganzen Scheibenturm auf einen anderen Stab, eine Scheibe nach der anderen, nie eine größere auf eine kleinere
Jetzt spielen - kostenlosKein Konto nötig. Funktioniert auf jedem Gerät.
