In dieser und den nächsten Praktikumsaufgaben wollen wir mit Hilfe der Programmiersprache Prolog ein Labyrinth implementieren, in dem eine Maus nach verschiedenen Strategien einen Weg vom Eingang des Labyrinths zu einem Ausgang sucht. In dieser Praktikumsaufgabe beginnen wir mit der Implementation des Labyrinths und einiger Prädikate, mit denen wir Aussagen über die Felder des Labyrinths erhalten können.

Das gegebene Labyrinth hat folgende Form:

%Labyrinth
% Ein Labyrinth besteht aus Zeilen von Feldern.
% Nachbarfelder sind durch eine Wand getrennt oder 
% der Durchgang zum Nachbarfeld ist offen.
% Das Labyrinth besitzt einen Eingang und einen Ausgang.

%Bezeichnungen der Felder:
% -----------------      
%|           |           |
%| a1    a2  | a3    a4  |
%|           |           |
%|                  -----|
%      |     |           |
%  b1  | b2  | b3    b4  |
%      |     |           |
%|                       |
%|                 |     |
%| c1    c2    c3  | c4  |
%|                 |     |
% -----------------------

Einen vollständig anderen Ansatz zur Codierung des Labyrinths legt Prolog nahe. Zu den Nachbarfeldern eines Feldes besteht die Relation "wand" oder "offen". Die verschiedenen Nachbarfelder lassen sich durch die Richtung unterscheiden, in der sie liegen. An den Rändern gibt es keine Nachbarfelder.

%Bezeichnung der Richtungen: osten, sueden, westen, norden

% Implementation des Labyrinths durch Relationen offen/3 und wand/3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Das Praedikat offen(Von, Nach, Richtung) beschreibt,
% in welcher Richtung die Maus vom Feld Von zum Feld Nach gelangen kann.
% Es ist nur notwendig, die Fakten fuer dieses Praedikat 
% fuer osten und sueden anzugeben,
% da offen(Von, Nach, westen) durch offen(Nach, Von, osten) gegeben ist
% und offen(Von, Nach, norden) durch offen(Nach, Von, sueden).
%
% Hinweis: Achten Sie darauf, dass nur die Variablen gross geschrieben werden!
offen(a1, a2, osten).
offen(a3, a4, osten).
offen(b3, b4, osten).
offen(c1, c2, osten).
offen(c2, c3, osten).

offen(a1, b1, sueden).
offen(b1, c1, sueden).
offen(a2, b2, sueden).
offen(b2, c2, sueden).
offen(a3, b3, sueden).
offen(b3, c3, sueden).
offen(b4, c4, sueden).

offen(F1, F2, westen):- offen(F2, F1, osten).
offen(F1, F2, norden):- offen(F2, F1, sueden).

% Mit Hilfe des Praedikats offen(Feld1, Feld2, Richtung) kann man einen Weg 
% vom Start zum Ziel finden, falls ueberhaupt ein Weg existiert.
% Will man aber alle Nachbarn eines Feldes oder das ganze Labyrinth
% ausgeben, so benoetigt man auch ein Praedikat, das die Waende beschreibt,
% z.B. wand(b1, b2, osten).
% Felder, die nur von Waenden umgeben sind, wuerden sonst unbekannt bleiben!

% *** Implementation des Praedikats wand(Feld1, Feld2, Richtung) 
%     fuer alle Richtungen einfuegen! ***
% Im Labyrinth gibt es vier Waende nach Osten und eine Wand nach Sueden.
% Die Waende fuer westen und norden lassen sich wie bei offen/3
% definieren.

Jedes Labyrinth-Feld ist hier durch eine Bezeichnung beschrieben. Die Bezeichnungen sind aber so gewählt, dass man aus der Bezeichnung leicht die Position des Feldes im Labyrinth ablesen kann. "b3" bezeichnet das 3.Feld in der zweiten Zeile (Zeile b). In einem Java-Feld wird die Nachbarschaftsrelation durch die Indizes des Feldes bestimmt (Zeilenindex bzw. Spaltenindex um 1 erhöhen bzw. verringern). Hier ist ein Feld des Labyrinths zu seinem Nachbarfeld offen oder durch eine Wand getrennt. Damit Sie sich an diese Denkweise gewöhnen, implementieren Sie als nächstes das Prädikat nachbar/3:

% *** Implementation des Praedikats nachbar/3 einfuegen! ***
% Es gilt nachbar(Feld1, Feld2, Richtung), wenn fuer Richtung, Feld1 und
% Feld2 die Relation offen/3 oder  wand/3 gilt.
% (Im Labyrinth gibt es in eine Richtung hoechstens einen Nachbarn.)

In Prolog ist es oft notwendig, Prädikate rekursiv zu definieren. Dabei muss man normalerweise zuerst prüfen, ob die Abbruchbedingung erfüllt ist. Ist das nicht der Fall, dann sind die Parameter für den rekursiven Aufruf festzulegen und mit diesen Parametern der rekursive Aufruf zu starten.

% Ende, wenn endeBedingung(X) erfolgreich
rekursiveProzedur(X):- 
	endeBedingung(X), endeBehandlung(X).       
% sonst rek. Aufruf, wenn neuerParameter(X,Y) erfolgreich
rekursiveProzedur(X):- 
	neuerParameter(X,Y), rekursiveProzedur(Y); 
% sonst nicht erfolgreich!

Nach diesem Schema läßt sich das Prädikat istFeldInRichtung/3 implementieren, das durch folgenden Kommentar beschrieben ist:

% *** Implementation des Praedikats istFeldInRichtung(X, Y, Ri) einfuegen! ***
% Bestimmt, ob Feld Y vom Feld X aus in Richtung Ri liegt.
% Beispiel:
% ?- istFeldInRichtung(a1,a3,osten).
% Yes 
% ?- istFeldInRichtung(a1,b3,osten).
% No 

Nicht selten bricht die Rekursion dadurch ab, dass die Berechnung der Parameter für den rekursiven Aufruf fehl schlägt. Dann vereinfacht sich die Implementation der rekursiven Prozedur:

  
rekursiveProzedur(X):- 
	neuerParameter(X,Y), rekursiveProzedur(Y); % rek. Aufruf 
% Sonst nicht erfolgreich!	

% *** Implementation des Praedikats felderInRichtung(X,Ri) einfuegen! *** 
% Gibt in einer Zeile alle Felder aus, die sich vom Feld X in Richtung Ri befinden.
% (Endet immer nicht erfolgreich, wenn kein weiterer Nachbar in Richtung R1 existiert)
% Beispiel:
% ?- felderInRichtung(c1, osten).
% No
% c2  c3  c4   ?-

Ähnlich einfach ist das letzte Prädikat alleFelder/1 zu implementieren, wobei Sie das Rekursionsschema wieder leicht modifizieren müssen.

% *** Implementation des Praedikats alleFelder(Feld)  einfuegen! ***
% Gibt zeilenweise alle Felder aus,
% die oestlich und suedlich von Feld liegen und Feld.
% Beispiel:
% ?- alleFelder(a1).
% a1  a2  a3  a4
% b1  b2  b3  b4
% c1  c2  c3  c4
% No

Für die Implementation der Ausgabe gibt es Standardprädikate: