Der Turm von Hanoi Mystery Cache

Ein Rätselcache, der sich mit dem (Mathematik-) Rätselspiel "Turm von Hanoi" befaßt.

Die Geschichte von den Türmen aus Hanoi

1883 hatte der französische Mathematiker Edouard Lucas jene kleine Geschichte ersonnen, die fortan als die Geschichte der Türme von Hanoi selbst Geschichte machte:

Im Großen Tempel von Benares, unter dem Dom, der die Mitte der Welt markiert, ruht eine Messingplatte, in der drei Diamantnadeln befestigt sind, jede eine Elle hoch und so stark wie der Körper einer Biene. Bei der Erschaffung der Welt hat Gott vierundsechzig Scheiben aus purem Gold auf eine der Nadeln gesteckt, wobei die größte Scheibe auf der Messingplatte ruht, und die übrigen, immer kleiner werdend, eine auf der anderen. Das ist der Turm von Brahma. Tag und Nacht sind die Priester unablässig damit beschäftigt, den festgeschriebenen und unveränderlichen Gesetzen von Brahma folgend, die Scheiben von einer Diamantnadel auf eine andere zu setzen, wobei der oberste Priester nur jeweils eine Scheibe auf einmal umsetzen darf, und zwar so, dass sich nie eine kleinere Scheibe unter einer größeren befindet. Sobald dereinst alle vierundsechzig Scheiben von der Nadel, auf die Gott sie bei der Erschaffung der Welt gesetzt hat, auf eine der anderen Nadeln gebracht sein werden, werden der Turm samt dem Tempel und allen Brahmanen zu Staub zerfallen, und die Welt wird mit einem Donnerschlag untergehen.

Hm. Das Ende der Zeit sei erreicht, wenn all diese 64 Scheiben auf einer dieser Nadeln wieder nach diesen Regeln aufgebaut werden. Brahma ist ein Gott der Hindus. Wieso diese Türmchen dann später in Hanoi angesiedelt wurden, also in Vietnam, in den Geschichten meist auch mit weniger Scheiben, konnte ich nicht herausfinden, aber das ist ja auch egal.

Auf die Frage hin, ob der oberste Priester wüsste, wie denn die Scheiben zu setzen seien, soll der noch gesagt haben, dass nichts leichter sei als das. Er braucht ja nur die unterste Scheibe zu versetzen, wenn seine Schüler alle die darüber bereits versetzt haben, so dass die unterste frei werde. Dann können die Schüler, die nun wüssten, wie die anderen 63 Scheiben zu bewegen sind, diese wieder auf der untersten 64. Scheibe aufbauen und der Turm wäre versetzt.

Doch warum soll dann das Ende der Zeit einbrechen?

Auch das hat seinen Grund. Wenn für 3 Scheiben 7 Züge notwendig sind, für 4 bereits 15 und für 6 insgesamt 63 Züge, so wäre die Anzahl der Züge für 64 Scheiben wie folgt

2⁶⁴-1  

und das sind:

2 · 2 · 2 · 2 · ... (64 Zweien, die da miteinander malgenommen werden) -1

also

18.446.744.073.709.551.615 Züge

Wenn jede Scheibe innerhalb einer schlappen Sekunde umgesetzt wird, macht das an die580 Milliarden Jahre. Kleiner Vergleich zum Mitdenken, unser Sonnensystem ist erst 4½ Milliarden Jahre alt. Für gerade mal 5 Milliarden Jahre wird das Licht der Sonne noch reichen. Wer auch immer dann weiter die Scheiben umlegen möchte, er macht es dann im Dunkeln, bzw. nicht mehr in diesem Sonnensystem.

Lustig, das ist eine dieser mathematischen Aufgaben, die man zwar berechnen kann, aber nie erleben wird. 64 Scheiben umzusetzen würde reichlich lange dauern. Auch eine Computersimulation wird es nicht schaffen. Was nützt es da, 1000 mal in der Sekunde einige Scheiben rechnerisch bewegen zu können, auch das würde Jahrmillionen dauern. 

