Türme von Hanoi

Datei:Hanoiklein.jpg

Die Türme von Hanoi

Die Türme von Hanoi sind ein mathematisches Knobel- und Geduldsspiel.

Aufbau

Das Spiel besteht aus drei Feldern, auf die Scheiben verschiedener Größe gelegt werden können. Zu Beginn sind alle Scheiben auf einem Feld, der Größe nach geordnet, mit der größten Scheibe unten und der kleinsten oben.

Bei jedem Zug darf die oberste Scheibe eines beliebigen Feldes auf eines der beiden anderen Felder gelegt werden, vorausgesetzt, dort liegt nicht schon eine kleinere Scheibe. Zu jedem Zeitpunkt des Spieles sind also die Scheiben auf jedem Feld der Größe nach von unten nach oben sortiert.

Ziel des Spiel ist es, den kompletten Scheiben-Stapel von einer Seite auf das gegenüberliegende Feld zu versetzen.

Geschichte

Vermutlich wurde das Spiel 1883 vom französischen Mathematiker Edouard Lucas erfunden. Er dachte sich dazu die Geschichte aus, dass indische Mönche im großen Tempel zu Benares, im Mittelpunkt der Welt, einen Turm aus 64 goldenen Scheiben versetzen müssten, und wenn ihnen das gelungen sei, wäre das Ende der Welt gekommen.

In der Geschichte lösen die Mönche das Problem folgendermaßen: Der älteste Mönch erhält die Aufgabe, den Turm aus 64 Scheiben zu versetzen. Da er die komplexe Aufgabe nicht bewältigen kann, gibt er dem zweitältesten Mönch die Aufgabe, die oberen 63 Scheiben auf einen Hilfplatz zu versetzen. Er selbst (der Älteste) würde dann die große letzte Scheibe zum Ziel bringen. Dann könnte der Zweitälteste wieder die 63 Scheiben vom Hilfsplatz zum Ziel bringen.

Der zweitälteste Mönch fühlt sich der Aufgabe ebenfalls nicht gewachsen. So gibt er dem drittältesten Mönch den Auftrag, die oberen 62 Scheiben zu transportieren, und zwar auf den endgültigen Platz. Er selbst (der Zweitälteste) würde dann die zweitletzte Scheibe an den Hilfsplatz bringen. Schließlich würde er wieder den Drittältesten beauftragen, die 62 Scheiben vom Zielfeld zum Hilfsplatz zu schaffen. Dies setzt sich nun bis zum 64. Mönch (dem Jüngsten) fort, der die Aufgabe, die kleinste und oberste Scheibe zu verschieben, alleine bewältigen kann.

Da es 64 Mönche im Kloster gibt und alle viel Zeit haben, können sie das Problem in endlicher, wenn auch sehr langer Zeit lösen.

Lösungsalgorithmus

Die Geschichte um die Mönche illustriert zugleich den Lösungsalgorithmus. Man kann Türme von Hanoi mit verschiedenen Anzahlen von Scheiben spielen. Das Lösungsprinzip ändert sich dadurch nicht.

Zur Erläuterung werden die Stäbe von links nach rechts mit A, B und C bezeichnet und die Scheiben von der Kleinsten bis zur Größten mit S₁ bis S_n, wobei n die Anzahl der Scheiben ist. Die Angabe S₁-AC bedeutet zum Beispiel, dass die Scheibe S₁ vom Stab A auf den Stab C verschoben wird.

Der triviale Fall mit n=1, also einer Scheibe, ist offensichtlich in einem Zug lösbar. Es genügt den Zug S₁-AC auszuführen.

Der Fall n=2, also mit zwei Scheiben, ist ebenfalls einfach. Zuerst wird die obere kleine Scheibe auf den Stab B gelegt, anschließend die untere größere Scheibe auf den Stab C gelegt und abschließend die kleine Scheibe vom Stab B auf den Stab C gelegt. Die Aufgabe wird also durch drei Züge:

S₁-AB | S₂-AC | S₁-BC

gelöst.

Lösung des Problems mit drei Scheiben.

