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 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 x of SA, there is some value y of NSW that is consis￾tent 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-