/*************************/ /* CSP over integers */ /* (forward checking) */ /* a plug-in module */ /* (c) R. Bart½k */ /* 1996 */ /*************************/ % this is a plug-in module for CSP labelling kernel (CSPkernel.pr) % it defines constraints eq,neq,lt(less then),gt(greater then),diff(different values % diff(ListOfVars)) with operations +,-,* % over integers (domains are finite sets of integers like [1ƒ5,7,9,15ƒ20] % it uses forward checking % example of usage: % ?-labelling([X::[1ƒ10],Y::[1ƒ10]],[lt(X,Y),eq(X+5,Y)],_). :-op(700,xfx,ƒ). % sort variables according to size of their domains (larger domains first) sort_vars([V|Vs],NVs):- sort_vars(Vs,AuxVs), ins_dom(V,AuxVs,NVs). sort_vars([],[]). % calculate domain size domain_size([H|T],OldS,NewS):- (H=[AƒB] -> AuxS is OldS+B-A+1 ; AuxS is OldS+1), domain_size(T,AuxS,NewS). domain_size([],Size,Size). % insert variable to list of variables according to domain size ins_dom(X::DX,Ds,NDs):- domain_size(DX,0,SX), ins_dom(Ds,X::DX,SX,NDs). ins_dom([Y::DY|T],DX,SX,NDs):- domain_size(DY,0,SY), (SY>=SX -> NDs=[DX,Y::DY|T] ; (NDs=[Y::DY|AuxDs],ins_dom(T,DX,SX,AuxDs))). ins_dom([],DX,_,[DX]). % generate member/test membership in domain domain_mem(X,[H|T]):- H=(AƒB) -> gen_num(X,A,B) ; X=H. domain_mem(X,[_|T]):- domain_mem(X,T). % generate member/test membership in interval gen_num(A,A,B):- A= (ER=0,NewVs=Vs) ; (X is -ER/EX,Tmp is EX*X+ER,Tmp=0,domain_mem(X,D),NewVs=AuxVs)). % test because of integer aritmetics eq([X],Vs,Vs,_,_). % don't test nonlinear equalities neq([],Vs,Vs,A,B):- CA is A, CB is B, CA\=CB. neq([X],Vs,NewVs,A,B):- extr_var(A,AX,AR), extr_var(B,BX,BR),!, find_domain(X,Vs,D,AuxVs), EX is AX-BX, ER is AR-BR, (EX=0 -> (ER\=0,NewVs=Vs) ; (Tmp is -ER/EX, Aux is EX*Tmp+ER, % test because of integer aritmetics (Aux=0 -> (eefd(Tmp,D,ND),ND\=[],ins_dom(X::ND,AuxVs,NewVs)) ; NewVs=Vs))). neq([X],Vs,Vs,_,_). % don't test nonlinear disequalities lt([],Vs,Vs,A,B):- CA is A, CB is B, CA (ER<0,NewVs=Vs) ; ((EX>0 -> (Tmp is -ER/EX-1,egfd(Tmp,D,ND)) ; (Tmp is -ER/EX+1,elfd(Tmp,D,ND))), ND\=[],ins_dom(X::ND,AuxVs,NewVs))). lt([X],Vs,Vs,_,_). % don't test nonlinear expressions gt([],Vs,Vs,A,B):- CA is A, CB is B, CA>CB. gt([X],Vs,NewVs,A,B):- extr_var(A,AX,AR), extr_var(B,BX,BR),!, find_domain(X,Vs,D,AuxVs), EX is AX-BX, ER is AR-BR, (EX=0 -> (ER>0,NewVs=Vs) ; ((EX>0 -> (Tmp is -ER/EX+1,elfd(Tmp,D,ND)) ; (Tmp is -ER/EX-1,egfd(Tmp,D,ND))), ND\=[],ins_dom(X::ND,AuxVs,NewVs))). gt([X],Vs,Vs,_,_). % don't test nonlinear expressions diff(Vars,Ds,NDs,List):- find_vals(List,[],Vals), elefld(Vals,Vars,Ds,NDs). find_vals([H|T],Old,New):- var(H), find_vals(T,Old,New). find_vals([H|T],Old,New):- nonvar(H), insert_val(H,Old,Aux), find_vals(T,Aux,New). find_vals([],Vals,Vals). insert_val(V,[H|T],[V,H|T]):- VH,insert_val(V,T,NT). insert_val(V,[],[V]). find_domain(X,[YD|T],D,NewT):- YD=(Y::DY), X==Y -> (D=DY,NewT=T) ; (find_domain(X,T,D,AuxT),NewT=[YD|AuxT]). % convert expression E to EX*Var+ER, if possible % (assumes that there is max. one free variable) extr_var(E,EX,ER):- nonvar(E),E=A+B,!, extr_var(A,AX,AR),extr_var(B,BX,BR), EX is AX+BX, ER is AR+BR,!. extr_var(E,EX,ER):- nonvar(E),E=A-B,!, extr_var(A,AX,AR),extr_var(B,BX,BR), EX is AX-BX, ER is AR-BR,!. extr_var(E,EX,ER):- nonvar(E),E=A*B,!, extr_var(A,AX,AR),extr_var(B,BX,BR), DoubleX is AX*BX, DoubleX=0, % nonlinear expression can't be solved EX is AX*BR+AR*BX, ER is AR*BR,!. extr_var(Y,1,0):- var(Y),!. extr_var(Y,0,Y):- nonvar(Y). % elefld-eliminate list of elements from list of domains elefld([],_,Ds,Ds):-!. elefld(Es,[V|Vs],Ds,NDs):- find_domain(V,Ds,D,RD), elefd(Es,D,ND),ND\=[], elefld(Es,Vs,RD,AuxDs), ins_dom(V::ND,AuxDs,NDs). elefld(_,[],Ds,Ds). % elefd-eliminate list of elements from domain elefd([E|Es],[H|T],ND):- H=(AƒB) -> (E elefd(Es,[H|T],ND) ; E= (eefi(E,A,B,T,Aux),elefd(Es,Aux,ND)) ; (elefd([E|Es],T,AuxD),ND=[H|AuxD])) ; (E=H -> elefd(Es,T,ND) ; (E elefd(Es,[H|T],ND) ; (elefd([E|Es],T,AuxD),ND=[H|AuxD]))). elefd(_,[],[]):-!. elefd([],D,D). % eefd-eliminate element from domain eefd(E,[H|T],ND):- H=(AƒB) -> (E ND=[H|T] ; E= eefi(E,A,B,T,ND) ; (eefd(E,T,AuxD),ND=[H|AuxD])) ; (E=H -> ND=T ; (E ND=[H|T] ; (eefd(E,T,AuxD),ND=[H|AuxD]))). eefd(_,[],[]). % eefi-eliminate element from interval eefi(E,A,B,Rest,ND):- EM is E-1, EP is E+1, aitd(EP,B,Rest,Aux), aitd(A,EM,Aux,ND). % aitd-add interval to the beginning of the domain aitd(A,B,Old,Old):- B H=B ; H=(AƒB)). % egfd-eliminate greater elements from domain egfd(E,[H|T],ND):- H=(AƒB) -> (E ND=[] ; E= aitd(A,E,[],ND) ; (egfd(E,T,AuxD),ND=[H|AuxD])) ; (E ND=[] ; (egfd(E,T,AuxD),ND=[H|AuxD])). egfd(_,[],[]). % elfd-eliminate less elements from domain elfd(E,[H|T],ND):- H=(AƒB) -> (E= ND=[H|T] ; E= aitd(E,B,T,ND) ; elfd(E,T,ND)) ; (E= ND=[H|T] ; elfd(E,T,ND)). elfd(_,[],[]).