Für den Fall n=3, also mit drei Scheiben, stellen wir zunächst folgende Vorüberlegung an:

1. Um die dritte (unterste) Scheibe nach rechts zu bewegen, muss der "2er-Stapel" darüber in die Mitte.
2. Um diesen "2er-Stapel" in die Mitte zu bekommen, muss der "1er-Stapel" darüber, also die oberste, kleinste Scheibe, nach rechts.

Man muss also den ersten Zug nach rechts ausführen, die 2. Scheibe in die Mitte bewegen und dann die kleinste Scheibe von rechts in die Mitte:

S₁-AC | S₂-AB | S₁-CB

Diese Zugfolge entspricht also dem Fall mit 2 Scheiben, wobei jedoch die Stabe B und C vertauschte Rollen spielen.

Jetzt kann die dritte, unterste Scheibe nach rechts verschoben werden. Dies entspricht dem Zug:

S₃-AC

Zum Schluss muss der "2er-Stapel" von der Mitte nach rechts verschoben werden, damit ist die Aufgabe gelöst. Dies funktioniert genauso wie die Zugfolge am Anfang, nur dass Stab A mit Stab B, Stab B mit Stab C und Stab C mit Stab A verstauchte Rollen spielen. Wir benötigen also folgende Zugfolge:

S₁-BA | S₂-BC | S₁-AC

Insgesammt werden hier also 7 Spielzüge benötigt.

Lösung des Problems mit vier Scheiben.

Für jede zusätzliche Scheibe gilt: Zuerst den Stapel mit einer Scheibe weniger auf den mittleren Platz bringen, dann die unterste Scheibe nach rechts und danach den Stapel von der Mitte nach rechts. Um jetzt mit diesem Lösungsalgorithmus das Problem mit 4 Scheiben zu lösen, bewegt man die drei Scheiben auf den Turm, der nicht das Ziel ist (hier also B), bewegt dann die Scheibe 4 auf den Zielstab, um danach die drei Scheiben von B nach C zu bewegen. Hier sind die 15 Lösungsschritte:

S₁-AB | S₂-AC | S₁-BC | S₃-AB | S₁-CA | S₂-CB | S₁-AB

S₄-AC

S₁-BC | S₂-BA | S₁-CA | S₃-BC | S₁-AB | S₂-AC | S₁-BC

Mathematische Betrachtung

Die minimale Zuganzahl kann induktiv bestimmt werden:

• Für eine Scheibe ist ein Zug nötig.
• Bei mehreren Scheiben muss die größte Scheibe mindestens einmal bewegt werden, und zu diesem Zeitpunkt müssen sich alle anderen Scheiben an der dritten Stelle befinden. Die minimale Zuganzahl beträgt also mindestens das Doppelte der minimalen Zuganzahl für den um eine Scheibe kleineren Turm, plus den einen Zug, um die größte Scheibe zu bewegen. Der Algorithmus zeigt, dass dies tatsächlich auch die minimale Zuganzahl ist.

Man kann induktiv zeigen, dass die beschriebene minimale Zuganzahl durch die Formel $2^{n}-1$ bei $n$ Scheiben gegeben ist. Bei einem Turm von 8 Scheiben (die gängigste Variante) sind also 255 Züge nötig.

Für den Stapel aus 64 Scheiben würden 18.446.744.073.709.551.615, also mehr als 18 Trillionen Züge benötigt. Würde man jede Sekunde eine Scheibe bewegen, bräuchte man dafür 584.554.049.253 Jahre, 10 Monate, 8 Tage 1h 41 m 39 s .

Es gelten weiterhin folgende Regeln für die Häufigkeit, mit der eine Scheibe bewegt wird:

