Die Legende der Türme von Hanoi soll erstmalig von Ed Lucas in einem Artikel in der französischen Zeitschrift »Cosmo« im Jahre 1890 veröffentlicht worden sein.[1] Der Legende nach standen vor langer Zeit im Tempel von Hanoi drei Säulen. Die erste war aus Kupfer, die zweite aus Silber und die dritte aus Gold. Auf der Kupfersäule waren einhundert Scheiben aufgestapelt. Die Scheiben hatten in der Mitte ein Loch und waren aus Porphyr[2]. Die Scheibe mit dem größten Umfang lag unten, und alle kleiner werdenden Scheiben lagen obenauf. Ein alter Mönch stellte sich die Aufgabe, den Turm der Scheiben von der Kupfersäule zur Goldsäule zu bewegen. In einem Schritt sollte aber nur eine Scheibe bewegt werden, und zudem war die Bedingung, dass eine größere Scheibe niemals auf eine kleinere bewegt werden durfte. Der Mönch erkannte schnell, dass er die Silbersäule nutzen musste; er setzte sich an einen Tisch, machte einen Plan, überlegte und kam zu einer Entscheidung. Er konnte sein Problem in drei Schritten lösen. Am nächsten Tag schlug der Mönch die Lösung an die Tempeltür:
§ Falls der Turm aus mehr als einer Scheibe besteht, bitte deinen ältesten Schüler, einen Turm von (N – 1) Scheiben von der ersten zur dritten Säule unter Verwendung der zweiten Säule umzusetzen.
§ Trage selbst die erste Scheibe von einer zur anderen Säule.
§ Falls der Turm aus mehr als einer Scheibe besteht, bitte deinen ältesten Schüler, einen Turm aus (N – 1) Scheiben von der dritten zu der anderen Säule unter Verwendung der ersten Säule zu transportieren.
Und so rief der alte Mönch seinen ältesten Schüler zu sich und trug ihm auf, den Turm aus 99 Scheiben von der Kupfersäule zur Goldsäule unter Verwendung der Silbersäule umzuschichten und ihm den Vollzug zu melden. Nach der Legende würde das Ende der Welt nahe sein, bis der Mönch seine Arbeit beendet hätte.
Nun, so weit die Geschichte. Wollen wir den Algorithmus zur Umschichtung der Porphyrscheiben in Java programmieren, so ist eine rekursive Lösung recht einfach. Werfen wir einen Blick auf das folgende Programm, das die Umschichtungen über die drei Pflöcke (engl. pegs) vornimmt:
class TowerOfHanoi {
static void move( int n, String fromPeg, String
toPeg, String usingPeg ) {
if ( n > 1 ) {
move( n - 1, fromPeg, usingPeg, toPeg );
System.out.printf( "Move disk %d
from %s to %s.%n", n, fromPeg, toPeg );
move( n - 1, usingPeg, toPeg, fromPeg );
}
else
System.out.printf( "Move disk %d
from %s to %s.%n", n, fromPeg, toPeg );
}
public static void main( String[] args )
{
move( 4, "copper peg", "gold peg",
"silver peg" );
}
}
Starten wir das Programm mit vier Scheiben, so bekommen wir folgende Ausgabe:
Move disk 1 from copper peg to silver peg.
Move disk 2 from copper peg to gold peg.
Move disk 1 from silver peg to gold peg.
Move disk 3 from copper peg to silver peg.
Move disk 1 from gold peg to copper peg.
Move disk 2 from gold peg to silver peg.
Move disk 1 from copper peg to silver peg.
Move disk 4 from copper peg to gold peg.
Move disk 1 from silver peg to gold peg.
Move disk 2 from silver peg to copper peg.
Move disk 1 from gold peg to copper peg.
Move disk 3 from silver peg to gold peg.
Move disk 1 from copper peg to silver peg.
Move disk 2 from copper peg to gold peg.
Move disk 1 from silver peg to gold peg.
Schon bei vier Scheiben haben wir 15 Bewegungen. Selbst wenn unser Prozessor mit vielen Millionen Operationen pro Sekunde arbeitet, benötigt ein Computer für die Abarbeitung von 100 Scheiben Tausende geologischer Erdzeitalter. An diesem Beispiel wird eines deutlich: Viele Dinge sind im Prinzip berechenbar, nur praktisch ist ein solcher Algorithmus nicht.
[1] Wir halten uns hier an eine Überlieferung von C. H. A. Koster aus dem Buch »Top-down Programming with Elan« von Ellis Horwood (Verlag Ellis Horwood Ltd, ISBN 0139249370, 1987).
[2] Gestein vulkanischen Ursprungs. Besondere Eigenschaften von Porphyr sind: hohe Bruchfestigkeit, hohe Beständigkeit gegen physikalisch-chemische Wirkstoffe und hohe Wälz- und Gleitreibung.