🗼 Wie man die Türme von Hanoi löst: Methode und Mindestzüge

Von Miguel Arechaga

Die Türme von Hanoi sind ein mathematisches Rätsel mit mehr als einem Jahrhundert Geschichte und einem Ehrenplatz in der Informatik, weil sie die Idee „ein Problem lösen, indem man es in kleinere zerlegt“ perfekt veranschaulichen. Hier ist die Methode, um sie jedes Mal zu lösen.

Was sind die Türme von Hanoi?

Es gibt drei Türme und einen Stapel Scheiben unterschiedlicher Größe, auf dem ersten Turm von der größten (unten) bis zur kleinsten (oben) gestapelt. Ziel ist es, den gesamten Stapel auf den letzten Turm zu bewegen, wobei zwei Regeln gelten: Es bewegt sich immer nur eine Scheibe auf einmal, und eine größere Scheibe darf nie auf einer kleineren landen.

Wie man spielt

1. Tipp auf den Ausgangsturm, um die oberste Scheibe aufzunehmen, und dann auf den Zielturm.
2. Du darfst nie eine größere Scheibe auf eine kleinere legen.
3. Du gewinnst, wenn du den gesamten Stapel auf den Turm rechts bewegt hast.
4. Versuch es mit der minimalen Anzahl an Zügen. Du kannst zwischen 3 und 6 Scheiben wählen.

Die rekursive Methode (die nie versagt)

Das Geheimnis besteht darin, „von oben nach unten“ zu denken. Um einen Stapel aus N Scheiben von Turm A nach Turm C zu bewegen und dabei B als Stütze zu nutzen, machst du immer dasselbe:

1. Beweg die obersten N−1 Scheiben von A nach B (dem Hilfsturm).
2. Beweg die größte Scheibe von A nach C.
3. Beweg die N−1 Scheiben von B nach C, oben auf die große.

Jeder dieser Schritte „bewege N−1 Scheiben“ wird gelöst, indem du dieselbe Idee mit einem kleineren Stapel wiederholst. Es ist ein Muster, das sich nach innen wiederholt, bis es bei einer einzigen Scheibe ankommt, die einfach direkt bewegt wird.

Der Trick mit den Mindestzügen

Die minimale Anzahl an Zügen für N Scheiben beträgt genau 2^N − 1: 7 bei 3 Scheiben, 15 bei 4, 31 bei 5 und 63 bei 6. Es gibt sogar einen praktischen Trick: Wenn du die kleinste Scheibe immer in dieselbe kreisförmige Richtung bewegst und in den Zügen dazwischen den einzigen anderen erlaubten Zug machst, löst du das Rätsel im Minimum, ohne auch nur darüber nachzudenken.

Die Türme von Hanoi sind eine wunderschöne Übung in Logik und Planung. Sobald du das rekursive Muster verstanden hast, ist es nur noch eine Frage des Wiederholens des Rezepts, sie für jede beliebige Anzahl an Scheiben zu lösen.

🏆 Rangliste der besten Partien

Die Türme von Hanoi haben eine eigene globale Rangliste: Deine Lösung mit den wenigsten Zügen wird gespeichert. Geh zur Rangliste, zum Tab 🕹️ 1 Spieler, wähle „Türme von Hanoi“ im Dropdown und vergleiche dein Ergebnis mit anderen Spielern, synchronisiert mit deinem Konto. Damit dein Ergebnis zählt, brauchst du ein kostenloses Konto bei MundoSudoku (nur Benutzername und Passwort, keine E-Mail nötig): Du kannst auch ohne spielen, aber ohne Anmeldung wird dein Ergebnis nicht in der Rangliste gespeichert.