Wie man die Türme von Hanoi löst

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

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.

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. ^*)

Bild 3

Lösung der Türme von Hanoi

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.

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.

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.

Bild 6

Also lasst uns die Scheibe bewegen.

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".

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.

^*) 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.