Beim Turm von Hanoi sollen kreisförmige Scheiben so gestapelt werden, dass niemals eine größere Scheibe über eine kleinere zu liegen kommt. Die Scheiben haben alle in der Mitte ein Loch, und auf einer Grundplatte stehen drei senkrechte Stäbe. Zu Beginn befinden sich alle Scheiben zu einem Kegel gestapelt auf einem der Stäbe, zum Schluss sollen sie sich in genau dieser Reihenfolge auf einem anderen Stab befinden. Dazwischen dürfen nur Züge der folgenden Art ausgeführt werden:
Man nimmt die oberste Scheibe von einem Stab und legt sie auf einen anderen Stab, aber nur, wenn dadurch nicht eine größere Scheibe über eine kleinere zu liegen kommt.
Dies erscheint zunächst als einfache Aufgabe. Und wir können sie noch weiter vereinfachen, wenn wir mit weniger als sechs Scheiben beginnen. Wir werden sehen, dass es sich hier um ein binäres Geduldspiel handelt. Dazu betrachten wir wir verschiedene Anzahlen von Scheiben.
- Haben wir nur eine Scheibe zu versetzen, so können wir das ganz einfach mit einem Zug tun, 1=2¹-1.
- Haben wir zwei Scheiben, dann benötigen wir drei Züge, 3=2²-1.
- Für drei Scheiben benötigen wir sieben Züge, 7=2³-1.
- Im allgemeinen Fall für n Scheiben benötigen wir 2ⁿ-1 Züge
Damit wird die Anzahl der Züge bei Hinzunahme einer weiteren Scheibe näherungsweise verdoppelt, und wir haben ein binäres Geduldspiel vor uns.
Historisches: Im Original von Edouard Lucas aus dem Jahr 1883 hatte das Geduldspiel acht Scheiben. Dazu gehört die Geschichte, dass dies eine vereinfachte Version des Turms von Brahma sei. Indische Mönche im großen Tempel zu Benares, im Mittelpunkt der Welt, müssten einen Turm aus 64 goldenen Scheiben versetzen.
Einfacher Lösungsalgorithmus: Wir bezeichnen die drei Stäbe mit A, B und C. Die Aufgabe besteht darin, dass von A nach B umgestapelt werden soll. Wir nehmen an, dass es sich um eine gerade Anzahl von Scheiben handelt. Unter einem legalen Zug zwischen zwei Stapeln (z.B. A und B) verstehen wir die Bewegung einer Scheibe entweder von A nach B oder von B nach A so dass die kleinere oben liegende Scheibe bewegt wird. Folgende Zugfolge ist auszuführen.
- Führe den legalen Zug zwischen den Stapeln A und B aus.
- Führe den legalen Zug zwischen den Stapeln A und C aus.
- Führe den legalen Zug zwischen den Stapeln B und C aus.
- Falls das Ziel noch nicht erreicht ist, wiederhole die Zugfolge 1-3.
Falls eine ungerade Anzahl von Scheiben umgestapelt werden soll, müssen in dem obigen Algorithmis nur B und C vertauscht werden.
Ähnliche Geduldspiele: Es gibt Abweichungen mit mehr als drei Stäben, mehrfarbigen Scheiben usw. Einige Beispiele sowie weitere Lösungsalgorithmen findet man in Wikipedia [1], [2].
Design: Edouard Lucas
Hersteller: Haba und viele andere
Erscheinungsjahr: 1883
Mehr Infos:
