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 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! · 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 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 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