5 CONSTRAINT SATISFACTION PROBLEMS In which we see ho reating states as more than just black boxes leads tothe complken search methods and a deeper understanding Chapters 3 and 4 explored the idea that problems can be solved by searching in a space of states.These states can be evaluated by domain-specific heuristics and tested to see whether they are goal states.From the point of view of the search algorithm,however, BLACK BOX each state is a black box with no discernible internal structure.It is represented by an arbi- trary data structure that can be accessed only by the problem-specific routines-the successor function heuristic function and goal test This chapter examines constraint satisfaction problems.whose states and goal test conform to a standard,structured,and very simple rep resentation (Section 5 1)Search al- cture of states and use general-purpose 0ns5.2 5.3).Perhaps most tantly,the standard representation of the ture of the itself (Section 5.4).This anderstanding of the intimate between the structure of a problem and of solving it 5.1 CONSTRAINT SATISFACTION PROBLEMS Formally speaking,a constraint satisfaction problem(or CSP)is defined by a set of vari- ARIABLES ables,X1,X2,....Xn.and a set of constraints,C1,C2.....Cm.Each variable Xi has a CONSTRAINTS nonempty domain Di of possible values.Each constraint Ci involves some subset of the DOMAIN variables and specifies the allowable combinations of values for that subset.A state of the VALUES problem is defined by an assignment of values to some or all ofthe variables,{X;=vi,X;= ASSIGNENT ...)An assignment that does not violate any constraints is called a consistent or legal CONSISTENT assignment.A complete assignment is one in which every variable is mentioned,and a so- lution to a CSP is a complete assignment that satisfies all the constraints.Some CSPs also 8 require a solution that maximizes an objective function. 137
5 CONSTRAINT SATISFACTION PROBLEMS In which we see how treating states as more than just little black boxes leads to the invention of a range of powerful new search methods and a deeper understanding of problem structure and complexity. Chapters 3 and 4 explored the idea that problems can be solved by searching in a space of states. These states can be evaluated by domain-specific heuristics and tested to see whether they are goal states. From the point of view of the search algorithm, however, BLACK BOX each state is a black box with no discernible internal structure. It is represented by an arbitrary data structure that can be accessed only by the problem-specific routines—the successor function, heuristic function, and goal test. This chapter examines constraint satisfaction problems, whose states and goal test REPRESENTATION conform to a standard, structured, and very simple representation (Section 5.1). Search algorithms can be defined that take advantage of the structure of states and use general-purpose rather than problem-specific heuristics to enable the solution of large problems (Sections 5.2– 5.3). Perhaps most importantly, the standard representation of the goal test reveals the structure of the problem itself (Section 5.4). This leads to methods for problem decomposition and to an understanding of the intimate connection between the structure of a problem and the difficulty of solving it. 5.1 CONSTRAINT SATISFACTION PROBLEMS Formally speaking, a constraint satisfaction problem (or CSP) is defined by a set of vari- CONSTRAINT SATISFACTION PROBLEM VARIABLES ables, X1, X2, . . . , Xn, and a set of constraints, C1, C2, . . . , Cm. Each variable Xi has a CONSTRAINTS nonempty domain Di of possible values. Each constraint Ci involves some subset of the DOMAIN VALUES variables and specifies the allowable combinations of values for that subset. A state of the problem is defined by an assignment of valuesto some or all of the variables, {Xi = vi , Xj = ASSIGNMENT vj , . . .}. An assignment that does not violate any constraints is called a consistent or legal CONSISTENT assignment. A complete assignment is one in which every variable is mentioned, and a solution to a CSP is a complete assignment that satisfies all the constraints. Some CSPs also require a solution that maximizes an objective function. OBJECTIVE FUNCTION 137
138 Chapter 5.Constraint Satisfaction Problems what does all this mean?Suppose that,having tired of Romnia.eare ookin at a map of. eachregion either red.green,or blue insandh of c owing cach and territories,as ing regions nis as a CSP,we to be the regions the se (red,green).(red,biue),(green,red),(green,blue).(bue,red),(blue,green) (The constraint can also be represented more succinctly as the inequality WA NT,pro- vided the constraint satisfaction algorithm has some way to evaluate such expressions.)There are many possible solutions such as {WA=red,NT=green,Q=red,NSW green,V=red,SA=blue,T=red } It is helpful to visualize a CSPas a constraint graph,as shown in Figure 5.1(b).The nodes of the graph correspond to variables of the problem and the arcs correspond to constraints Treating a problem as a CSP confers several important benefits.Because the representa tion of states in a CSP conforms to a standard pattern-that is,a set of variables with assigned -the successor function and goal test can written in a generic way that applies to al CSPs.Furthermore,we can develop effective,generic heuristics that require no additional domain-specific expertise.Finally,the structure of the constraint graph can be used to sim- plify the solution process,in some cases giving an exponential reduction in complexity.The CSP representation is the first,and simplest,in a series of representation schemes that will be developed throughout the book. NT SA Victoria Tasmania (a) (b) Figure 5.1 on pro s to map-c ng pr m represente as a constraint graph
138 Chapter 5. Constraint Satisfaction Problems So what does all this mean? Suppose that, having tired of Romania, we are looking at a map of Australia showing each of its states and territories, as in Figure 5.1(a), and that we are given the task of coloring each region either red, green, or blue in such a way that no neighboring regions have the same color. To formulate this as a CSP, we define the variables to be the regions: WA, NT, Q, NSW , V , SA, and T. The domain of each variable is the set {red, green, blue}. The constraints require neighboring regions to have distinct colors; for example, the allowable combinations for WA and NT are the pairs {(red, green),(red, blue),(green, red),(green, blue),(blue, red),(blue, green)} . (The constraint can also be represented more succinctly as the inequality WA 6= NT, provided the constraint satisfaction algorithm has some way to evaluate such expressions.) There are many possible solutions, such as {WA = red, NT = green, Q = red, NSW = green, V = red, SA = blue, T = red }. CONSTRAINT GRAPH It is helpful to visualize a CSP as a constraint graph, as shown in Figure 5.1(b). The nodes of the graph correspond to variables of the problem and the arcs correspond to constraints. Treating a problem as a CSP confers several important benefits. Because the representation of states in a CSP conforms to a standard pattern—that is, a set of variables with assigned values—the successor function and goal test can written in a generic way that applies to all CSPs. Furthermore, we can develop effective, generic heuristics that require no additional, domain-specific expertise. Finally, the structure of the constraint graph can be used to simplify the solution process, in some cases giving an exponential reduction in complexity. The CSP representation is the first, and simplest, in a series of representation schemes that will be developed throughout the book. Western Australia Northern Territory South Australia Queensland New South Wales Victoria Tasmania WA NT SA Q NSW V T (a) (b) Figure 5.1 (a) The principal states and territories of Australia. Coloring this map can be viewed as a constraint satisfaction problem. The goal is to assign colors to each region so that no neighboring regions have the same color. (b) The map-coloring problem represented as a constraint graph
Section 5.1. Constraint Satisfaction Problems 139 It is fairly easy to see that a CSP can be given an incremental formulation as a standard search problem as follows Initial state:the empty assignment in which all variables are unassigned. Successor function:a value can be assigned to any unassigned variable,provided that it does not conflict with previously assigned variables Goal test:the curent assignment is complete. Path cost:a constant cost (e.g..1)for every step. earch algor thaplete assignment and therelore appears at depth n if therear nds are popu CSP 2)t that which eve a night the co forhSth 53 riables that are 1 ems are o f this n Chapt te-domain CS where each queen in c cach v ne do 2,6 .8 th main size of an then hat is,exponential in the Ite-a BOOLEAN CSPS include Boolean CSPs, whos can be e or fals Boolean CSP as special ca NP-complete probler ms,such as 3s (See Chapter 7.)Int cas ,therefore we cannot expect to solve finite-domain CSPs in less than exponentia In most practical applications,however,general-purpose CSP algorithms can solve problems orders ofmagnitde larger than those solvable via the general-purpose search algorithms that we saw in Chapter NFINTE DOMAINS Discrete variables can also have infinite domains-for example,the set of integers o the set of strings.For example,when scheduling construction jobs onto a calendar,each job's start date is a variable and the possible values are integer numbers of days from the current date.With infinite domains.it is no longer possible to describe constraints by enumerating aR all allowed combinations of values.Instead,a constraint language must be used.For ex- ample,if Job.which takes five days,must precede Jobs.then we would need a constraint language of algebraic inequalities such as StartJob+5<StartJob3.It is also no longer possible to solve such constraints by enumerating all possible assignments,because there are nfinitely many of them.Special solution algorithms(which we will not discuss here)exist ONSTPAINTS for linear constraints on integer variables-that is,constraints,such as the one just given, in which each variable appears only in linear form.It can be shown that no algorithm exists &8棉S for solving general nonlinear constraints on integer variables.In some cases.we can reduce integer constraint problems to finite-domain problems simply by bounding the values of all the variables.For example,in a scheduling problem,we can set an upper bound equal to the total length of all the jobs to be scheduled. CONANSOUS Constraint satisfaction problems with continuous domains are very common in the real world and are widely studied in the field of operations research.For example,the scheduling
Section 5.1. Constraint Satisfaction Problems 139 It is fairly easy to see that a CSP can be given an incremental formulation as a standard search problem as follows: ♦ Initial state: the empty assignment {}, in which all variables are unassigned. ♦ Successor function: a value can be assigned to any unassigned variable, provided that it does not conflict with previously assigned variables. ♦ Goal test: the current assignment is complete. ♦ Path cost: a constant cost (e.g., 1) for every step. Every solution must be a complete assignment and therefore appears at depth n if there are n variables. Furthermore, the search tree extends only to depth n. For these reasons, depth- first search algorithms are popular for CSPs. (See Section 5.2.) It is also the case that the path by which a solution is reached is irrelevant. Hence, we can also use a complete-state formulation, in which every state is a complete assignment that might or might not satisfy the constraints. Local search methods work well for this formulation. (See Section 5.3.) FINITE DOMAINS The simplest kind of CSP involves variables that are discrete and have finite domains. Map-coloring problems are of this kind. The 8-queens problem described in Chapter 3 can also be viewed as a finite-domain CSP, where the variables Q1, . . . , Q8 are the positions of each queen in columns 1, . . . , 8 and each variable has the domain {1, 2, 3, 4, 5, 6, 7, 8}. If the maximum domain size of any variable in a CSP is d, then the number of possible complete assignments is O(d n )—that is, exponential in the number of variables. Finite-domain CSPs BOOLEAN CSPS include Boolean CSPs, whose variables can be either true or false. Boolean CSPs include as special cases some NP-complete problems, such as 3SAT. (See Chapter 7.) In the worst case, therefore, we cannot expect to solve finite-domain CSPs in less than exponential time. In most practical applications, however, general-purpose CSP algorithms can solve problems orders of magnitude larger than those solvable via the general-purpose search algorithms that we saw in Chapter 3. INFINITE DOMAINS Discrete variables can also have infinite domains—for example, the set of integers or the set of strings. For example, when scheduling construction jobs onto a calendar, each job’s start date is a variable and the possible values are integer numbers of days from the current date. With infinite domains, it is no longer possible to describe constraints by enumerating all allowed combinations of values. Instead, a constraint language must be used. For ex- CONSTRAINT LANGUAGE ample, if Job1, which takes five days, must precede Job3, then we would need a constraint language of algebraic inequalities such as StartJob1 + 5 ≤ StartJob3. It is also no longer possible to solve such constraints by enumerating all possible assignments, because there are infinitely many of them. Special solution algorithms (which we will not discuss here) exist for linear constraints on integer variables—that is, constraints, such as the one just given, LINEAR CONSTRAINTS in which each variable appears only in linear form. It can be shown that no algorithm exists for solving general nonlinear constraints on integer variables. In some cases, we can reduce NONLINEAR CONSTRAINTS integer constraint problems to finite-domain problems simply by bounding the values of all the variables. For example, in a scheduling problem, we can set an upper bound equal to the total length of all the jobs to be scheduled. Constraintsatisfaction problems with continuous domains are very common in the real CONTINUOUS DOMAINS world and are widely studied in the field of operations research. For example, the scheduling
140 Chapter 5.Constraint Satisfaction Problems on the Hubble Space Telescope requires very precise timing of obse are contnuous-valu variab must obey a van e,and power constraint The best-known ntinuo of linear programming problems straints can be solved in time polynomial in the numb er of varial ferent types o constraints and objective unctions have also been studied- -quadratic programming,seconc order conic programming,and so on. In addition to examining the types of variables that can appear in CSPs,it is useful to NARY CONSTRAINT look at the types of constraints.The simplest type is the unary constraint,which restricts the value of a single variable.For example.it could be the case that South Australians actively dislike the color green.Every unary constraint can be eliminated simply by preprocessing the domain of the corresponding variable to remove any value that violates the constraint.A BINARY CONSTRAINT binary constraint relates two variables.For example.SA NSW is a binary constraint.A binary CSP is one with only binary constraints,it can be represented as a constraint graph,as in Figure 5.1(b). Higher-order constraints involve three or more variables.A familiar example is pro- vided by cryptarithmetic puzzles.(See Figure 5.2(a).)It is usual to insist that each letter in a cryptarithmetic puzzle represent a different digit.For the case in Figure 5.2(a)),this would be represented as the six-variable constraint Alldiff(F,T,U,W,R,O).Alternatively,it can be represented by a collection of binary constraints such as..The addition constraints on the four columns of the puzzle also involve several variables and can be written as O+0=R+10,X: X1+W+W=U+10,X2 X2+T+T=0+10:X3 X3=F where X,X2,and X3 are auxiliary variables representing the digit(0 or 1)carried over into the next column.Higher-order constraints can be represented in a constraint hypergraph such as the one shown in Figure 5.2(b).The sharp-eyed reader will have noticed that the Alldiff constraint can be broken down into binary constraints-FTFU,and so on. In fact,as Exercise 5.11 asks you to prove,every higher-order,finite-domain constraint can be reduced to a set of binary constraints ifenough auxiliary variables are introduced.Because of this.we will deal only with binary constraints in this chapter. The constraints we have described so far have all been absolute constraints,violation of which rules out a potential solution.Many real-world CSPs include preference constraints indicating which solutions are preferred.For example,in a university timetabling problem Prof.X might prefer teaching in the morning whereas Prof.Y prefers teaching in the after- noon.A timetable that has Prof.X teaching at 2 p.m.would still be a solution(unless Prof.X happens to be the department chair).but would not be an optimal one.Preference constraints can often be encoded as costs on individual variable assi nments -for example,assigning an afternoon slot for Prof.X costs 2 points against the overall objective function.whereas a morning slot costs 1.With this formulation,CSPs with preferences can be solved using opti-
140 Chapter 5. Constraint Satisfaction Problems of experiments on the Hubble Space Telescope requires very precise timing of observations; the start and finish of each observation and maneuver are continuous-valued variables that must obey a variety of astronomical, precedence, and power constraints. The best-known category of continuous-domain CSPs is that of linear programming problems, where con- LINEAR PROGRAMMING straints must be linear inequalities forming a convex region. Linear programming problems can be solved in time polynomial in the number of variables. Problems with different types of constraints and objective functions have also been studied—quadratic programming, secondorder conic programming, and so on. In addition to examining the types of variables that can appear in CSPs, it is useful to UNARY CONSTRAINT look at the types of constraints. The simplest type is the unary constraint, which restricts the value of a single variable. For example, it could be the case that South Australians actively dislike the color green. Every unary constraint can be eliminated simply by preprocessing the domain of the corresponding variable to remove any value that violates the constraint. A BINARY CONSTRAINT binary constraint relates two variables. For example, SA 6= NSW is a binary constraint. A binary CSP is one with only binary constraints; it can be represented as a constraint graph, as in Figure 5.1(b). Higher-order constraints involve three or more variables. A familiar example is proCRYPTARITHMETIC vided by cryptarithmetic puzzles. (See Figure 5.2(a).) It is usual to insist that each letter in a cryptarithmetic puzzle represent a different digit. For the case in Figure 5.2(a)), this would be represented as the six-variable constraint Alldiff (F, T,U, W, R, O). Alternatively, it can be represented by a collection of binary constraints such as F 6= T. The addition constraints on the four columns of the puzzle also involve several variables and can be written as O + O = R + 10 · X1 X1 + W + W = U + 10 · X2 X2 + T + T = O + 10 · X3 X3 = F where X1, X2, and X3 are auxiliary variables representing the digit (0 or 1) carried over into AUXILIARY VARIABLES the next column. Higher-order constraints can be represented in a constraint hypergraph, CONSTRAINT HYPERGRAPH such as the one shown in Figure 5.2(b). The sharp-eyed reader will have noticed that the Alldiff constraint can be broken down into binary constraints—F 6= T, F 6= U, and so on. In fact, as Exercise 5.11 asks you to prove, every higher-order, finite-domain constraint can be reduced to a set of binary constraints if enough auxiliary variables are introduced. Because of this, we will deal only with binary constraints in this chapter. The constraints we have described so far have all been absolute constraints, violation PREFERENCE of which rules out a potential solution. Many real-world CSPs include preference constraints indicating which solutions are preferred. For example, in a university timetabling problem, Prof. X might prefer teaching in the morning whereas Prof. Y prefers teaching in the afternoon. A timetable that has Prof. X teaching at 2 p.m. would still be a solution (unless Prof. X happens to be the department chair), but would not be an optimal one. Preference constraints can often be encoded as costs on individual variable assignments—for example, assigning an afternoon slot for Prof. X costs 2 points against the overall objective function, whereas a morning slot costs 1. With this formulation, CSPs with preferences can be solved using opti-
Section 5.2.Backtracking Search for CSPs 141 TWO F(T)mRO +TWO FOUR a (b) Figure5.2 (a)A cry arithmetic problem fach letter stands for a distinet digit the aim i to find a substitution of digits for letters such that the resulting sum is arithmetically correct. for the crypt em,sho sthecolumn addition constraints. chapter.erther patd or we do not discus such CPs further in ide some pointers in the notes sectio 5.2 BACKTRACKING SEARCH FOR CSPS The preceding section gave a formulation of CSPs as search problems.Using this formula- tion,any of the search algorithms from Chapters 3 and 4 can solve CSPs.Suppose we apply breadth-first search to the generic CSP problem formulation given in the preceding section. We quickly notice something terrible:the branching factor at the top level is nd,because any of d values can be assigned to any of n variables.At the next level,the branching factor is (n-1)d,and so on for n levels.We generate a tree with n!dn leaves,even though there are only d"possible complete assignments! Our seemingly reasonable but naive problem formulation has ignored a crucial property COMMUTATIVITY common to all CSPs:commutativity.A problem is commutative if the order of application of any given set of actions has no effect on the outcome.This is the case for CSPs be- cause,when assigning values to variables,we reach the same partial assignment,regardless 哈 of order.Therefore,all CSP search algorithms generate successors by considering possible assignments for only a single variable at each node in the search tree.For example,at the root node of a search tree for coloring the map of Australia,we might have a choice between SA=red,SA=green,and SA=blue,but we would never choose between SA=red and WA=blue.With this restriction,the number of leaves is d",as we would hope. The term backtracking search is used for a depth-first search that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign.The algorithm is shown in Figure 5.3.Notice that it uses,in effect,the one-at-a-time method of
Section 5.2. Backtracking Search for CSPs 141 (a) F T U W R O (b) + F T T O W W U O O R X3 X2 X1 Figure 5.2 (a) A cryptarithmetic problem. Each letter stands for a distinct digit; the aim is to find a substitution of digits for letters such that the resulting sum is arithmetically correct, with the added restriction that no leading zeroes are allowed. (b) The constraint hypergraph for the cryptarithmetic problem, showing the Alldiff constraint as well asthe column addition constraints. Each constraint is a square box connected to the variables it constrains. mization search methods, either path-based or local. We do not discuss such CSPs further in this chapter, but we provide some pointers in the bibliographical notes section. 5.2 BACKTRACKING SEARCH FOR CSPS The preceding section gave a formulation of CSPs as search problems. Using this formulation, any of the search algorithms from Chapters 3 and 4 can solve CSPs. Suppose we apply breadth-first search to the generic CSP problem formulation given in the preceding section. We quickly notice something terrible: the branching factor at the top level is nd, because any of d values can be assigned to any of n variables. At the next level, the branching factor is (n − 1)d, and so on for n levels. We generate a tree with n! · d n leaves, even though there are only d n possible complete assignments! Our seemingly reasonable but na¨ıve problem formulation has ignored a crucial property COMMUTATIVITY common to all CSPs: commutativity. A problem is commutative if the order of application of any given set of actions has no effect on the outcome. This is the case for CSPs because, when assigning values to variables, we reach the same partial assignment, regardless of order. Therefore, all CSP search algorithms generate successors by considering possible assignments for only a single variable at each node in the search tree. For example, at the root node of a search tree for coloring the map of Australia, we might have a choice between SA = red, SA = green, and SA = blue, but we would never choose between SA = red and WA = blue. With this restriction, the number of leaves is d n , as we would hope. The term backtracking search is used for a depth-first search that chooses values for BACKTRACKING SEARCH one variable at a time and backtracks when a variable has no legal values left to assign. The algorithm is shown in Figure 5.3. Notice that it uses, in effect, the one-at-a-time method of
142 Chapter 5.Constraint Satisfaction Problems function RECURSIVE-BACKTRACKING(assignment,csp)returns a solution,or failure if assignment is complete then return assignment rEC-UMASIONED-VARABLEVARALEnp) arue in ORDE result-RECURSIVE-BACKTRACKING(assignment,csp) SELECT-UNASSIGNEDVARLRE MAIN-VALUESD ment the general-purpose heuristics discussed in the text. WAgroen wehtscxamcgocadanhtatgwpo incremental successor generation described on page 76.Also,it extends the current assign ment to generate a successor,rather than copying it.Because the representation of CSPs is standardized,there is no need to supply BACKTRACKING-SEARCH with a domain-specific initial state,successor function,or goal test.Part of the search tree for the Australia problem is shown in Figure 5.4.where we have assigned variables in the order WA.NT.O. Plain backtracking is an uninformed algorithm in the terminology of Chapter 3,so we do not expect it to be very effective for large problems.The results for some sample problems nCegemeR5omeoeasehennsh are showr
142 Chapter 5. Constraint Satisfaction Problems function BACKTRACKING-SEARCH(csp) returns a solution, or failure return RECURSIVE-BACKTRACKING({ }, csp) function RECURSIVE-BACKTRACKING(assignment, csp) returns a solution, or failure if assignment is complete then return assignment var ← SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp], assignment, csp) for each value in ORDER-DOMAIN-VALUES(var , assignment, csp) do if value is consistent with assignment according to CONSTRAINTS[csp] then add {var = value} to assignment result ← RECURSIVE-BACKTRACKING(assignment, csp) if result 6= failure then return result remove {var = value} from assignment return failure Figure 5.3 A simple backtracking algorithm for constraint satisfaction problems. The algorithm is modeled on the recursive depth-first search of Chapter 3. The functions SELECT-UNASSIGNED-VARIABLE and ORDER-DOMAIN-VALUES can be used to implement the general-purpose heuristics discussed in the text. WA=red WA=green WA=blue WA=red NT=blue WA=red NT=green WA=red NT=green Q=red WA=red NT=green Q=blue Figure 5.4 Part of the search tree generated by simple backtracking for the map-coloring problem in Figure 5.1. incremental successor generation described on page 76. Also, it extends the current assignment to generate a successor, rather than copying it. Because the representation of CSPs is standardized, there is no need to supply BACKTRACKING-SEARCH with a domain-specific initial state, successor function, or goal test. Part of the search tree for the Australia problem is shown in Figure 5.4, where we have assigned variables in the order WA, NT, Q, . . .. Plain backtracking is an uninformed algorithm in the terminology of Chapter 3, so we do not expect it to be very effective for large problems. The results for some sample problems are shown in the first column of Figure 5.5 and confirm our expectations. In Chapter 4 we remedied the poor performance of uninformed search algorithms by supplying them with domain-specific heuristic functions derived from our knowledge of the problem. It turns out that we can solve CSPs efficiently without such domain-specific knowl-
Section 5.2. Backtracking Search for CSPs 143 Problem Backtracking BT+MRV Forward Checking FC+MRY Min-Conflicts (000 6 817 415 Random 2 942K 27K 77K 15K Figure 5.5 o right re simple orwa cell is the median number of consistenc checks (over five runs)required to solve the p lem;note that all entries except the two in the upper right are in thousands(K).Numbers in parentheses mean that no answer was found in the allotted number of checks.The first prob em is finding a ne 3 /1005 the total number of checks required to solve all n-Que problems for from 2 to 50 The third is the"Zebra Puzzle,"as described in Exercise 5.13.The last two are artificial random was not run on thes han the rward checking ot alwa edge.Instead,we find general-purpose methods that address the following questions: 1.Which variable should be assigned next,and in what order should its values be tried? 2.What are the implications of the current variable assignments for the other unassigned variables? 3.When a path fails-that is,a state is reached in which a variable has no legal values- can the search avoid repeating this failure in subsequent paths? The subsections that follow answer each of these questions in turn. Variable and value ordering The backtracking algorithm contains the line var+-SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp). By default,SELECT-UNASSIGNED-VARIABLE simply selects the next unassigned variable in the order given by the list VARIABLES[csp].This static variable ordering seldom results in the most efficient search.For example,after the assignments for WA=red and NT=green, there is only one possible value for SA,so it makes sense to assign SA=blue next rather than assigning Q.In fact,after SA is assigned,the choices for Q,NSW,and V are all forced.This intuitive idea-choosing the variable with the fewest"legal"values-is called the minimum remaining values(MRV)heuristic.It also has been called the"most constrained variable"or "fail-first"heuristic,the latter because it picks a variable that is most likely to cause a failure soon,thereby pruning the search tree.If there is a variable X with zero legal values remain- ing.the MRV heuristic will select X and failure will be detected immediately-avoiding pointless searches through other variables which always will fail when X is finally selected
Section 5.2. Backtracking Search for CSPs 143 Problem Backtracking BT+MRV Forward Checking FC+MRV Min-Conflicts USA (> 1,000K) (> 1,000K) 2K 60 64 n-Queens (> 40,000K) 13,500K (> 40,000K) 817K 4K Zebra 3,859K 1K 35K 0.5K 2K Random 1 415K 3K 26K 2K Random 2 942K 27K 77K 15K Figure 5.5 Comparison of various CSP algorithms on various problems. The algorithms from left to right, are simple backtracking, backtracking with the MRV heuristic, forward checking, forward checking with MRV, and minimum conflicts local search. Listed in each cell is the median number of consistency checks (over five runs) required to solve the problem; note that all entries except the two in the upper right are in thousands (K). Numbers in parentheses mean that no answer was found in the allotted number of checks. The first problem is finding a 4-coloring for the 50 states of the United States of America. The remaining problems are taken from Bacchus and van Run (1995), Table 1. The second problem counts the total number of checks required to solve all n-Queens problems for n from 2 to 50. The third is the “Zebra Puzzle,” as described in Exercise 5.13. The last two are artificial random problems. (Min-conflicts was not run on these.) The results suggest that forward checking with the MRV heuristic is better on all these problems than the other backtracking algorithms, but not always better than min-conflicts local search. edge. Instead, we find general-purpose methods that address the following questions: 1. Which variable should be assigned next, and in what order should its values be tried? 2. What are the implications of the current variable assignments for the other unassigned variables? 3. When a path fails—that is, a state is reached in which a variable has no legal values— can the search avoid repeating this failure in subsequent paths? The subsections that follow answer each of these questions in turn. Variable and value ordering The backtracking algorithm contains the line var ← SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp], assignment, csp). By default, SELECT-UNASSIGNED-VARIABLE simply selects the next unassigned variable in the order given by the list VARIABLES[csp]. This static variable ordering seldom results in the most efficient search. For example, after the assignments for WA = red and NT = green, there is only one possible value for SA, so it makes sense to assign SA = blue next rather than assigning Q. In fact, after SA is assigned, the choices for Q, NSW , and V are all forced. This intuitive idea—choosing the variable with the fewest “legal” values—is called the minimum remaining values (MRV) heuristic. It also has been called the “most constrained variable” or MINIMUM REMAINING VALUES “fail-first” heuristic, the latter because it picks a variable that is most likely to cause a failure soon, thereby pruning the search tree. If there is a variable X with zero legal values remaining, the MRV heuristic will select X and failure will be detected immediately—avoiding pointless searches through other variables which always will fail when X is finally selected
144 Chapter 5.Constraint Satisfaction Problems .labeled BT+MRV.shws mance of this heuristic 000 times depending on the prob that our pe compu a n that ma manage help at all in choosing the firs gion to co or in Australi initially every region has three ors. In this case degree heuristic comes choices by selecting the var able that is involved in the largest number of constraints on other unassigned variables.In Figure 5.1,SA is the variable with highest degree,5:the other variables have degree 2 or except for T,which has 0.In fact,once SA is chosen,applying the degree heuristic solves the problem without any false steps-you can choose any consistent color at each choice point and still arrive at a solution with no backtracking.The minimum remaining valucs heuristic is usually a more powerful guide,but the degree heuristic can be useful as a tie-breaker. Once a variable has been selected,the algorithm must decide on the order in which to 器uwe examine its values.For this,the least-constraining-value heuristic can be effective in some cases.It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.For example,suppose that in Figure 5.1 we have generated the partial assignment with WA=red and NT=green,and that our next choice is for Q.Blue would be a bad choice,because it eliminates the last legal value left for O's neighbor,SA.The least-constraining-value heuristic therefore prefers red to blue.In general,the heuristic is trying to leave the maximum flexibility for subsequent variable assignments.Of course,if we are trying to find all the solutions to a problem,not just the first one,then the ordering does not matter because we have to consider every value anyway.The same holds if there are no solutions to the problem. Propagating information through constraints So far our search algorithm considers the constraints on a variable only at the time that the variable is chosen by SELECT-UNASSIGNED-VARIABLE.But by looking at some of the constraints earlier in the search,or even before the search has started,we can drastically reduce the search space. Forward checking CHECANS One way to make better use of constraints during search is called forward checking.When ever a variable X is assigned,the forward checking process looks at each unassigned variable Y that is connected to x by a constraint and deletes from y's domain any value that is in- consistent with the valuc chosen for X.Figure 5.6 shows the progress of a map-coloring search with forward checking.There are two important points to notice about this exam. ple.First,notice that after assigning WA=red and Q=green,the domains of NT and SA are reduced to a single value:we have eliminated branching on these variables altogether by propagating information from WA and Q.The MRV heuristic.which is an obvious part. ner for forward checking.would automatically select SA and NT next.(Indeed,we can view forward checking as an efficient way to incrementally compute the information that the
144 Chapter 5. Constraint Satisfaction Problems The second column of Figure 5.5, labeled BT+MRV, shows the performance of this heuristic. The performance is 3 to 3,000 times better than simple backtracking, depending on the problem. Note that our performance measure ignores the extra cost of computing the heuristic values; the next subsection describes a method that makes this cost manageable. The MRV heuristic doesn’t help at all in choosing the first region to color in Australia, DEGREE HEURISTIC because initially every region has three legal colors. In this case, the degree heuristic comes in handy. It attempts to reduce the branching factor on future choices by selecting the variable that is involved in the largest number of constraints on other unassigned variables. In Figure 5.1, SA is the variable with highest degree, 5; the other variables have degree 2 or 3, except for T, which has 0. In fact, once SA is chosen, applying the degree heuristic solves the problem without any false steps—you can choose any consistent color at each choice point and still arrive at a solution with no backtracking. The minimum remaining values heuristic is usually a more powerful guide, but the degree heuristic can be useful as a tie-breaker. Once a variable has been selected, the algorithm must decide on the order in which to examine its values. For this, the least-constraining-value heuristic can be effective in some LEASTCONSTRAININGVALUE cases. It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph. For example, suppose that in Figure 5.1 we have generated the partial assignment with WA = red and NT = green, and that our next choice is for Q. Blue would be a bad choice, because it eliminates the last legal value left for Q’s neighbor, SA. The least-constraining-value heuristic therefore prefers red to blue. In general, the heuristic is trying to leave the maximum flexibility for subsequent variable assignments. Of course, if we are trying to find all the solutions to a problem, not just the first one, then the ordering does not matter because we have to consider every value anyway. The same holds if there are no solutions to the problem. Propagating information through constraints So far our search algorithm considers the constraints on a variable only at the time that the variable is chosen by SELECT-UNASSIGNED-VARIABLE. But by looking at some of the constraints earlier in the search, or even before the search has started, we can drastically reduce the search space. Forward checking One way to make better use of constraints during search is called forward checking. When- FORWARD CHECKING ever a variable X is assigned, the forward checking process looks at each unassigned variable Y that is connected to X by a constraint and deletes from Y ’s domain any value that is inconsistent with the value chosen for X. Figure 5.6 shows the progress of a map-coloring search with forward checking. There are two important points to notice about this example. First, notice that after assigning WA = red and Q = green, the domains of NT and SA are reduced to a single value; we have eliminated branching on these variables altogether by propagating information from WA and Q. The MRV heuristic, which is an obvious partner for forward checking, would automatically select SA and NT next. (Indeed, we can view forward checking as an efficient way to incrementally compute the information that the
Section 5.2. Backtracking Search for CSPs 145 NT NSW Initial domains After WA=red R G After Ougreen B After V=blue R BG©R RG B Figure 5.6 re is deleted from the domains of NT SA and NSW.AfterVbue,ble is deleted from the domains of NSW and SA,leaving SA with no legal values. 10 [WA=red,Q=green,V=blue}is inconsistent with the constraints of the problem,and the algorithm will therefore backtrack immediately. Constraint propagation Although fory tall of them.For ing detects manync der the third row or Figure It shows at when are ford d to be But they are adjacent and have the am value.Fo ard checking does not detect this as an inconsistency,because it does not look far s enough ahead.Constraint propagation is the general term for propagating the implications of a constraint on one variable onto other variables,in this case we need to propagate from WA and Q onto NT and SA.(as was done by forward checking)and then onto the constraint between NT and SA to detect the inconsistency.And we want to do this fast:it is no good reducing the amount of search if we spend more time propagating constraints than we would have spent doing a simple search ARC CONSISTENCY The idea of are consistency provides a fast method of constraint propagation that is substantially stronger than forward checking.Here,"are"refers to a directed arc in the con- straint graph.such as the arc from SA to NSW.Given the current domains of SA and NSW the arc is consistent if,for every value z of SA,there is some value y of NSW that is consis- tent with z.In the third row of Figure 5.6,the current domains of SA and NSW are (blue and {red,blue}respectively.For SA=blue,there is a consistent assignment for NSW namely,NSW=red:therefore,the arc from SA to NSW is consistent.On the other hand the reverse arc from NSW to SA is not consistent:for the assignment NSW=blue,there is no consistent assignment for SA.The arc can be made consistent by deleting the value blue from the domain of NSW. We can also apply arc consistency to the arc from SA to NT at the same stage in the search process.The third row of the table in Figure 5.6 shows that both variables have the domain (blue}.The result is that blue must be deleted from the domain of SA,leaving the domain empty.Thus,applying arc consistency has resulted in early detection of an inconsis-
Section 5.2. Backtracking Search for CSPs 145 Initial domains After WA=red After Q=green After V=blue R G B R R B R G B R G B B R G B R G B R G B R R R R G B B B G B R G B G G R G B R G B B G B R G B R G B R G B R G B WA NT Q NSW V SA T Figure 5.6 The progress of a map-coloring search with forward checking. WA = red is assigned first; then forward checking deletes red from the domains of the neighboring variables NT and SA. After Q = green, green is deleted from the domains of NT, SA, and NSW . After V = blue, blue is deleted from the domains of NSW and SA, leaving SA with no legal values. MRV heuristic needs to do its job.) A second point to notice is that, after V = blue, the domain of SA is empty. Hence, forward checking has detected that the partial assignment {WA = red, Q = green, V = blue} is inconsistent with the constraints of the problem, and the algorithm will therefore backtrack immediately. Constraint propagation Although forward checking detects many inconsistencies, it does not detect all of them. For example, consider the third row of Figure 5.6. It shows that when WA is red and Q is green, both NT and SA are forced to be blue. But they are adjacent and so cannot have the same value. Forward checking does not detect this as an inconsistency, because it does not look far enough ahead. Constraint propagation is the general term for propagating the implications CONSTRAINT PROPAGATION of a constraint on one variable onto other variables; in this case we need to propagate from WA and Q onto NT and SA, (as was done by forward checking) and then onto the constraint between NT and SA to detect the inconsistency. And we want to do this fast: it is no good reducing the amount of search if we spend more time propagating constraints than we would have spent doing a simple search. ARC CONSISTENCY The idea of arc consistency provides a fast method of constraint propagation that is substantially stronger than forward checking. Here, “arc” refers to a directed arc in the constraint graph, such as the arc from SA to NSW . Given the current domains of SA and NSW , the arc is consistent if, for every value x of SA, there is some value y of NSW that is consistent with x. In the third row of Figure 5.6, the current domains of SA and NSW are {blue} and {red, blue} respectively. For SA = blue, there is a consistent assignment for NSW , namely, NSW = red; therefore, the arc from SA to NSW is consistent. On the other hand, the reverse arc from NSW to SA is not consistent: for the assignment NSW = blue, there is no consistent assignment for SA. The arc can be made consistent by deleting the value blue from the domain of NSW . We can also apply arc consistency to the arc from SA to NT at the same stage in the search process. The third row of the table in Figure 5.6 shows that both variables have the domain {blue}. The result is that blue must be deleted from the domain of SA, leaving the domain empty. Thus, applying arc consistency has resulted in early detection of an inconsis-
146 Chapter 5.Constraint Satisfaction Problems AC-3 s the CSP.p with reduced do mains while queue is not empty do E-FIRST(queue) MO ()then add ()to queue REMoVE-INCONSISTENT-VALUE(e e for sach in DOMAIN[X:]do if no valuey in DoMAIN[X]allows()to satisfy the constraint between X andX then delete r from DOMAIN[X:];removed-true return removed Figure 5.7 The arc consistency algorithm AC-3.After applying AC-3.either every ard is arc-consistent,or some variable has an empty domain,indicating that the CSP cannot be made arc-c sistent (an thus the C nnot be solved The name“AC-3”was use d by the algorithm's inventor (Mackworth,1977)because it's the third version developed in the paper tency that is not detected by pure forward checking Arc nsistency che eking can be applied eithe e the b ginning of th search proce r as a propa after every (The latter algorithr s som MA stency.in epeatedly unt es remain. This is because ome varial an arc inconsistency,a new ar consistency could arise in arcs pointing to tha variable.The full algorithm for arc consistency,AC-3,uses a queue to keep track of the ares that need to be checked for inconsistency.(See Figure 5 7.)Each arc (Xi,Xi) in turn i removed from the agenda and checked:if any values need to be deleted from the domain Xi,then every arc (Xk,Xi)pointing to Xi must be reinserted I on the queue for checking.The complexity of arc consistency checking can be analyzed as follows:a binary CSP has at most O(n2)arcs;each are (X&,Xi)can be inserted on the agenda only d times,because Xi has at most d values to delete;checking consistency of an arc can be done in O(d2)time;so the total worst-case time is O(n2d).Although this is substantially more expensive than forward checking.the extra cost is usually worthwhile Because CSPs include 3SAT as a special case,we do not expect to find a polynomial- time algorithm that can decide whether a given CSP is consistent.Hence,we deduce that arc consistency does not reveal every possible inconsistency.For example,in Figure 5.1,the par- tial assignment WA=red,NSW=red}is inconsistent,but AC-3 will not find the incon- The AC-4 algorithm,due to Mohr and Henderson(1986),runs in O(n).See Exereise 5.10
146 Chapter 5. Constraint Satisfaction Problems function AC-3(csp) returns the CSP, possibly with reduced domains inputs: csp, a binary CSP with variables {X1, X2, . . . , Xn} local variables: queue, a queue of arcs, initially all the arcs in csp while queue is not empty do (Xi , Xj ) ← REMOVE-FIRST(queue) if REMOVE-INCONSISTENT-VALUES(Xi , Xj ) then for each Xk in NEIGHBORS[Xi] do add (Xk, Xi) to queue function REMOVE-INCONSISTENT-VALUES(Xi , Xj ) returns true iff we remove a value removed ←false for each x in DOMAIN[Xi] do if no value y in DOMAIN[Xj ] allows (x ,y) to satisfy the constraint between Xi and Xj then delete x from DOMAIN[Xi]; removed ←true return removed Figure 5.7 The arc consistency algorithm AC-3. After applying AC-3, either every arc is arc-consistent, or some variable has an empty domain, indicating that the CSP cannot be made arc-consistent (and thus the CSP cannot be solved). The name “AC-3” was used by the algorithm’s inventor (Mackworth, 1977) because it’s the third version developed in the paper. tency that is not detected by pure forward checking. Arc consistency checking can be applied either as a preprocessing step before the beginning of the search process, or as a propagation step (like forward checking) after every assignment during search. (The latter algorithm is sometimes called MAC, for Maintaining Arc Consistency.) In either case, the process must be applied repeatedly until no more inconsistencies remain. This is because, whenever a value is deleted from some variable’s domain to remove an arc inconsistency, a new arc inconsistency could arise in arcs pointing to that variable. The full algorithm for arc consistency, AC-3, uses a queue to keep track of the arcs that need to be checked for inconsistency. (See Figure 5.7.) Each arc (Xi , Xj ) in turn is removed from the agenda and checked; if any values need to be deleted from the domain of Xi , then every arc (Xk, Xi) pointing to Xi must be reinserted on the queue for checking. The complexity of arc consistency checking can be analyzed as follows: a binary CSP has at most O(n 2 ) arcs; each arc (Xk, Xi) can be inserted on the agenda only d times, because Xi has at most d values to delete; checking consistency of an arc can be done in O(d 2 ) time; so the total worst-case time is O(n 2d 3 ). Although this is substantially more expensive than forward checking, the extra cost is usually worthwhile.1 Because CSPs include 3SAT as a special case, we do not expect to find a polynomialtime algorithm that can decide whether a given CSP is consistent. Hence, we deduce that arc consistency does not reveal every possible inconsistency. For example, in Figure 5.1, the partial assignment {WA = red, NSW = red} is inconsistent, but AC-3 will not find the incon- 1 The AC-4 algorithm, due to Mohr and Henderson (1986), runs in O(n 2 d 2 ). See Exercise 5.10
