Solving CsPs Solving CSPs involves some combination of 1. Constraint propagation eliminates values that cant be part of any solution 2. Search explores valid assignments Arc Consistency Arc consistency eliminates values of each variable domain that can never satisfy a particular constraint (an arc {1,2, {1,2} Directed arc(V, V is arc consistent if For every x in D, there exists some y in D, such that assignment (x,y)is allowed by constraint Ci Or WXEDi EyeD, such that(x,y)is allowed by constraint Ci Where · Y denotes“ for al ·彐 denotes“ there exists ·∈ denotes“in3 Solving CSPs Solving CSPs involves some combination of: 1. Constraint propagation • eliminates values that can’t be part of any solution 2. Search • explores valid assignments 4 Arc Consistency • Directed arc (Vi , Vj ) is arc consistent if • For every x in Di , there exists some y in Dj such that assignment (x,y) is allowed by constraint Cij • Or ∀x∈Di ∃y∈Dj such that (x,y) is allowed by constraint Cij where • ∀ denotes “for all” • ∃ denotes “there exists” • ∈ denotes “in” Arc consistency eliminates values of each variable domain that can never satisfy a particular constraint (an arc). Vi Vj {1,2,3} {1,2} =