Das Prinzip des Spiels "Turm von Hanoi" ist relativ schnell erklärt:

Das Spiel besteht aus drei gleichgroßen Stäben A, B und C, auf die mehrere gelochte Scheiben gelegt werden, alle verschieden groß. Zu Beginn liegen alle Scheiben auf Stab A, der Größe nach geordnet, mit der größten Scheibe unten und der kleinsten oben. Ziel des Spiels ist es, den kompletten Scheiben-Stapel von A nach C zu versetzen.

Bei jedem Zug darf die oberste Scheibe eines beliebigen Stabes auf einen der beiden anderen Stäbe gelegt werden, vorausgesetzt, dort liegt nicht schon eine kleinere Scheibe. Folglich sind zu jedem Zeitpunkt des Spieles die Scheiben auf jedem Feld der Größe nach geordnet.

(Quelle: Wikipedia).

Die kürzeste mögliche Lösung, also die minimale Anzahl der Züge, läßt sich vorab berechnen, denn diese ist von der Anzahl der Scheiben abhängig, mit denen gespielt wird.

Ein Spiel mit n Scheiben braucht nämlich: 2^n-1 Züge. Die Zugfolge für die kürzeste mögliche Lösung ist natürlich auch bekannt, wobei intereßanter Weise die Reihenfolge der Züge für die kürzeste Lösung für eine gerade Anzahl von Scheiben anders ist als die für eine ungerade Anzahl von Scheiben.

Bei z.B. fünf (5) Scheiben besteht die kürzeste Lösung aus 2^5-1 = 31 Zügen.

Für diesen Rätselcache spielen wir auch mit fünf Scheiben. Dabei gelten die folgenden Rahmenbedingungen:

• Es gibt drei Stäbe Names "Start" (=der Ausgangßtab, auf dem am Anfang alle Scheiben sind), "Mitte" (=der mittlere Hilfßtab) und "Ziel" (=der Zielstab, auf dem am Ende alle Scheiben sein sollen).

• Die Scheiben sind von 1 bis 5 durchnummeriert, wobei 5 die größte Scheibe (also die, die zu Anfang ganz unten liegt) und 1 die kleinste Scheibe (also, die Anfang oben liegt) ist.

• Wird im folgenden nach der Summe der Scheiben auf einem bestimmten Stab gefragt, dann sind die Nummer der Scheiben gemäß obiger Definition einfach zu addieren. Beispiel: liegen auf dem mittleren Stab nach dem 7. Zug die Scheiben 4 und 1, dann ist die Summe für den mittleren Stab folglich 5.

• Sollte keine Scheibe auf einem Stab sein, dann ist die Summe 0 (null).

• Sollte auf einem Stab nur eine Scheibe sein, dann ist die Summe gleich dem Wert der Scheibe.

• Es wird davon ausgegangen, daß die Zugfolge der kürzest möglichen entspricht.

Alles klar, die Scheiben bereit gelegt? Dann kann es los gehen!

A = Summe der Scheiben auf Mitte nach dem 4. Zug

B = Summe der Scheiben auf Start nach dem 23. Zug

C = Summe der Scheiben auf Start nach dem 13. Zug

D = Sind nach dem 22. Zug die Scheiben 2 und 3 auf Start? ja ⇒ D = 6 , nein ⇒ D = 0

E = Wie viele Scheiben befinden sich nach dem 28. Zug in der Mitte? kein ⇒ E = 2 , eine ⇒ E = 1 , zwei ⇒ E = 4

F = Summe der Scheiben auf Mitte nach dem 6. Zug

G = Summe der Scheiben auf Ziel nach dem 15. Zug

H = Wie viele Scheiben befinden sich nach dem 13. Zug auf Ziel? kein ⇒ H = 9 , eine ⇒ H = 6 , zwei ⇒ H = 2

I = Summe der Scheiben auf Ziel nach dem 8. Zug

J = Summe der Scheiben auf Start nach dem 24. Zug

Die Dose befindet sich bei:

• N53° A B , C D E
• E12° F G , H I J

 Viel Spaß beim Spielen und lösen der Aufgaben.