Türme-von-Hanoi-Löser

Wie der Löser arbeitet

Die Methode ist die Logik des Rätsels selbst, vorwärts durchgespielt. Damit die größte Scheibe auf ihrem Zielturm landen kann, muss jede kleinere Scheibe woanders sein — genauer: alle zusammen auf dem einen verbleibenden Turm. Also verlangt der Löser zuerst, dass dieser kleinere Stapel dorthin wandert, schiebt die große Scheibe hinüber und verlangt dann, dass der kleinere Stapel obendrauf zurückkommt. Jede dieser Forderungen ist dasselbe Problem mit einer Scheibe weniger, bis hinunter zu einer einzelnen Scheibe, die sich in einem Schritt bewegt.

Was diesen Löser von denen unterscheidet, die nur einen vollen Stapel können, ist eine einzige zusätzliche Überlegung: Liegt die größte Scheibe bereits auf ihrem Ziel, ist für sie nichts zu tun, und das ganze Problem schrumpft auf die Scheiben darüber. Dieser eine Fall ist es, der ihn aus einer halb gespielten Stellung heraus lösen lässt, statt Sie von vorn anfangen zu lassen — und deshalb sind die Zugzahlen aus einer eigenen Stellung kleiner als 2ⁿ − 1, bei einer angefangenen Partie oft weit kleiner.

1. 1Die n−1 Scheiben darüber auf den Hilfsturm legen. Nichts anderes geht, solange sie im Weg liegen.

2. 2Die größte Scheibe ist jetzt frei, und ihr Zielturm ist leer. Sie wechselt mit einem einzigen Zug – dem einzigen, den diese Phase braucht.

3. 3Den Stapel aus n−1 Scheiben darauf wieder aufbauen. Das ist dasselbe Problem mit einer Scheibe weniger, bis hinunter zu einer einzelnen Scheibe, die sich in einem Zug bewegt.

Eine Lösung lesen

Jede Zeile nennt einen Zug: welche Scheibe, welchen Turm sie verlässt, auf welchem sie landet. Scheibe 1 ist die kleinste. Sie müssen nie prüfen, ob ein Zug erlaubt ist — jeder Zug der Liste ist es per Konstruktion bereits.

Aus einem vollen Stapel fallen sofort zwei Muster auf:

• Die kleinste Scheibe zieht in jedem zweiten Zug — Zug 1, 3, 5 und so fort — und wandert dabei immer in derselben Richtung um die drei Türme.
• Jeder Zug dazwischen ist der einzige erlaubte Zug, der die kleinste Scheibe nicht anfasst.

Das ist die iterative Methode vollständig, und sie lässt sich an jeder Lösung aus einem vollen Stapel direkt ablesen. Aus einer eigenen Stellung bleibt die Liste die kürzeste, ist aber aus kleineren Umschichtungen zusammengesetzt, sodass die kleinste Scheibe unterwegs die Richtung wechseln kann. Die iterative Lösung zeigt, warum die Methode funktioniert, und der Strategie-Leitfaden macht etwas daraus, wonach man spielen kann. Die Rekursion selbst, Zeile für Zeile in sechs Sprachen verfolgt, steht auf der Seite zum Algorithmus.

Die üblichen Größen haben außerdem je eine eigene Seite mit allen Zügen und dem, was für diese Größe besonders ist: Lösungen von 3 bis 10 Scheiben und die 64 Scheiben der Legende.

Die Lösung mitnehmen

Die Adresszeile beschreibt immer das Brett auf dem Bildschirm. Eine vollständige Umschichtung liest sich ?disks=5&from=A&to=C; eine eigene Stellung ergänzt einen Code wie pos=CBBAA, ein Buchstabe je Scheibe, beginnend bei der kleinsten. Kopieren Sie diesen Link, und er öffnet genau dieses Rätsel wieder — so schicken Sie jemandem auch die Stellung, in der Sie feststecken, statt einer Beschreibung davon.

