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 Werk Récréations mathématiques (Unterhaltungsmathematik), erschienen 1891. 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. Lucas hat die notwendige Anzahl an Zügen im Originaltext aufgeführt, s. hier.

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.

Quelle: „Édouard Lucas“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 11. Juli 2020, 12:29 UTC. URL: https://de.wikipedia.org/w/index.php?title=%C3%89douard_Lucas&oldid=201779295 (Zuletzt abgerufen: 13. Juli 2021, 06:43 UTC)