Türme von Hanoi: häufig gestellte Fragen

Es gibt einen, und er ist eher mechanisch als raffiniert: Bewegen Sie bei jedem ungeraden Zug die kleinste Scheibe um einen Turm in dieselbe Richtung — nach links bei einer ungeraden Scheibenzahl, nach rechts bei einer geraden, an den Enden umlaufend, sodass bei drei Scheiben ihr allererster Zug von A nach C springt. Bei jedem geraden Zug gibt es immer nur einen erlaubten Zug, der die kleinste Scheibe nicht berührt, den machen Sie also, ohne nachzudenken. Im Wechsel spielen die beiden ein perfektes Spiel, ohne dass Sie einen einzigen Schritt vorausplanen. Die Strategieseite arbeitet es durch.

Beginnen Sie mit dem ganzen Stapel auf dem linken Turm, die kleinste Scheibe oben. Ziel ist derselbe Stapel auf dem rechten Turm. Drei Regeln: immer nur eine Scheibe, immer nur die oberste eines Turms, und nie eine größere Scheibe auf eine kleinere. Bei drei Scheiben ist das kürzeste Spiel sieben Züge in drei Gruppen: A→C, A→B, C→B baut die beiden kleinsten Scheiben auf dem mittleren Turm auf; A→C lässt die größte Scheibe hinüber; und B→A, B→C, A→C baut jene beiden obendrauf wieder auf. Die Anleitung, mit einem Übungsfeld.

Leicht zu lernen, und auf genau eine Weise schwer: Mit jeder Scheibe mehr wird es doppelt so lang. Drei Scheiben sind sieben Züge, und die meisten Menschen — Kinder ab etwa sechs — schaffen es im ersten Anlauf. Irgendwo bei fünf oder sechs Scheiben hört Ausprobieren auf zu funktionieren und man braucht eine Methode; und das Schwere an der Methode ist, Zügen zu trauen, die rückwärts aussehen, etwa einen ganzen Stapel auf dem mittleren Turm aufzuschichten, während das Ziel rechts liegt. Wenn die rekursive Idee einmal sitzt, ist jede Größe dasselbe Rätsel. Warum die rekursive Idee das ganze Rätsel ist.

Es gibt keinen Verband, der Geschwindigkeitsrekorde für die Türme von Hanoi anerkennt, wie es ihn für den Zauberwürfel gibt — behauptete Zeiten sind also nicht vergleichbar und nennen meist nicht einmal die Scheibenzahl, die als Einzige zählt. Rechnen Sie es lieber aus: Ein perfektes Spiel mit n Scheiben sind 2ⁿ − 1 Züge, und geübte Spielende halten etwa zwei Züge pro Sekunde. Das sind rund vier Sekunden für drei Scheiben, etwa neun Minuten für zehn Scheiben und ihre 1.023 Züge, und ungefähr viereinhalb Stunden für 15 Scheiben und ihre 32.767. Das Spielfeld dieser Website merkt sich Ihre wenigsten Züge je Scheibenzahl in Ihrem Browser und zeigt Ihre Zeit auf dem Ergebnisbildschirm. Der Rechner gibt die Dauer für jede Größe.

2ⁿ − 1, und das ist eine bewiesene Untergrenze, kein bestbekanntes Ergebnis. Drei Scheiben brauchen 7 Züge, vier brauchen 15, fünf brauchen 31, zehn brauchen 1.023, und 15 brauchen 32.767. Der Beweis hat zwei Hälften: Die rekursive Methode erreicht diese Zahl, und keine Lösung kann sie unterbieten, weil die größte Scheibe sich mindestens einmal bewegen muss und jede kleinere Scheibe über ihr zuvor auf den freien Turm geräumt und danach zurückgeholt werden muss. Beide Hälften des Beweises, vollständig.

T(n) = 2·T(n − 1) + 1, mit T(0) = 0. Sie liest sich direkt aus der Methode ab: Um n Scheiben zu bewegen, räumen Sie n − 1 Scheiben aus dem Weg, bewegen eine Scheibe hinüber und holen jene n − 1 Scheiben zurück — zwei kleinere Lösungen plus ein einzelner Zug. Ausgerollt ergibt das T(n) = 2ⁿ − 1, was Sie per Induktion prüfen können: Ist T(n − 1) = 2ⁿ⁻¹ − 1, dann ist T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1. Die Rekursionsgleichung lösen, Schritt für Schritt.

Im komplexitätstheoretischen Sinn nicht, trotz der exponentiellen Zugzahl. Der Algorithmus ist ein paar Zeilen lang, den nächsten Zug zu bestimmen braucht konstante Zeit, und die Lösung ist nur deshalb exponentiell lang, weil die Antwort es ist: 2ⁿ − 1 Züge auszugeben geht nicht in weniger als 2ⁿ − 1 Schritten. Es ist nicht NP-schwer, und den kürzesten Weg zwischen zwei beliebigen erlaubten Stellungen auf drei Türmen zu finden ist ebenfalls effizient lösbar. Die wirklich schwere Fassung ist das Rätsel mit vier Türmen, dessen optimale Lösung 1941 vermutet und erst 2014 von Thierry Bousch bewiesen wurde. Der Algorithmus und was er kostet.

