
/* disjoint teste si deux rectangles sont disjoints 
   Un rectangle est donné par les coordonnées du points d'origine du
   rectangle et sa largeur et sa hauteur */

disjoint(X1,_,R1,_,X2,_,_,_) :-
   X1 + R1 #=< X2.   
disjoint(X1,Y1,R1,L1,X2,Y2,R2,L2) :-
   Y1 + L1 #=< Y2.
disjoint(X1,Y1,R1,L1,X2,Y2,R2,L2) :-
   X2 + R2 #=< X1.
disjoint(X1,Y1,R1,L1,X2,Y2,R2,L2) :-
   Y2 + L2 #=< Y1.

/* covered teste si un rectangle couvre le point donné par le schéma du 
sikaku */

covered(X,Y,R,L,P1,P2) :- 
   X #=< P1, P1 #< X+R,
   Y #=< P2, P2 #< Y+L.

/* resoud le sikaku de l'exemple */

sikaku1(L) :-
   L = [X1,Y1,R1,L1,X2,Y2,R2,L2,X3,Y3,R3,L3,X4,Y4,R4,L4],
   /* contraintes sur la taille des rectangles */
   R1*L1 #= 5, R2*L2 #= 8, R3*L3 #= 6, R4*L4 #=6,
   X1 #> 0,  X2 #> 0, X3 #> 0, X4 #> 0,
   Y1 #> 0,  Y2 #> 0, Y3 #> 0, Y4 #> 0,
   X1+R1 #=< 6,X2+R2 #=< 6, X3+R3 #=< 6, X4 + R4 #=< 6,
   Y1+L1 #=< 6,Y2+L2 #=< 6, Y3+L3 #=< 6, Y4 + L4 #=< 6,
   covered(X1,Y1,R1,L1,1,1),
   covered(X2,Y2,R2,L2,2,2),
   covered(X3,Y3,R3,L3,3,5),
   covered(X4,Y4,R4,L4,4,2),
   disjoint(X1,Y1,R1,L1,X2,Y2,R2,L2),
   disjoint(X1,Y1,R1,L1,X3,Y3,R3,L3),
   disjoint(X1,Y1,R1,L1,X4,Y4,R4,L4),
   disjoint(X2,Y2,R2,L2,X3,Y3,R3,L3),
   disjoint(X2,Y2,R2,L2,X4,Y4,R4,L4),
   disjoint(X3,Y3,R3,L3,X4,Y4,R4,L4),
   fd_labeling(L).

/* makevars(Size,L,L1) genere dans L1 les variables pour un sikaku de 
taille Size et une liste de points donnés dans L. Les contraintes
correspondantes sont aussi générées */

makevars(Size,[],[]).
makevars(Size,[(A,B,C)|L],[X1,Y1,R1,U1|L1]) :-
   X1+R1 #=< Size+1, Y1+U1 #=< Size+1,
   R1*U1 #= C,
   X1 #> 0, Y1 #> 0,
   covered(X1,Y1,R1,U1,A,B),
   makevars(Size,L,L1),
   disjoint(X1,Y1,R1,U1,L1).

disjoint(X1,Y1,R1,U1,[]).

disjoint(X1,Y1,R1,U1,[X2,Y2,R2,U2|L]) :-
   disjoint(X1,Y1,R1,U1,X2,Y2,R2,U2),
   disjoint(X1,Y1,R1,U1,L).

sikaku(Size,L,L1) :- 
   makevars(Size,L,L1),
   fd_labeling(L1).
  
/* le probleme suivant est une problème 7*7. Il se resoud avec
   ?- probleme(L),sikaku(7,L,L1) */ 
probleme([(1,5,4),(1,6,4),(2,1,4),(2,3,2),(3,1,6),(3,6,6),(4,4,2),(5,2,4),(5,7,2),(6,5,6),(6,7,2),(7,2,2),(7,3,5)]).















