CLP lernen

... [ Seminarthemen SS01 ] ... [ Inhaltsverzeichnis ] ... [ Lösen eines logischen Puzzles ] ... 

Übersicht: CLP lernen

Einleitung

Das letzte Kapitel hat uns die Grenzen der Lösungsfindung mit Hilfe einer Tabelle gezeigt. Um aber auch Rätzel mit Ordnungsrelationen und logischen Verknüpfungen zu lösen, muß man einen Computer, eine logischen Programmiersprache (Prolog) und eine geeignete Entwicklungsumgebung (ECLiPSe) benutzen. Aus dieser Kombination läßt sich auch das Kürzel CLP (Constraint Logic Programming), also logisches Programmieren mit Einschränkungen, leicht ableiten. In den folgenden zwei Abschnitten wird kurz auf die Prolog-Syntax und die Bibliothek FD (Finite Domain) von ECLiPSe eingegangen. Falls eine ausführliche Beschreibung der beiden Themen erforderlich ist, verweise ich auf das in der Einleitung bereits erwähnte Seminar.

Prolog


FD-Library von ECLiPSe

Die ECLiPSe-Bibliothek FD (Finite Domain - endliche Wertebereiche) stellt dem Benutzer schon viele vordefinierte Regeln zur Verfügung, von denen die vorgestellt werden, die für das Lösen von logischen Puzzlen von Bedeutung sind. Um die Bibliothek einzubinden hat man zwei Möglichkeiten:
        :- use_modul(library(fd)).
        :- lib(fd).
Da diese Regeln keinen Kopf enthalten, sondern nur aus einen Rumpf bestehen, werden die Regel während der Compilation ausgeführt und somit wird die Library FD eingebunden.

Bei der Codierung des Quelltextes sollte man auf Kommentare nicht verzichten. Um so größer die Programme werden, desto sinnvoller ist es seine Überlegungen zu dokumentieren. Für Kommentare, die nur bis zum Zeilenende gelten, benutzt man das Prozentzeichen, für einen mehrzeiligen Kommentar kann man die aus der Programmiersprache C bekannte Notation verwenden.
               % Kommentar bis zum Zeilenende

        /* Kommentar
           über
           mehrere
           Zeilen */

Einige Beispiele für die Festlegung des Wertebereichs von Variablen
        die Variable A erhält den Wertebereich von 1..12:
        A :: 1..12,
        die Listenelemente A, B und C erhalten den Wertebereich 1..4:
        [A, B, C] :: 1..4,
        Zuweisung des Wertebereichs, der Lücken enthält:
        [A, B, C] :: [10,12,14..16,18],
        eine Liste mit drei Elementen definieren und anschließend den Elementen der Liste einen Wertebereich zuordnen:
        Liste = [A, B, C], Liste :: 1..4,

Die definierten Variablen mit zugehörigen Wertebereich können nun miteinander verglichen werden.Mit dieser Syntax werden auch überwiegend die Aussagen der logischen Puzzles dargestellt.
        die Variable A hat den gleichen Wert wie die Variable B:
             A#=B,
        die Variable A hat einen anderen Wert wie die Variable C:
             A##C,
        die Variable B ist echt kleiner als die Variable C
             B#<C,
        die Variable B ist um den Wert 1 kleiner als die Variable C
             B + 1 #= C,
 

Die nächsten fünf Regeln werden von der FD-Library bereitgestellt.
 
labeling(Liste) alle Variablen in der Liste werden komplett ausgewertet
member(Element,Liste)  prüft, ob das Element Bestandteil der Liste ist
alldistinct(Liste)  alle Variablen in der Liste sind verschieden
write(X)
write("Text")		 für die Ausgabe von Variablen und Text
make_display_matrix(Term,Name) erzeugt eine Tabelle, mit der man den Wertebereich der Variablen zur Laufzeit überprüfen kann

 

Send-More-Money - Beispiel

     S E N D 
   + M O R E
   M O N E Y		 -Buchstaben durch die Ziffern 0..9 ersetzen
-gleiche Buchstaben haben die gleiche Ziffer
-unterschiedliche Buchstaben haben verschiedene Ziffern 
-keine führenden Nullen

Der Quelltext für das Problem könnte folgendes Aussehen haben:
 
:- use_module(library(fd)). Die Bibliothek FD wird eingebunden.
send(List) :-
  List = [S, E, N, D, M, O, R, Y],
  List :: 0..9,		 Es wird eine Regel send definiert, die einen Parameter List hat. Die Variablen werden in einer Liste List zusammengefaßt und der Wertebereich der Listenelemente wird festgelegt.
  make_display_matrix(List/1, send), Erzeugt eine Tabelle, mit der die Wertebereiche der Variablen zur Laufzeit überprüft werden können.
    alldistinct(List), Die Elemente in der Liste List müssen verschieden sein.
                  1000*S+100*E+10*N+D
               + 1000*M+100*O+10*R+E #=
  10000*M+1000*O+100*N+10*E+Y,
  M ## 0,		 Die Einschränkungen für die Variablen werden definiert.
  labeling(List). Die Elemente der Liste List werden komplett ausgewertet.

Die Anfrage send(X) wird wie folgt beantwortet:

X = [9, 5, 6, 7, 1, 0, 8, 2]
 

Nach oben
... [ Seminarthemen SS01 ] ... [ Inhaltsverzeichnis ] ... [ Lösen eines logischen Puzzles ] ...