Mit der Frame–Stewart-Methode. Mit vier Türmen bewegt man nicht länger n − 1 Scheiben am Stück: Man wählt eine Teilung k, bringt die obersten k Scheiben mit allen vier Türmen auf einen freien Turm, bringt die restlichen n − k Scheiben mit nur drei Türmen ans Ziel — der freie ist belegt, dieser Teil ist also das klassische Rätsel — und legt dann die k Scheiben obenauf. Probiert man jedes k durch und nimmt das beste, erhält man die optimale Zahl, und die bricht spektakulär ein: 15 Scheiben fallen von 32.767 Zügen auf drei Türmen auf 129 auf vieren. Das Rätsel mit vier Türmen spielen.

Teile und herrsche, ausgedrückt als Rekursion. Die Standardlösung ist eine Funktion — bringe n − 1 Scheiben vom Ausgang auf den freien Turm, bringe Scheibe n vom Ausgang ans Ziel, bringe jene n − 1 Scheiben vom freien Turm ans Ziel — mit einem Basisfall, der nichts tut, sobald n null erreicht. Es gibt einen gleichwertigen iterativen Algorithmus ganz ohne Rekursion: die kleinste Scheibe wiederholt um einen Turm in eine feste Richtung bewegen und dann den einzigen anderen erlaubten Zug machen. Beide erzeugen genau dieselbe Zugfolge, denn die optimale Lösung ist eindeutig. Der Algorithmus, Zeile für Zeile.

Eine rekursive Funktion und drei Parameter: void hanoi(int n, char from, char to, char via) — ist n null, return; sonst rufen Sie hanoi(n − 1, from, via, to) auf, geben den Zug from → to aus und rufen dann hanoi(n − 1, via, to, from) auf. Aufgerufen wird sie als hanoi(3, 'A', 'C', 'B'). Sammeln Sie die Züge in einem std::vector<std::pair<char, char>>, statt sie auszugeben, wenn der Aufrufer sie braucht, und lassen Sie n ein schlichtes int: Mit einem vorzeichenlosen Parameter wird eine versehentlich übergebene negative Zahl stillschweigend zu rund vier Milliarden, und die Rekursion läuft bis zum Stapelüberlauf, statt an einer einfachen Prüfung n &lt; 0 zu scheitern. Das vollständige C++-Programm, Zeile für Zeile erklärt.

Das sind zwei verschiedene Verwendungen eines Stacks, und es lohnt sich, sie auseinanderzuhalten. Die Türme sind Stacks: Jeder ist last-in-first-out, Sie fassen immer nur die oberste Scheibe an, und ein Zug ist ein Pop von einem Turm und ein Push auf einen anderen — weshalb die Regelprüfung ein einziger Vergleich mit der Spitze des Ziels ist. Getrennt davon kann ein expliziter Stack die Rekursion ersetzen: Legen Sie die ganze Aufgabe (n, from, to, via) ab, dann in der Schleife eine Aufgabe herunternehmen und, falls sie noch Scheiben hat, ihre drei Teile in umgekehrter Reihenfolge ablegen: den zweiten Transfer, den einzelnen Zug von Scheibe n, dann den ersten Transfer. Die umgekehrte Reihenfolge ist wichtig, weil ein Stack das zuletzt Abgelegte zuerst zurückgibt. Genau das erledigt die Laufzeitumgebung der Sprache in der rekursiven Fassung für Sie. Die Lösung ganz ohne Rekursion.

In der KI ist das Rätsel ein Suchproblem, keine Formel. Jeder Zustand ist eine Zuordnung jeder Scheibe zu einem Turm, es gibt also 3ⁿ davon, und die erlaubten Züge sind die Kanten dazwischen; eine Suche — Breitensuche, A* oder IDA* mit einer Heuristik wie der Zahl der noch nicht am Zielturm liegenden Scheiben — findet den kürzesten Weg vom Start- zum Zielzustand. Es ist seit dem General Problem Solver von Newell, Shaw und Simon ein Standard-Testproblem, weil es ein sauberes Beispiel für Mittel-Zweck-Analyse und für Zielzerlegung ist: Das Teilziel „die größte Scheibe bewegen“ ist nur erreichbar, wenn zuvor ein Teilziel erfüllt wird, das den Fortschritt scheinbar rückgängig macht. Beachten Sie: Der rekursive Algorithmus ist keine Suche — er ist die bekannte Lösung und betrachtet nie einen Zustand, den er nicht verwendet. Dasselbe Rätsel als psychologische Aufgabe.