Türme von Hanoi
Die Türme von Hanoi sind ein mathematisches Knobel- und Geduldsspiel.
Aufbau
Das Spiel besteht aus drei Feldern, auf die Scheiben verschiedener Größe gelegt werden können. Zu Beginn sind alle Scheiben auf einem Feld, der Größe nach geordnet, mit der größten Scheibe unten und der kleinsten oben.
Bei jedem Zug darf die oberste Scheibe eines beliebigen Feldes auf eines der beiden anderen Felder gelegt werden, vorausgesetzt, dort liegt nicht schon eine kleinere Scheibe. Ziel des Spiel ist es, den kompletten Scheiben-Stapel auf ein anderes Feld zu versetzen.
| | |
= | |
=== | |
===== | |
======= | |
========= | |
=========== | |
--------------- --------------- ---------------
Startfeld Zielfeld
Geschichte
Vermutlich wurde das Spiel 1883 vom französischen Mathematiker Edouard Lucas erfunden. Er dachte sich dazu die Geschichte aus, dass indische Mönche im großen Tempel zu Benares, im Mittelpunkt der Welt, einen Turm aus 64 goldenen Scheiben versetzen müssten, und wenn ihnen das gelungen sei, wäre das Ende der Welt gekommen.
Lösungsalgorithmus
 |
| Lösung des Problems mit drei Scheiben. Von dieser Animation gibt es auch eine Version mit vier Scheiben. |
Man kann Türme von Hanoi mit verschiedenen Anzahlen von Scheiben spielen. Das Lösungsprinzip ändert sich dadurch nicht. Der einfachste, nicht völlig triviale Fall ist der mit 3 Scheiben. Wenn es gelingt 3 Scheiben von einem Stab (Turm) zum anderen bewegen, kann mit diesem Ansatz auch jeder Fall mit beliebiger Anzahl von Scheiben gelöst werden.
Lösung des 3-Scheiben-Falles: Die 3 Stäbe (Türme) werden von links nach rechts A,B,C und die Scheiben von klein nach groß 1,2,3 benannt, dann gibt ein Zahl-Buchstabenpaar an, welche Scheibe wohin bewegt werden soll (3B bedeutet z.B. die größte der 3 Scheiben soll auf den mittleren Turm gelegt werden).
Hier sind die Lösungsschritte: 1C, 2B, 1B, 3C, 1A, 2C, 1C (7 Schritte)
Es ist zu beachten, dass die erste Scheibe dorthin bewegt wird, wo sich letztendlich die drei Scheiben befinden sollen. Um jetzt mit diesem Lösungsalgorithmus das Problem mit 4 Scheiben zu lösen, bewegt man die drei Scheiben auf den Turm, der nicht das Ziel ist (hier also B), bewegt dann die Scheibe 4 auf den Zielstab, um danach die drei Scheiben von B nach C zu bewegen.
Hier sind die Lösungsschritte: 1B, 2C, 1C, 3B, 1A, 2B, 1B, 4C, 1C, 2A, 1A, 3C, 1B, 2C, 1C (15 Schritte)
Obwohl es auf den ersten Blick kompliziert klingt, gibt es für das Spiel einen ganz einfachen rekursiven Algorithmus. Da sich ein Computerprogramm zur Lösung des Spiels mit wenigen Zeilen schreiben lässt, ist Türme von Hanoi ein klassisches Beispiel für rekursive Programmierung.
Die minimale Anzahl von Zügen für einen Stapel aus n Scheiben beträgt 2n-1, bei einem Turm von 8 Scheiben (die gängigste Variante) also 255 Züge. Für den Stapel aus 64 Scheiben würden 18.446.744.073.709.551.615, also mehr als 18 Trillionen Züge benötigt. Würde man jede Sekunde eine Scheibe bewegen, bräuchte man dafür über 584 Milliarden Jahre.
Beispiel-Algorithmus (geschrieben in der Programmiersprache Scheme):
n = Anzahl der Scheiben
(define hanoi
(lambda (n aktuell ziel)
(begin (cond ((> n 1) (hanoi (- n 1) aktuell (- (- 6 aktuell) ziel))))
(display
(string-append "Setze Scheibe " (number->string n)
" von Platz " (number->string aktuell)
" nach Platz " (number->string ziel) ". "))
(cond ((> n 1) (hanoi (- n 1) (- (- 6 aktuell) ziel) ziel))))))
Aufruf: > (hanoi n 1 2)
"Beispiel-Algorithmus-Rekursiv" (geschrieben in c++)
#include <unistd.h>
#include <iostream.h>
#include <conio.h>
int rekhanoi (int anz, char a, char b, char c) // Definition Funktion rekhanoi
{
if (anz==1)
{
cout << "\n" << " obere Scheibe von " << a << " nach " << c;
return(anz);
}
rekhanoi (anz-1, a, c, b); // Aufruf der Funktion rekhanoi
rekhanoi (1, a, b, c);
rekhanoi (anz-1, b, a, c);
}
int main() // Hauptprogramm
{
int anz;
char a='a', b='b', c='c';
cout << "Anzahl: ";
cin >> anz;
rekhanoi (anz, a, b, c); // Aufruf der Funktion rekhanoi
getch();
return 0;
}
Lösungsalgorithmus von Buneman und Levy (1980)
Die Rekursive-Variante ist einfacher herzuleiten und es ist auch einzusehen, warum er funktioniert. Buneman und Levy haben 1980 einen Lösungsalgorithmus beschrieben, der ebenfalls funktioniert, für Menschen viel einfacher aussieht und ohne Rekursion auskommt:
Beispiel-Implementation (geschrieben in Pseudocode):
Ausführen bis der gesamte Turm verschoben wurde
1. Die kleinste verschiebbare Scheibe auf den Stapel rechts von ihr legen
(bzw. auf den ersten, wenn die Scheibe auf dem letzten Stapel liegt)
2. Die zweitkleinste verschiebbare Scheibe auf den einzig möglichen Stapel verschieben
Weblinks
- Hanoi Tutorial mit illustrierter Anwendung zur Erstellung von Lösungen und kommentiertem Algorithmus
- mister-mueller - Anschauliche Darstellung mit einer ausführlichen Erklärung.
- hanoimania - Implementation in 110 verschiedenen Programmiersprachen.
- Towers of Hanoi bei Wolfram Research - Zusammenhang zu verschiedenen mathematischen Fachgebieten
