Türme von Hanoi

Bei den Türmen von Hanoi handelt es sich um ein berühmtes mathematisches Knobelspiel, das vor über 130 Jahren populär wurde. Gemeinhin wird angenommen, dass der französische Mathematiker Édouard Lucas das Spiel erdacht hat, zumindest schrieb er darüber in seinem vierbändigen Werk Récréations mathématiques (Unterhaltungsmathematik), erschienen um 1890. Auch hat er dieses Spielzeug wohl erstmals auf den Markt gebracht. Ziel des Spiels ist es, die acht Scheiben mit so wenigen Zügen wie möglich auf eines der anderen Stäbchen zu versetzen unter Beachtung der folgenden Regeln:

• Es darf jeweils nur ein Stein bewegt werden.
• Es darf kein größerer Stein auf einen kleineren Stein gelegt werden.
• Die Spielsteine dürfen nur von Stäbchen zu Stäbchen wandern.

Wer mag, fängt zuerst mit wenigen Steinen an. Man sieht dann auch besser, dass im Idealfall immer genau (2^n)-1 Spielzüge benötigt werden, um den Turm zu versetzen. Bei drei Steinen (n = 3) wäre die minimale Anzahl von Spielzügen also 2 ³- 1 = 8 - 1 = 7. 

Nicht nur für Mathematiker, sondern auch für Informatiker ist die Theorie hinter den Türmen von Hanoi von Interesse. In der Informatik können sie etwa als Beispiel für rekursive Algorithmen dienen - also auf sich selbst verweisende Handlungsvorschriften. Sehr schön ist das hier erklärt: http://www.kubitz-online.de/LK12_abi02/thema1/hanoi.html. Es findet sich auf dieser Seite auch die Lösung.