Εργαστήριο 2 στην Prolog

Θέματα που εξετάζονται στο εργαστήριο: Λίστες¹ ², αποκοπή και άρνηση (cut and negation)³, Λογικός Προγραμματισμός με Περιορισμούς (CLP=Constraint Logic Programming)⁴.

Εξάσκηση (εκφωνήσεις και λύσεις ασκήσεων)

Άσκηση PRO2E1 Έστω ένας χάρτης με αριθμημένες περιοχές. Η πληροφορία για τις περιοχές του χάρτη που συνορεύουν δίνεται με μια λίστα της μορφής [[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[3,4],[4,5]] που σημαίνει ότι η περιοχή 1 συνορεύει με τις περιοχές 2, 3, 4, 5, κ.ο.κ. Κατασκευάστε το κατηγόρημα adjacent(X,Y,Map) με ορίσματα X και Y, 2 αριθμούς περιοχών και Map τη λίστα με τις περιοχές που συνορεύουν. Το κατηγόρημα adjacent/3 να επαληθεύεται όταν οι 2 περιοχές είναι γειτονικές.

Ο χάρτης [[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[3,4],[4,5]] αντιστοιχεί στο ακόλουθο σχήμα:

,

Θέστε τα ακόλουθα ερωτήματα:

Είναι οι περιοχές 4 και 2 γειτονικές στον παραπάνω χάρτη;
Είναι οι περιοχές 5 και 2 γειτονικές στον παραπάνω χάρτη;

Έστω ότι επιθυμούμε να ελέγξουμε αν ένας χρωματισμός περιοχών είναι έγκυρος, δηλαδή αν δεν υπάρχουν γειτονικές περιοχές που να έχουν χρωματιστεί με το ίδιο χρώμα. Κατασκευάστε το κατηγόρημα conflict(Map, Coloring) που δέχεται μια λίστα Map όπως στο προηγούμενο κατηγόρημα και μια λίστα Coloring της μορφής [[5,red],[4,red],[3,blue],[1,blue],[2,yellow]] που σημαίνει ότι η περιοχή 5 χρωματίζεται κόκκινη κ.ο.κ. Το κατηγόρημα conflict/2 να επαληθεύεται αν υπάρχει σύγκρουση χρωμάτων.

Θέστε τα ακόλουθα ερωτήματα:

Έχει ο χρωματισμός [[5,red],[4,red],[3,blue],[1,blue],[2,yellow]] για τον παραπάνω χάρτη σύγκρουση;
Έχει ο χρωματισμός [[5,blue],[4,red],[3,yellow],[1,green],[2,blue]] για τον παραπάνω χάρτη σύγκρουση;

Λύση άσκησης PRO2E1

pro2e1.pl
% https://www.cpp.edu/~jrfisher/www/prolog_tutorial/pt_framer.html

% η περιοχή Χ είναι γειτονική με τη περιοχή Υ για τον χάρτη Map 
adjacent(X,Y,Map) :- member([X,Y],Map) ; member([Y,X],Map). 

conflict(Map,Coloring) :- 
    member([R1,C],Coloring), 
    member([R2,C],Coloring), 
    adjacent(R1,R2,Map). 

Φόρτωση του αρχείου pro2e2.pl στην Prolog:

$ swipl -l pro1e3.pl

Για να μην εμφανίζονται οι μεταβλητές που ξεκινούν με _ δίνεται η ακόλουθη εντολή:

?- set_prolog_flag(toplevel_print_anon, false).

Είναι οι περιοχές 4 και 2 γειτονικές στον χάρτη [[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[3,4],[4,5]];

?- _Map = [[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[3,4],[4,5]], adjacent(4, 2, _Map).
true .

Είναι οι περιοχές 5 και 2 γειτονικές στον χάρτη [[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[3,4],[4,5]];

?- _Map = [[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[3,4],[4,5]], adjacent(5, 2, _Map). 
false.

Έχει ο χρωματισμός [[5,red],[4,red],[3,blue],[1,blue],[2,yellow]] για τον χάρτη [[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[3,4],[4,5]] σύγκρουση;

?- _Map = [[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[3,4],[4,5]], _Coloring = [[5,red],[4,red],[3,blue],[1,blue],[2,yellow]], conflict(_Map,_Coloring).
true .

Έχει ο χρωματισμός [[5,blue],[4,red],[3,yellow],[1,green],[2,blue]] για τον χάρτη [[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[3,4],[4,5]] σύγκρουση;

?- _Map = [[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[3,4],[4,5]], _Coloring = [[5,blue],[4,red],[3,yellow],[1,green],[2,blue]], conflict(_Map,_Coloring).
false.

Άσκηση PRO2E2 Το κατηγόρημα max\3 πρέπει να επαληθεύεται όταν το τρίτο όρισμα είναι η μεγαλύτερη τιμή των 2 πρώτων ορισμάτων. Δίνεται η ακόλουθη υλοποίηση με χρήση cut. Μπορείτε να εντοπίσετε κάποιο παράδειγμα για το οποίο δεν λειτουργεί σωστά; Γιατί; Διορθώστε το.

max(X,Y,Y) :- Y>X, !.
max(X,_,X).

Λύση άσκησης PRO2E2

pro2e2.pl
% http://www.let.rug.nl/bos/lpn//lpnpage.php?pagetype=html&pageid=lpn-htmlse44

max(X,Y,Y) :- Y>X, !.
max(X,_,X).

Ορθή συμπεριφορά:

?- max(1,2,X).
X = 2.

Ορθή συμπεριφορά:

?- max(2,1,X).
X = 2.

Ορθή συμπεριφορά:

?- max(1,2,2).
true.

Ορθή συμπεριφορά:

?- max(1,2,99). 
false.

Λάθος συμπεριφορά:

?- max(1,2,1).
true.

Στη συνέχεια παρουσιάζονται 3 διαφορετικές διαμορφώσεις του κατηγορήματος max/3 που λειτουργούν σωστά.

Α' διαμόρφωση

max(X,Y,Y) :- Y > X.
max(X,Y,X) :- X >= Y.

Β' διαμόρφωση

max(X,Y,Y) :- Y > X, !.
max(X,Y,X) :- X >= Y.

Γ' διαμόρφωση

max(X,Y,Z) :- Y > X, !, Z=Y.
max(X,_,X).

Άσκηση PRO2E3 Με τη χρήση της βιβλιοθήκης CLPFD, εντοπίστε όλες τις τιμές των X, Y και Z με πεδία τιμών ακέραιους από το 1 μέχρι και το 20 για τις οποίες το άθροισμά τους είναι 15, η X είναι μεγαλύτερη από την Y και η Ζ είναι διπλάσια ή μεγαλύτερη της Y.

Λύση άσκησης PRO2E3

pro2e3.pl
:- use_module(library(clpfd)).

solve(X,Y,Z) :- 
    X in 1..20,
    Y in 1..20,
    Z in 1..20,
    X + Y + Z #= 15,
    X #> Y,
    Z #>= 2 * Y,
    label([X,Y,Z]).

% εναλλακτική λύση
solve2(X,Y,Z) :- 
    Vs = [X,Y,Z], 
    Vs ins 1..20,
    X + Y + Z #= 15,
    X #> Y,
    Z #>= 2 * Y,
    label(Vs), 
    write(Vs),
    nl,
    fail.

?- solve(X,Y,Z).
X = 2,
Y = 1,
Z = 12 ;
X = 3,
Y = 1,
Z = 11 ;
X = 3,
Y = 2,
Z = 10 ;
X = 4,
Y = 1,
Z = 10 ;
X = 4,
Y = 2,
Z = 9 ;
X = 4,
Y = 3,
Z = 8 ;
X = 5,
Y = 1,
Z = 9 ;
X = 5,
Y = 2,
Z = 8 ;
X = 5,
Y = 3,
Z = 7 ;
X = 6,
Y = 1,
Z = 8 ;
X = 6,
Y = 2,
Z = 7 ;
X = Z, Z = 6,
Y = 3 ;
X = Z, Z = 7,
Y = 1 ;
X = 7,
Y = 2,
Z = 6 ;
X = 8,
Y = 1,
Z = 6 ;
X = 8,
Y = 2,
Z = 5 ;
X = 9,
Y = 1,
Z = 5 ;
X = 9,
Y = 2,
Z = 4 ;
X = 10,
Y = 1,
Z = 4 ;
X = 11,
Y = 1,
Z = 3 ;
X = 12,
Y = 1,
Z = 2.

?- solve2(X,Y,Z). 
[2,1,12]
[3,1,11]
[3,2,10]
[4,1,10]
[4,2,9]
[4,3,8]
[5,1,9]
[5,2,8]
[5,3,7]
[6,1,8]
[6,2,7]
[6,3,6]
[7,1,7]
[7,2,6]
[8,1,6]
[8,2,5]
[9,1,5]
[9,2,4]
[10,1,4]
[11,1,3]
[12,1,2]
false.

Άσκηση PRO2E4 Με τη χρήση της βιβλιοθήκης CLPFD, λύστε το κρυπταριθμητικό παζλ SEND + MORE = MONEY στο οποίο κάθε χαρακτήρας πρέπει να αντικατασταθεί με ένα ψηφίο έτσι ώστε η παραπάνω πράξη να είναι ορθή.

Λύση άσκησης PRO2E4

pro2e4.pl
% https://github.com/Anniepoo/swiplclpfd/blob/master/clpfd.adoc#an-example

:- use_module(library(clpfd)).

puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]) :-
        Vars = [S,E,N,D,M,O,R,Y],
        Vars ins 0..9,  
        all_different(Vars),       
                  S*1000 + E*100 + N*10 + D +  
                  M*1000 + O*100 + R*10 + E #=
        M*10000 + O*1000 + N*100 + E*10 + Y,
        M #\= 0, S #\= 0,   
        label(Vars).

?- puzzle(X).
X = ([9, 5, 6, 7]+[1, 0, 8, 5]=[1, 0, 6, 5, 2]) ;
false.