Turm von Hanoi

Der Rechner soll folgendes Problem lösen: Vorgegeben sind drei Stapel a,b,c. Auf dem Stapel a liegen n Scheiben, die von oben nach unten durchnumeriert sind. Die anderen Stapel sind leer. Ziel ist es, Scheiben so umzustapeln, dass zum Schluss alle Scheiben in der alten Reihenfolge auf dem Stapel c liegen. Zu beachten ist, dass beim Umstapeln keine Scheibe mit einer größeren Nummer auf einer mit einer kleineren zu liegen kommen.

Nach einer alten Sage soll die Welt untergehen, wenn jemand das Problem mit 100 Scheiben löst.

Die Idee

Wie geht man nun programmtechnisch vor?
Wir vermuten, dass ein KI-Programm in der Lage ist, die oberen n-1 Scheiben von Stapel a auf Stapel b umzuschichten. Die schwierige Aufgabe, die größte Scheibe mit der Nummer n von a auf den leeren Stapel c umzulegen, lösen wir selbst und geben dies auf dem Bildschirm aus. Nun muss der Rechner nur noch dank KI die restlichen Scheiben von Stapel b auf den Stapel c transportieren. Wie der Rechner das schafft, soll es auf dem Bildschirm ausgeben.

Die Werkzeuge

Das Programm ist ein einfaches Beispiel dafür, wie man in Prolog Schleifen (Rekursionen) programmieren kann.Damit der Nutzer mit dem Programm kommunizieren kann, sind Ein- und Ausgabebefehle sinnvoll.

Die Ein- und Ausgabe soll zunächst im Hauptfenster von SWI-Prolog erfolgen, ohne die vielfältigen Möglichkeiten von Windows zu nutzen (wird später behandelt).

Für die Eingabe gibt es zwei Möglichkeiten:<

Die Eingabe wird als Parameter in das Startprädikat geschrieben.
Beispiel: ?-start('Das ist eine Eingabe').
Die Eingabe kann mit den Prädikaten read(A) bzw. readln(A) erfolgen, die eine Eingabezeile öffnen, in der ein Text geschrieben werden kann. Die Eingabe wird mit ENTER in A übertragen. A kann dann in anderen Prädikaten ausgewertet werden. read und readln zeigen keine Fragen an!
Die Eingabe muss bei read mit einem Punkt enden. Werden Großschrift oder Leerzeichen verwendet, ist der Text in Hochkomma oder " einzuschließen.
Bei readln sind diese Maßnahmen nicht nötig, dafür wird der Text aufgegliedert als Liste von Wörtern übergeben.

Es gibt weitere Varianten von read, die uns an dieser Stelle aber nichts nützen.

Die Ausgabe geschieht mit dem Prädikat write(A), wobei der Textinhalt des Parameters A im Hauptfenster ausgegeben wird. A kann auch direkt durch einen Text ersetzt werden, der in ' eingeschlossen ist. write löst keinen Zeilenvorschub aus.
Soll der Rechner eine neue Zeile beginnen, so geschieht das mit dem Prädikat nl.

Hinweis: In SWI-Prolog gibt es weitere Varianten der Prädikate write und read, die u.a. die Bearbeitung von Dateien ermöglichen.

Um u.a. das Programm flexibler zu gestalten, werden wir Variablen verwenden, und zwar N für die Scheibenzahl, Q für die Bezeichnung des Quellstapels, von dem Scheiben genommen werden, Z für den Zielstapel, auf den die Scheiben gelegt werden, und U für den dritten Stapel.
Es ist zudem N-1 zu berechnen. Berechnungen in Prolog geschehen in der Form
E is Term ,
wobei in der Variablen E das Ergebnis gespeichert wird.

Das Programm

ausg(N,Q,Z):-write('Scheibe '),write(N),write(' von '),
write(Q),write(' nach '),write(Z),nl.

bewege(0,_,_,_).
bewege(N,Q,Z,U) :- M is N-1,bewege(M,A,C,B),
ausg(N,A,B),bewege(M,C,B,A).

hanoi(N) :- bewege(N,a,b,c).

Ausgabe: Scheibe N von Stapel Q nach Stapel Z
danach: neue Zeile
Prädikat bewege: Wenn 0 Scheiben, dann keine Aktion
Sonst: Berechne N-1 und speichere das Ergebnis in M, verschiebe
M Scheiben von Q nach U, Augabe "Schiebe Scheibe N von Q nach Z",
verschiebe die M Scheiben von U nach Z

Prädikat hanoi: Dient dem vereinfachten Progammstart,
dabei Scheibenzahl statt N eingegeben.

In der zweiten Klausel von bewege() wird der Wahrheitswert überprüft, indem bewege() mit anderen Parametern aufgerufen wird. Insgesamt hat man eine rekursive Definition. Dadurch entsteht eine Art Schleife, die erst dann endet, wenn M beim Aufruf den Wert 0 hat, also die Klausel bewege(0,_,_,_) überprüft wird. Diese ist aber immer richtig, so dass dann auch für andere N bewege() richtig wird. Da bei dem wiederholten Aufruf die Werte von Q,Z,U vertauscht werden, entsteht über die Ausgabe eine Art Protokoll, wie der Rechner die Scheibenbewegungen durchgeführt hat, was wir ja wissen wollten.

Hinweis: Rekursionen können in Prolog tückisch sein, da man vielfach nicht nachvollziehen kann, welche Klauseln wann benutzt werden.

Aufgabe: Man teste das Programm für verschiedene N und versuche, den Ablauf vorherzusagen.