Wie man die Türme von Hanoi löst

Klassische Türme von Hanoi - am Anfang sind alle Scheiben auf dem Stab'A'.

Die Türme
Bild 1

Die Lösung des Rätsels ist, dass alle Scheiben mit möglichst wenigen Zügen auf dem Stab "C" liegen sollen. Ein Zug ist das Verschieben einer Scheibe von einem Stab auf den anderen, wobei größere Scheiben nicht auf kleineren liegen dürfen.

Die Türme
Bild 2

Beliebige Türme von Hanoi - am Anfang können die Scheiben in einer beliebigen Position sein, unter der Bedingung, dass keine größere Scheibe auf einer kleineren liegt (siehe Bild 3). Am Ende können die Scheiben beliebig anders liegen - aber unter der selben Bedingung. *)

Die Türme
Bild 3

Lösung der Türme von Hanoi

'Lösung' der kürzester Weg

Rekursive Lösung:

1. Identifiziere die größte Scheibe (= Scheibe N)

2. IF es möglich ist, die Scheibe auf den Zielstab zu bewegen
     THEN dann
     ELSE

3. Anderes Ziel: ordne (N−1)-Scheiben Turm auf einen Stab, der nicht dein Zielstab ist.

4. Gehe zu Punkt 1. ...


Ein paar Worte zur Nomenklatur:
Manche Autoren benutzen den Term "regular position" für jede beliebige 3N Aufstellung, welche die Regeln beachtet, dass keine größere Scheibe auf einer kleineren liegen darf, und "perfect position" für eine der 3 Aufstellungen, wenn alle Scheiben auf einem Stab liegen.
Also ist der obere Algorithmus die optimale Lösung zwischen "regular position" und "perfect position" oder zwischen "perfect position" und "regular position", aber nicht zwischen zwei "regular positions".

P.K. Stockmeyer


Lösung der Türme von Hanoi - von "regular" nach "perfect"

Fangen wir an das Rätsel zu lösen.
Lasst uns annehmen, damit es leichter ist, dass es unser Ziel ist, 4 Scheiben auf den Stab "C" zu legen - wie bei den klassischen Türmen von Hanoi (siehe Bild 2).
Lasst uns annehmen, dass wir "wissen", wie man einen "perfekten" 3 Scheiben Turm verschiebt.
Auf dem Weg zur Lösung bekommt man eine spezielle Aufstellung. Die Scheibe 4 ist auf dem Stab "A" und der 3 Scheiben Turm ist auf dem Stab "B", der Zielstab "C" ist leer.

Die Türme
Bild 4

Bei dieser Aufstellung müssen wir nun die Scheibe 4 von Stab "A" nach "C" übertragen und als nächstes verschieben wir den 3 Scheiben Turm mit ein bisschen Magie auf den Zielstab.

Lasst uns zurückdenken. Lasst uns vergessen, dass wir eine größere Scheibe als 3 haben. Scheibe 3 ist auf dem Stab "C", aber sollte sich auf dem Stab "B" befinden. Um das zu erreichen muss Scheibe 3 da sein, wo sie sich jetzt befindet und Stab "B" sollte frei sein. Scheiben 1 und 2 sollten auf Stab "A" sein. Unser Ziel ist also, Scheibe 2 auf den Stab "A" zu verschieben.

Die Türme
Bild 5

Lasst uns die Scheibe 3 vergessen (siehe Bild 6). Um Scheibe 2 nach Stab "A" verschieben zu können (über der dünnen blauen Linie), sind die Scheiben, die kleiner sind als Scheibe 2, auf Stab "B" gelegt. Unser Ziel ist jetzt also, Scheibe 1 nach Stab "B" zu verschieben. Wir sehen, dass das eine leichte Aufgabe ist, da Scheibe 1 von keiner anderen Scheibe blockiert wird und Stab "B" frei ist.

Die Türme
Bild 6

Also lasst uns die Scheibe bewegen.

Die Türme
Bild 7

Die oben beschriebenen Schritte werden durch den wiederholten Algorithmus in Die Türme von Hanoi verwendet, durch Drücken des "Hilf mir" Knopfes. Es wird eine Analyse der Aufstellung der Scheiben durchgeführt und ein einzelner Zug wird generiert, der auf dem kürzesten Weg zur Lösung führt. Das ist mit Absicht so.

Wenn man noch mal "Hilf mir" klickt, wiederholt der Algorithmus die Schritte der Analyse beginnend mit der größten Scheibe - in dem Fall Scheibe 4 - und generiert den nächsten Zug - Scheibe 2 von Stab "C" nach Stab "A".

Die Türme
Bild 8

Wenn ein rekursiver oder iterativer Algorithmus benötigt wird, welcher die Serie der Züge zur Lösung einer beliebigen Aufstellung der Türme von Hanoi generiert, sollte man eine Art back tracking programming verwenden, d.h. der Algorithmus sollte sich an die Schritte der Analyse erinnern und nicht jedes Mal von Anfang an analysieren.

Aber das ist eine andere, lange Geschichte.

Romek



*) Bemerke, dass diese Aufstellung nicht unbedingt der kürzeste Weg zwischen Anfang und Ende der Türme sein muss. Dies kann passieren wenn man falsche Züge währen des Lösens der klassischen Türme gemacht hat.