The Constraint Satisfaction Problem (CSP)

/* 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)).

LPA Index     Home Page

Valid HTML 4.01 Strict