/* The Constraint Satisfaction Problem */ /* Demonstrated by the N queens problem */ /* We are given a set of variables, a finite and discrete domain for each variable, and a set of constraints. Each constraint is defined over some subset of the original set of variables, and limits the combinations of values that the variables in this subset can take. The goal is to find one assignment to the variables such that the assignment satisfies all the constraints. In some problems, the goal is to find all such assignments. We restrict the CSPs to those in which each constraint is binary. (The above definition and much of the descriptions of the various search procedures are taken from "Algorithms for Constraint Satisfaction Problems: A Survey" by Vipin Kumar.) */ /* * Library procedures */ /* integers(M, N, Is) is true if Is is the list of integers from M to N */ /* inclusive. */ integers(N, N, [N]):-!. integers(I, N, [I|Is]):-I < N, I1 is I + 1, integers(I1, N, Is). /* is_shorter(Xs, Ys) is true if the list Xs contains fewer elements than */ /* the list Ys. */ is_shorter([], [_|_]). is_shorter([_|Xs], [_|Ys]):-is_shorter(Xs, Ys). /* * Procedures particular to the N queens problem */ queens_gt(N, VVs):- integers(1, N, Is), initialize_domains(Is, Is, VDs), gt(VDs, [], VVs). queens_bt(N, VVs):- integers(1, N, Is), initialize_domains(Is, Is, VDs), bt(VDs, [], VVs). queens_fc(N, VVs):- integers(1, N, Is), initialize_domains(Is, Is, VDs), fc(VDs, VVs). queens_fcmrv(N, VVs):- integers(1, N, Is), initialize_domains(Is, Is, VDs), fcmrv(VDs, VVs). queens_fcmrvac(N, VVs):- integers(1, N, Is), initialize_domains(Is, Is, VDs), fcmrvac(VDs, VVs). queens_fcmrvdac(N, VVs):- integers(1, N, Is), initialize_domains(Is, Is, VDs), fcmrvdac(VDs, VVs). /* initialize_domains(Is, Is, VDs) is true if Is is a list of the integers */ /* from 1 to N, and VDs is the list [vd(1,Is),vd(2,Is),vd(3,Is),..., */ /* vd(N-1,Is),vd(N,Is)]. */ initialize_domains([], _, []). initialize_domains([Xi|Xis], Di, [vd(Xi,Di)|VDs]):- initialize_domains(Xis, Di, VDs). /* test(vv(Xh,Vh), vv(Xi,Vi)) is true if vv(Xi,Vi) is consistent with */ /* vv(Xh,Vh). */ test(vv(Xh,Vh), vv(Xi,Vi)):- Vh - Vi =\= 0, Vh - Vi =\= Xh - Xi, Vh - Vi =\= Xi - Xh. /* Generate and test: Each possible combination of the variables is systematically generated and then tested to see if it satisfies all the constraints. Each combination that satisfies all the constraints is a solution. The number of combinations considered by this method is the size of the Cartesian product of all the variable domains. */ /* gt(VDs, [], VVs) is true if for each element vd(Xi,Di) of the list VDs */ /* the corresponding element of the list VVs is vv(Xi,Vi) where Vi is an */ /* element of Di, such that the elements of VVs satisfy the constraints. */ /* On backtracking, all solutions will be found. */ gt([], VVs, VVs):- solution(VVs). gt([vd(Xi,[Vi|_])|VDs], VVs0, VVs):- gt(VDs, [vv(Xi,Vi)|VVs0], VVs). gt([vd(Xi,[_|Di])|VDs], VVs0, VVs):- gt([vd(Xi,Di)|VDs], VVs0, VVs). /* solution(VVs) is true if the elements vv(Xi,Vi) of VVs constitute a */ /* solution to the CSP. */ solution([]). solution([VV|VVs]):- consistent_all(VVs, VV), solution(VVs). /* consistent_all(VVs, vv(Xi,Vi)) is true if vv(Xi,Vi) is consistent with */ /* all the vv(Xh,Vh) in VVs. */ consistent_all([], _). consistent_all([VVh|VVs], VVi):- test(VVi, VVh), consistent_all(VVs, VVi). /* Backtracking: In this method, variables are instantiated sequentially. As soon as all the variables relevant to a constraint are instantiated, the validity of the constraint is checked. If a partial instantiation violates any of the constraints, backtracking is performed to the most recently instantiated variable that still has alternatives available. Clearly, whenever a partial instantiation violates a constraint, backtracking is able to eliminate a subspace from the Cartesian product of all variable domains. The backtrack method essentially performs a depth-first search of the space of potential solutions of the CSP. In cases where the sizes of the domains are not all the same, it may be profitable to instantiate variables with the smallest domains first. Although, backtracking is strictly better than generate-and-test, its run- time complexity for most nontrivial problems is still exponential. One of the reasons for this poor performance is that the backtracking paradigm suffers from thrashing; i.e., search in different parts of the space keeps failing for the same reasons. */ /* bt(VDs, [], VVs) is true if for each element vd(Xi,Di) of the list VDs */ /* the corresponding element of the list VVs is vv(Xi,Vi) where Vi is an */ /* element of Di, such that the elements of VVs satisfy the constraints. */ /* On backtracking, all solutions will be found. */ bt([], VVs, VVs). bt([vd(Xi,[Vi|_])|VDs], VVs0, VVs):- consistent_all(VVs0, vv(Xi,Vi)), bt(VDs, [vv(Xi,Vi)|VVs0], VVs). bt([vd(Xi,[_|Di])|VDs], VVs0, VVs):- bt([vd(Xi,Di)|VDs], VVs0, VVs). /* Forward checking with chronological variable selection: Whenever a new variable instantiation is made, the domains of all as yet uninstantiated variables are filtered to contain only those values that are consistent with this instantiation. If the domains of any of these uninstantiated variables become null, then failure is recognized and backtracking occurs. The next variable in the list is selected for instantiation. */ /* fc(VDs, VVs) is true if for each element vd(Xi,Di) of the list VDs the */ /* corresponding element of the list VVs is vv(Xi,Vi) where Vi is an */ /* element of Di, such that the elements of VVs satisfy the constraints. */ /* On backtracking, all solutions will be found. */ fc([], []). fc([vd(Xi,[Vi|_])|VDs], [vv(Xi,Vi)|VVs]):- update_domains(VDs, vv(Xi,Vi), VDs1), fc(VDs1, VVs). fc([vd(Xi,[_|Di])|VDs], VVs):- fc([vd(Xi,Di)|VDs], VVs). /* update_domains(VDs0, vv(Xi,Vi), VDs) is true if: each element vd(Xh,Dk) */ /* of VDs is the same as the corresponding element vd(Xh,Dh) of VDs0 */ /* except that each value Vh is removed if vv(Xi,Vi) and vv(Xh,Vh) are */ /* not consistent; and no domain Dk is empty. */ /* e.g. update_domains([vd(2,[1,2,3,4]),vd(3,[1,2,3,4]),vd(4,[1,2,3,4])], */ /* vv(1,1), */ /* [vd(2,[3,4]),vd(3,[2,4]),vd(4,[2,3])]). */ update_domains([], _, []). update_domains([vd(Xh,Dh)|VDs0], VV, [vd(Xh,Dk)|VDs]):- update_domain(Dh, Xh, VV, Dk), Dk=[_|_], update_domains(VDs0, VV, VDs). /* update_domain(Dh, Xh, vv(Xi,Vi), Dk) is true if the domain Dk is the */ /* same as the domain Dh except that each value Vh is removed if */ /* vv(Xi,Vi) and vv(Xh,Vh) are not consistent. */ update_domain([], _, _, []). update_domain([Vh|Dh], Xh, VVi, Dk):- /* \+... helps to avoid heap overflow but is slightly slower */ /* than putting the test in the next clause */ \+ test(vv(Xh,Vh), VVi), !, update_domain(Dh, Xh, VVi, Dk). update_domain([Vh|Dh], Xh, VVi, [Vh|Dk]):- update_domain(Dh, Xh, VVi, Dk). /* Forward checking with dynamic variable ordering: Whenever a new variable instantiation is made, the domains of all as yet uninstantiated variables are filtered to contain only those values that are consistent with this instantiation. If the domains of any of these uninstantiated variables become null, then failure is recognized and backtracking occurs. The variable with the minimum remaining values (MRV) is selected for instantiation. */ /* fcmrv(VDs, VVs) is true if for each element vd(Xi,Di) of the list VDs */ /* the corresponding element of the list VVs is vv(Xi,Vi) where Vi is an */ /* element of Di, such that the elements of VVs satisfy the constraints. */ /* On backtracking, all solutions will be found. */ fcmrv([], []). fcmrv([VD|VDs], [vv(Xi,Vi)|VVs]):- shortest_and_rest(VDs, VD, vd(Xi,Di), VDs1), member(Vi, Di), update_domains(VDs1, vv(Xi,Vi), VDs2), fcmrv(VDs2, VVs). /* shortest_and_rest(VDs, VD, Shortest, Rest) is true if Shortest is the */ /* shortest element of [VD|VDs] and Rest contains the other elements of */ /* [VD|VDs] (not necessarily in the same order). */ shortest_and_rest([], Shortest, Shortest, []). shortest_and_rest([vd(Xh,Dh)|VDs], vd(Xi,Di), Shortest, [vd(Xi,Di)|Rest]):- is_shorter(Dh, Di), !, shortest_and_rest(VDs, vd(Xh,Dh), Shortest, Rest). shortest_and_rest([VD|VDs], BestSoFar, Shortest, [VD|Rest]):- shortest_and_rest(VDs, BestSoFar, Shortest, Rest). /* Forward checking with dynamic variable ordering and arc consistency: Whenever a new variable instantiation is made, the domains of all as yet uninstantiated variables are filtered to contain only those values that are consistent with this instantiation. Arc consistency is enforced for all uninstantiated variables. If the domains of any of these uninstantiated variables become null, then failure is recognized and backtracking occurs. The variable with the minimum remaining values (MRV) is selected for instantiation. (Arc (Xi ,Xj) is arc consistent if for every value Vi in the current domain of Xi there is some value Vj in the domain of Xj such that Xi = Vi and Xj = Vj is permitted by the binary constraint between Xi and Xj.) */ /* fcmrvac(VDs, VVs) is true if for each element vd(Xi,Di) of the list VDs */ /* the corresponding element of the list VVs is vv(Xi,Vi) where Vi is an */ /* element of Di, such that the elements of VVs satisfy the constraints. */ /* On backtracking, all solutions will be found. */ fcmrvac([], []). fcmrvac([VD|VDs], [vv(Xi,Vi)|VVs]):- shortest_and_rest(VDs, VD, vd(Xi,Di), VDs1), member(Vi, Di), update_domains(VDs1, vv(Xi,Vi), VDs2), arc_consistency(VDs2, VDs3), fcmrvac(VDs3, VVs). /* arc_consistency(VDs0, VDs) is true if: for each element vd(Xi,Di) of */ /* the list VDs0, the corresponding element of the list VDs is vd(Xi,Dk) */ /* where Dk contains those elements Vi of Di for which there is a Vh in */ /* each of the *other* elements vd(Xh,Dh) of VDs0 such that vv(Xh,Vh) is */ /* consistent with vv(Xi,Vi); and no Dk is empty. */ /* e.g. arc_consistency([vd(2,[4]),vd(3,[1,3]),vd(4,[1,3,4])], */ /* [vd(2,[4]),vd(3,[1]),vd(4,[3])]). */ /* e.g. arc_consistency([vd(2,[3,4]),vd(3,[2,4]),vd(4,[2,3])], X) fails */ arc_consistency(VDs0, VDs):- arc_consistency_1(VDs0, [], VDs1, nochange, Flag), arc_consistency_0(Flag, VDs1, VDs). /* Fails if a domain becomes empty */ arc_consistency_0(change, VDs1, VDs):- /* Changes have been made - iterate */ arc_consistency(VDs1, VDs). arc_consistency_0(nochange, VDs, VDs). /* No changes have been made - return */ arc_consistency_1([], _, [], Flag, Flag). arc_consistency_1([VDi|VDis], VDks0, VDks, Flag0, Flag):- arc_consistency_2(VDks0, VDi, VDk1), arc_consistency_2(VDis, VDk1, VDk2), !, arc_consistency_1_1([VDi|VDis], VDks0, VDks, Flag0, Flag, VDk2). arc_consistency_1([_|_], _, [], _, emptydomain). /* arc_consistency_2/3 failed - a domain has become empty */ arc_consistency_1_1([VDi|VDis], VDks0, [VDk2|VDks], _, Flag, VDk2):- VDi \= VDk2, !, /* Changes have been made */ arc_consistency_1(VDis, [VDk2|VDks0], VDks, change, Flag). arc_consistency_1_1([VDi|VDis], VDks0, [VDi|VDks], Flag0, Flag, _):- /* No changes have been made */ arc_consistency_1(VDis, [VDi|VDks0], VDks, Flag0, Flag). /* arc_consistency_2(VDs, vd(Xi,Di), vd(Xi,Dk)) is true if the domain Dk */ /* is not empty and is the same as the domain Di except that each value */ /* Vi is removed if there is no value Vh in the domain of any Xh in VDs */ /* such that vv(Xi,Vi) and vv(Xh,Vh) are consistent. */ arc_consistency_2([], VDi, VDi). arc_consistency_2([VD|VDs], vd(Xi,Di), VDk):- revise(Di, Xi, VD, Dk), Dk=[_|_], arc_consistency_2(VDs, vd(Xi,Dk), VDk). /* revise(Di, Xi, vd(Xh,Dh), Dk) is true if the domain Dk is not empty, */ /* and is the same as the domain Di except that each value Vi is removed */ /* if there is no value Vh in Dh such that vv(Xi,Vi) and vv(Xh,Vh) are */ /* consistent. */ revise([], _, _, []). revise([Vi|Di], Xi, VD, [Vi|Dk]):- VD=vd(Xh, Dh), consistent_any(Dh, Xh, Vi, Xi), !, revise(Di, Xi, VD, Dk). revise([_|Di], Xi, VD, Dk):- revise(Di, Xi, VD, Dk). /* consistent_any(Dh, Xh, Vi, Xi) is true if there exists a Vh in Dh such */ /* that vv(Xi,Vi) and vv(Xh,Vh) are consistent. */ consistent_any([Vh|_], Xh, Vi, Xi):- test(vv(Xh,Vh), vv(Xi,Vi)), !. consistent_any([_|Dh], Xh, Vi, Xi):- consistent_any(Dh, Xh, Vi, Xi). /* Forward checking with dynamic variable ordering and directional arc consistency: Whenever a new variable instantiation is made, the domains of all as yet uninstantiated variables are filtered to contain only those values that are consistent with this instantiation. Directional arc consistency is enforced for all uninstantiated variables. If the domains of any of these uninstantiated variables become null, then failure is recognized and backtracking occurs. The variable with the minimum remaining values (MRV) is selected for instantiation. */ /* fcmrvdac(VDs, VVs) is true if for each element vd(Xi,Di) of the list */ /* VDs the corresponding element of the list VVs is vv(Xi,Vi) where Vi */ /* is an element of Di, such that the elements of VVs satisfy the */ /* constraints. On backtracking, all solutions will be found. */ fcmrvdac([], []). fcmrvdac([VD|VDs], [vv(Xi,Vi)|VVs]):- shortest_and_rest(VDs, VD, vd(Xi,Di), VDs1), member(Vi, Di), update_domains(VDs1, vv(Xi,Vi), VDs2), directional_arc_consistency(VDs2, VDs3), fcmrvdac(VDs3, VVs). /* directional_arc_consistency(VDs0, VDs) is true if: for each element */ /* vd(Xi,Di) of the list VDs0, the corresponding element of the list VDs */ /* is vd(Xi,Dk) where Dk contains those elements Vi of Di for which */ /* there is a Vh in each of the *following* elements vd(Xh,Dh) of VDs0 */ /* such that vv(Xh,Vh) is consistent with vv(Xi,Vi); and no Dk is empty. */ /* e.g. */ /* directional_arc_consistency([vd(2,[3,4]),vd(3,[2,4]),vd(4,[2,3])], VDs).*/ /* gives VDs=[vd(2,[4]),vd(3,[4]),vd(4,[2,3])] */ directional_arc_consistency([], []). directional_arc_consistency([vd(Xi,Di)|VDs0], [vd(Xi,Dk)|VDs]):- findall(Vi, directional_arc_consistency_1(Di, Xi, VDs0, Vi), Dk), Dk=[_|_], directional_arc_consistency(VDs0, VDs). directional_arc_consistency_1(Di, Xi, VDs, Vi):- member(Vi, Di), directional_arc_consistency_2(VDs, vv(Xi,Vi)). /* directional_arc_consistency_2(VDs, vv(Xi,Vi)) is true if for each */ /* element vd(Xh,Dh) of VDs there exists an element Vh of Dh such that */ /* vv(Xh,Vh) is consistent with vv(Xi,Vi). */ directional_arc_consistency_2([], _). directional_arc_consistency_2([vd(Xh,Dh)|VDs], vv(Xi,Vi)):- consistent_any(Dh, Xh, Vi, Xi), directional_arc_consistency_2(VDs, vv(Xi,Vi)).