4 Reasoning with Constraints

4.2 Solving CSPs by Searching

A finite CSP could be solved by exhaustively searching the total assignments.

The generate-and-test algorithm to find one solution is as follows: check each total assignment in turn; if an assignment is found that satisfies all of the constraints, return that assignment. A generate-and-test algorithm to find all solutions is the same except, instead of returning the first solution found, it enumerates the solutions.

Example 4.10.

In Example 4.9, the assignment space is

S={ {A= 1,B= 1,C= 1,D= 1,E= 1},
{A= 1,B= 1,C= 1,D= 1,E= 2},…,
{A= 4,B= 4,C= 4,D= 4,E= 4}}.

In this case there are |S|=45=1024 different assignments to be tested. If there were fifteen variables instead of five, there would be 415, which is about a billion, assignments to test. This method could not work for thirty variables.

If there are n variables, each with domain size d, there are dn total assignments. If there are e constraints, the total number of constraints tested is O⁢(e⁢dn). As n becomes large, this becomes intractable very quickly.

The generate-and-test algorithm assigns values to all variables before checking the constraints. Because individual constraints only involve a subset of the variables, some constraints can be tested before all of the variables have been assigned values. If a partial assignment violates a constraint, any total assignment that extends the partial assignment will also violate the constraint. This can potentially prune a large part of the search space.

Example 4.11.

In the delivery scheduling problem of Example 4.9, the assignment {A= 1,B= 1} violates the constraint A≠B regardless of the values of the other variables. If the variables A and B are assigned values first, this violation can be discovered before any values are assigned to C, D, or E, thus saving a large amount of work.

1: procedure DFS_solver(V⁢s, C⁢s, c⁢o⁢n⁢t⁢e⁢x⁢t)
2:   Let ce={c∈Cs∣c can be evaluated in context}
3:   if c⁢o⁢n⁢t⁢e⁢x⁢t violates a constraint in c⁢e then
4:    return {}
5:   else if V⁢s={} then
6:    return {c⁢o⁢n⁢t⁢e⁢x⁢t}
7:   else
8:    select variable v⁢a⁢r∈V⁢s
9:    s⁢o⁢l⁢s:={}
10:    for v⁢a⁢l in d⁢o⁢m⁢a⁢i⁢n⁢(v⁢a⁢r) do
11:      sols:=sols∪DFS_solver(Vs∖{var}, C⁢s∖c⁢e, {v⁢a⁢r=v⁢a⁢l}∪c⁢o⁢n⁢t⁢e⁢x⁢t)    
12:    return s⁢o⁢l⁢s   
Figure 4.1: Search-based algorithm to find all solutions to a CSP

Figure 4.1 gives a depth-first search-based algorithm to find all solutions for a CSP defined by variables V⁢s and constraints C⁢s that extend c⁢o⁢n⁢t⁢e⁢x⁢t, a partial or total assignment. V⁢s contains the variables not assigned in c⁢o⁢n⁢t⁢e⁢x⁢t, and C⁢s contains the constraints that involve at least one variable in V⁢s. It is called initially using

D⁢F⁢S⁢_⁢s⁢o⁢l⁢v⁢e⁢r⁢(V⁢s,C⁢s,{})

where V⁢s is the set of all variables, and C⁢s is the set of all constraints in a CSP, with d⁢o⁢m⁢a⁢i⁢n implicit.

It first collects in c⁢e the assignments that can be evaluated given the context. If the context violates a constraint that can be evaluated, there are no solutions that extend this context. If there are no variables in V⁢s, all variables have been assigned and so all constraints have been satisfied and it has found a solution. Otherwise, it selects a variable not assigned in the context and branches on all values of that variable.

This algorithm can be modified to implement generate and test by making it check the constraints only when all variables have been assigned.

The search-based algorithm carries out a depth-first search. It is possible to use any of the search strategies of the previous chapter to search the graph of assignments. However, as all of the solution paths are the same length – the length is the number of variables – there is not much point in doing so.

Example 4.12.

Consider a CSP with variables A, B, and C, each with domain {1,2,3,4}, and constraints A<B and B<C. A possible search tree is shown in Figure 4.2.

Refer to caption
Figure 4.2: A possible search tree for the CSP of Example 4.12

In this figure, a node corresponds to all of the assignments from the root to that node. The potential nodes that are pruned because they violate constraints are labeled ✘.

The leftmost ✘ corresponds to the assignment {A= 1, B= 1}. This violates the A<B constraint, and so it is pruned.

This CSP has four solutions. The leftmost one is {A= 1, B= 2, C= 3}. The size of the search tree, and thus the efficiency of the algorithm, depends on which variable is selected at each time. A static ordering, such as always splitting on A then B then C, is usually less efficient than the dynamic ordering used here, but it might be more difficult to find the best dynamic ordering than to find the best static ordering. The set of answers is the same regardless of the variable ordering.

There would be 43=64 total assignments tested in a generate-and-test algorithm. For the search method, there are 8 total assignments generated, and 16 other partial assignments that were tested as to whether they satisfy some of the constraints.