Applicazioni di Intelligenza Artificiale - CLP

Prof. Marco Gavanelli

13 Aprile 2010

Esercizio (8 punti)

Il file tessere.pl contiene dei fatti

che rappresentano le tessere di un domino.

Si desidera creare una sequenza di tessere, tali che due tessere contigue hanno lo stesso numero nel lato comune.

Le tessere sono tutte diverse, tutte le tessere devono essere usate e ogni tessera può essere usata una sola volta. Le tessere possono essere ribaltate. Ad esempio, date le tessere

si può costruire la sequenza [[4,1],[1,3],[3,2]].

Si scriva un programma CLP(FD) che risolve questo problema.

Soluzione

:- lib(fd).
:- lib(propia).
:- [tessere].

domino(L):-
    findall((A,B),tessera(A,B),Tessere),
    crea_var(Tessere,L),
    esistono(L),
    diverse(L),
    contigue(L),
    flatten(L,Flat),
    labeling(Flat).

crea_var([],[]).
crea_var([_|LT],[[_,_]|Lvar]):-
    crea_var(LT,Lvar).

diverse([_]).
diverse([[A,B],[C,D]|T]):-
    diverse_loop([A,B],[[C,D]|T]),
    diverse([[C,D]|T]).

diverse_loop([_,_],[]).
diverse_loop([A,B],[[C,D]|T]):-
    #\+( (A#=C #/\ B#=D) #\/ (A#=D #/\ B#=C) ),
    diverse_loop([A,B],T).

% Impongo che le tessere che inserisco siano prese da quelle disponibili
esistono([]).
esistono([H|T]):-
    tessera_orientata(H) infers fd,
    esistono(T).

tessera_orientata([A,B]):- tessera(A,B).
tessera_orientata([A,B]):- tessera(B,A).

contigue([_]).
contigue([[_A,B],[C,D]|T]):-
    B #= C,
    contigue([[C,D]|T]).