Die Türme von Hanoi



Reset mit F5


Der Turm aus drei bis sieben Scheiben mit verschiedenen grössen soll vom Mittelpfosten zum rechten oder linken Pfosten verschoben werden. Der dritte Pfosten rechts oder links ist der Hilfsplatz (Ausweichplatz) damit die Scheiben der richtigen Reihenfolge aufgestapelt werden können.
  • Es kann nur die oberste Scheibe vom einem Turm bewegt werden.
  • Es kann nie eine grössere Scheibe auf eine kleinere Scheibe gelegt werden.


  • Spiele bei äbe.ch      Download:   TurmVonHanoi.zip

    Die grafische Darstellung der Schritte

    Türme von Hanoi, gespielt mit drei Scheiben (sieben Schritte)
    Türme von Hanoi, gespielt mit vier Scheiben (fünfzehn Schritte)
    Der Turm von Hanoi (auch als Turm des Brahma oder Weltende Puzzle bekannt) wurde 1883 von dem französischen Mathematiker Edouard Lucas erfunden. Er wurde durch folgende Legende inspiriert: Im Grossen 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össte Scheibe auf der Messingplatte liegt, 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 die Priester nur jeweils eine Scheibe auf einmal umsetzen dürfen, und zwar so, dass sich nie eine kleinere Scheibe unter einer grösseren befindet. Sobald einmal 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.
    Doch das wird noch eine Weile dauern denn:
    Mit vier Scheiben sind 15 Schritte nötig, verdoppeln wir jedoch die Höhe des Turms auf 8 Scheiben, so werden nicht, wie erwartet, 30 Schritte benötigt, sondern 255. Wir sprechen in diesem Fall von einem exponentiellen Wachstum. Um die Auswirkung des exponentiellen Wachstums zu verstehen, nehmen wir an, dass die Mönche von Brahma eine Scheibe pro Sekunde verschieben können und dass sie bis zur Vollendung der Aufgabe Tag und Nacht arbeiten. Jetzt können wir mit Hilfe der obigen Daten folgende Zeiten ermitteln:
       
    Turmhöhe: Notwendige Zeit:
      5 Scheiben 31 Sekunden
    10 Scheiben 17 Minuten
    20 Scheiben 12 Tage
    30 Scheiben 34 Jahre
    40 Scheiben 348 Jahrhunderte
    50 Scheiben 35 Jahrmillionen

    Diese Tabelle zeigt, dass der Aufwand die Türme zu verschieben unvorstellbar gross ist. Machen wir die Berechnung für den 64-stöckigen Turm der Mönche von Brahma, so kommen wir auf 584 Milliarden Jahre Eine unvorstellbare Zahl, bedenke, unser Universum ist schätzungsweise 13.5 Milliarden Jahre.
    Die Grenzen der Computer:

    Auch modernste Computer stehen solchen Aufgaben machtlos gegenüber. Obwohl sie pro Sekunde viele tausend Scheiben bewegen können, bräuchten sie zur Verschiebung eines Turms mit 64 Scheiben Millionen Jahre. Kein Mensch möchte solange auf das Resultat dieser Berechnungen warten. Und auch wenn es dereinst Computer geben würde, die diese Aufgabe in vernünftiger Zeit lösen können, dann genügt es infolge des beschleunigten Wachstums, einfach eine einzige Scheibe mehr auf den Turm zu setzen und auch diese mächtigen Computer würden an der Aufgabe scheitern. Bestimmt haben Sie bereits daran gedacht, einfach ein anderes Vorgehen als das obige zur Verschiebung der Türme zu entwerfen, welches mit weniger Arbeitsschritten auskommt. Man kann jedoch mathematisch beweisen, dass es keine andere Möglichkeit zur Verschiebung von Hanoi- Türmen geben kann, welches weniger Schritte als dasjenige der Priester von Brahma produziert. Aktuell kennt die Informatik viele tausende Probleme und Anwendungen mit ähnlichem Charakter und oft liegt die Schwierigkeit gerade in der Erkennung dieser Eigenschaften. Daher hat es sich die theoretische Informatik zur Aufgabe gemacht, diese Probleme zu studieren und zu katalogisieren. Dieses Bestreben hat auch wirtschaftliches Interesse, denn wer möchte schon, dass sich Leute mit der Lösung von Problemen beschäftigen, für die es einfach keine Lösung gibt.