Türme von Hanoi

Wenn du die Lektion zum Thema Rekursion verstanden hast, dann ist es an der Zeit sich eines weiteren Problems zu widmen bei dem Mehrfachrekursion unabdingbar ist. Es handelt sich dabei um die Türme von Hanoi, bestehend aus drei gleich großen Stiften und $n$‍ gelochten Scheiben unterschiedlicher Größe. Wir benennen die Stifte von links nach rechts A, B, and C, und nummerieren die Scheiben aufsteigend nach Größe, beginnend mit der kleinsten, von 1 bis $n$‍. In der Ausgangsstellung befinden sich alle $n$‍ Scheiben auf dem linken Stift A, der Größe nach geordnet, mit der größten Scheibe $n$‍ unten und der kleinsten Scheibe 1 oben. Der Turm von Hanoi sieht mit $n=5$‍ Scheiben folgendermaßen aus:

Ziel des Spiels ist es, alle $n$‍ Scheiben von Stift A nach Stift B zu versetzen.

Klingt einfach, nicht wahr? Es ist allerdings nicht ganz so einfach, weil zwei Regeln gelten:

Man könnte denken, dass dieses Problem nicht furchtbar wichtig ist. Au contraire! Der Überlieferung nach lösen Mönche in Asien (also z.B. Tibet, Vietnam, Indien, ...) dieses Rätsel mit bis zu 64 Scheiben. Nach der Überlieferung glauben die Mönche, dass wenn sie fertig damit sind alle 64 Scheiben von Stift A nach Stift B gemäß den beiden Regeln bewegt zu haben, dass die Welt enden wird.

Zuerst untersuchen wir, wie dieses Problem rekursiv zu lösen ist. Wir beginnen mit einem ganz einfachen Fall mit nur einer Scheibe, d. h. $n=1$‍. Dieser Fall von $n=1$‍ wird zu unserem Basisszenario. Wir können die Scheibe 1 jederzeit und ohne Einschränkungen von Stift A nach B verschieben, weil wir wissen, dass es keine drunterliegenden Scheiben gibt. Stifte A und B sind auch beliebig. Man könnte genauso gut die Scheibe 1 von Stift B nach C bewegen, oder von C nach A, oder von einem beliebigen Stift auf einen anderen beliebigen Stift. Das Türme von Hanoi-Problem mit einer Scheibe zu lösen ist trivial und es ist bedarf lediglich diese eine Scheibe genau einmal zu bewegen.

Wie verhält es sich mit zwei Scheiben? Wie löst man das Problem wenn $n=2$‍ ist? Wir brauchen dazu drei Schritten. Hier ist die Ausgangsposition:

Verschiebe zuerst Scheibe 1 von Stift A nach C.

beachte, dass wir Stift C als Zwischenablage verwenden um Scheibe 1 abzulegen, damit wir zur Scheibe 2 gelangen können. \ Nun, dass Scheibe 2 — die unterste Scheibe — freiliegt, verschieben wir sie auf Stift B.

Schließlich bewegen wir Scheibe 1 von Stift C nach B.

Diese Lösung erfordert drei Schritte, und wieder ist der Umzug zweier Scheiben von Stift A nach Stift B eigentlich ganz beliebig. Man können sie ebensogut vom Stift B zu C bewegen und dabei Stift A als Zwischenablage verwenden: Verschiebe dazu Scheibe 1 vom Stift B nach A, dann Scheibe 2 von B, nach C und schlussendlich Scheibe 1 von A nach C. Denkst du auch, dass du die Scheiben 1 und 2 von jedem beliebigen Stift auf jeden anderen Stift bewegen kannst?

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.