• Die größte Scheibe $S_{n}$ wird einmal bewegt, und zwar beim mittleren Zug Nr. $2^{n-1}$ der Zugfolge.
• Die zweitgrößte Scheibe $S_{n-1}$ zweimal, und zwar nach dem 1. und 3. Viertel der um 1 erhöhten Zugfolge (Züge Nr. $2^{n-2}$ und $3*2^{n-2}$
• Allgemein gilt: Scheibe $S_{n-k}$ wird $2^{k}$ mal bewegt.

• Die kleinste Scheibe $S_{1}$ wird bei jedem 2. Zug bewegt, beginnend mit dem 1. Zug.
• Die zweitkleinste Scheibe $S_{2}$ wird bei jedem 4. Zug bewegt, beginnend mit dem 2. Zug.
• Allgemein gilt: Scheibe $S_{k}$ wird nach jeweils $2^{k}$ Zügen erneut bewegt, das erste mal bei Zug Nr. $2^{k-1}$.

Auf diese Weise ist es möglich, an jedem Punkt der Zugfolge zu bestimmen, welche Scheibe als nächstes bewegt werden muss.

Hinweise zum Spiel

• Es gibt nur einen optimalen Lösungsweg, um den Turm auf ein bestimmtes Feld, z.B. rechts, zu bewegen. Jede Abweichung von diesem Weg führt zu einer der folgenden Situationen, an denen eine Abweichung erkennbar ist:
  • Die zuletzt bewegte Scheibe muss gleich noch einmal bewegt werden, entweder auf den dritten Stab oder zurück.
  • Eine bestimmte Spielsituation wird erneut erreicht, d.h., es wurde ein "Umweg" gemacht.
• Bei größerer Scheibenzahl ist es sinnvoll, die Spielzüge schriftlich zu notieren. Dabei kann die zu bewegende Scheibe im Voraus angegeben werden.
• bei vorgegebenem Zielstab kann man beim ersten Spielzug den größten Fehler machen. Bei ungerader Scheibenzahl muss beim ersten Zug die kleinste Scheibe auf den späteren Zielstab, bei gerader Scheibenzahl auf den anderen.

Programme

Obwohl es auf den ersten Blick kompliziert klingt, gibt es für das Spiel also einen ganz einfachen rekursiven Algorithmus. Da sich ein Computerprogramm zur Lösung des Spiels mit wenigen Zeilen schreiben lässt, ist Türme von Hanoi ein klassisches Beispiel für rekursive Programmierung. Die rekursive Lösung eines Problems zeichnet sich dadurch aus, dass ein komplexes Problem aufgeteilt wird in ein triviales Problem (Transport nur einer Scheibe) und ein weniger komplexes Problem (Transport eines kleineren Turms), auf das dann wieder der gleiche Algorithmus angewandt werden kann.

Beispiel-Algorithmus rekursiv (geschrieben in Pseudocode):

Lösungsalgorithmus von Buneman und Levy (1980)

Die rekursive Variante ist einfacher herzuleiten und es ist auch einzusehen, warum sie funktioniert. Aber Buneman und Levy haben 1980 einen Lösungsalgorithmus beschrieben, der die gleiche Zugfolge liefert, für Menschen aber viel einfacher aussieht und ohne Rekursion auskommt:

Beispiel-Implementation (geschrieben in Pseudocode):

Ausführen bis der gesamte Turm verschoben wurde
    1. Die kleinste verschiebbare Scheibe auf den Stapel rechts von ihr legen
       (bzw. auf den ersten, wenn die Scheibe auf dem letzten Stapel liegt).
    2. Die zweitkleinste verschiebbare Scheibe auf den einzig möglichen
       Stapel verschieben.

Ist die Scheibenanzahl ungerade, so wird der Turm insgesamt um ein Feld nach rechts bewegt; ist sie gerade, um zwei Felder.

Weblinks

• Hanoi Tutorial mit illustrierter Anwendung zur Erstellung von Lösungen und kommentiertem Algorithmus
• mister-mueller - Anschauliche Darstellung mit einer ausführlichen Erklärung.
• hanoimania - Implementation in 110 verschiedenen Programmiersprachen.
• Towers of Hanoi bei Wolfram Research - Zusammenhang zu verschiedenen mathematischen Fachgebieten
• "Towers of Hanoi" von Apostolos Syropoulos - mit vielen weiteren Algorithmen
• Online-Spiel der Hanoi Türme