Die Zugliste selbst lässt sich in die Zwischenablage kopieren oder als Textdatei herunterladen, um sie neben einem echten Rätsel zu lesen, und als CSV für die Tabellenkalkulation. Der Download kennt die Grenze der gedruckten Tabelle nicht: Bei fünfzehn Scheiben enthält die Datei weiterhin alle 32.767 Züge.

Warum die Liste bei 12 Scheiben endet

Lösungen verdoppeln sich mit jeder Scheibe. Zwölf Scheiben sind 4.095 Züge — eine lange, aber brauchbare Tabelle. Dreizehn sind 8.191, zwanzig sind 1.048.575, und kein Browser macht aus einer Tabelle mit einer Million Zeilen etwas, das ein Mensch benutzen kann. Über zwölf Scheiben nennt diese Seite die genaue Zahl und behält das laufende Brett — und die Downloads oben enthalten weiterhin jeden Zug: Die Lösung gehört Ihnen also nach wie vor, sie wird nur nicht gedruckt. Geht es allein um die Zahlen, reicht der Rechner bis vierundsechzig Scheiben und darüber hinaus.

Häufige Fragen

Was macht der Türme-von-Hanoi-Löser?

Er gibt die kürzestmögliche Zugfolge aus, die alle Scheiben auf einem Turm sammelt. Geben Sie ihm eine Scheibenzahl, löst er die klassische vollständige Umschichtung; geben Sie ihm eine halb fertige Stellung, löst er von dort aus — und das können die meisten Löser nicht.

Ist die Lösung die kürzeste?

Ja. Der Löser ist nicht nur richtig, sondern nachweislich optimal: Aus einem vollen Startstapel erzeugt er genau 2ⁿ − 1 Züge, und aus jeder anderen erlaubten Stellung den tatsächlich kürzesten Weg zum Ziel. Eine Folge mit weniger Zügen gibt es nicht.

Kann er aus einer schon begonnenen Stellung lösen?

Ja — dafür ist die eigene Startstellung da. Legen Sie jede Scheibe auf den Turm, auf dem sie gerade liegt, und der Löser bringt die Sache in den wenigsten von dort aus möglichen Zügen zu Ende, meist in weit weniger als beim Neuanfang.

Kann ich eine Lösung teilen oder als Lesezeichen speichern?

Ja. Die Adresszeile enthält immer das Brett, das Sie ansehen: /de/solver/?disks=5&from=A&to=C ist eine vollständige Umschichtung mit fünf Scheiben, und eine eigene Stellung ergänzt einen Code wie pos=CBBAA, ein Buchstabe je Scheibe, beginnend bei der kleinsten. Kopieren Sie den Link, und er öffnet genau dieses Rätsel wieder.

Kann ich die Zugliste herunterladen?

Ja, als einfache .txt-Datei oder als .csv mit einer Zeile je Zug, gleich neben der Kopierschaltfläche. Der Download funktioniert auch für die sehr langen Lösungen, die die Seite nicht als Tabelle druckt — eine Antwort mit 15 Scheiben bleibt also Ihre.

Wie lese ich die Zugliste?

Jede Zeile nennt einen Zug: die Scheibennummer, den Turm, den sie verlässt, und den Turm, auf dem sie landet. Scheibe 1 ist die kleinste. Spielen Sie sie der Reihe nach, und das Rätsel löst sich von selbst; Sie müssen nie überlegen, welche Scheibe erlaubt ist, denn jeder aufgeführte Zug ist es bereits.

Warum endet die Zugliste bei 12 Scheiben?

Eine Lösung mit 12 Scheiben hat 4.095 Züge. Bei 20 Scheiben wären es 1.048.575 Zeilen, die kein Browser sinnvoll darstellt — über 12 Scheiben nennt die Seite deshalb die genaue Zugzahl und die Formel statt der Liste, und das laufende Brett spielt die Lösung weiterhin ab.