Applicazioni di Intelligenza Artificiale - CLP

Prof. Marco Gavanelli

27 Luglio 2009

Esercizio (6 punti)

Dato un numero intero N, è possibile costruire N quadrati, di dimensione 1×1, 2×2, ... N ×N. Si costruisca un programma CLP che, dato un numero N e due dimensioni X e Y, dice se è possibile inserire i quadrati 1×1, 2×2, ... N ×N all'interno di un rettangolo X ×Y senza che i quadrati si sovrappongano vicendevolmente.

Facoltativo (2 punti)

Si trovi il rettangolo di area minima che contiene gli N quadrati senza che si sovrappongano.

Soluzione

Vedi anche la discussione su questo esercizio nelle FAQ.

:- lib(fd).

rett(X,Y,Lx,Ly,N):-
    length(Lx,N),
    length(Ly,N),
    numeri(Dim,1,N), % Costruisco la lista [1,2,3,...,N]
% Prendo una dimensione sufficientemente grande per il rettangolo contenitore
% Se metto in fila tutti i quadrati, ho una larghezza totale di 1+2+3+...+N=N*(N+1)/2
% 'fix' e` per portare tutto in virgola fissa
% Non e` indispensabile usare questo calcolo: andava bene qualunque dimensione
% abbastanza grande, anche un numero predefinito
    N2 is fix(N*(N+1)/2),
    [X|Lx]::0..N2,
    [Y|Ly]::0..N2,
    no_overlap(Lx,Ly,Dim,Dim),
    max_dim(Lx,Dim,X), % Tutti i quadrati stanno entro la X
    max_dim(Ly,Dim,Y), % Tutti i quadrati stanno entro la Y
    Area #= X*Y, % Area del rettangolo contenitore
    flatten([X,Y,Lx,Ly],All),
    min_max(labeling(All),Area).

max_dim([],[],_).
max_dim([X1|Lx],[D|Ld],Max):-
    X1+D #=< Max,
    max_dim(Lx,Ld,Max).

numeri([N],N,N):-!.
numeri([N|T],N,M):-
    N1 is N+1,
    numeri(T,N1,M).

% Impone che i quadrati non si sovrappongano a due a due
no_overlap([],[],[],[]).
no_overlap([X|Lx],[Y|Ly],[W|Lw],[H|Lh]):-
    no_overlap_loop(X,Y,W,H,Lx,Ly,Lw,Lh),
    no_overlap(Lx,Ly,Lw,Lh).

no_overlap_loop(_,_,_,_,[],[],[],[]).
no_overlap_loop(X1,Y1,W1,H1,[X2|Lx],[Y2|Ly],[W2|Lw],[H2|Lh]):-
    X1+W1 #=< X2 #\/ % il primo quadrato e` a sinistra del secondo
    X2+W2 #=< X1 #\/ % il primo quadrato e` a destra del secondo
    Y1+H1 #=< Y2 #\/ % il primo quadrato e` sopra il secondo
    Y2+H2 #=< Y1,    % il primo quadrato e` sotto il secondo
    no_overlap_loop(X1,Y1,W1,H1,Lx,Ly,Lw,Lh).