Constraint Propagation Example Graph Coloring R G. B *Different-color constraint Initial Domains Arc examined Value deleted none V,G) R G V2-V3 V,(R) Arcs to examine V2>V1 V>V Delete unmentioned tail values F An element of a variable 's domain is removed THEN add all arcs to that variable to the examination queue Constraint Propagation Example RG Graph coloring xgtDifferent-color constraint ( R,66 Arc examined value deleted V2(G) V,(R) Arcs to examine none V3>V1 none F examination queue is empty THEN arc(pairwise) consistent.29 Constraint Propagation Example R,G,B R, G G Different-color constraint V1 V2 V3 V3>V1 V2>V1 V1 V (R) 2-V1 V2 V (G) 2 -V3 V1 V (G) 1-V3 V1 – V2 none Arc examined Value deleted Graph Coloring Initial Domains B R G V2 V3 V1 Arcs to examine • Delete unmentioned tail values IF An element of a variable’s domain is removed, THEN add all arcs to that variable to the examination queue. 30 Constraint Propagation Example R,G,B R, G G Different-color constraint V1 V2 V3 V3>V1 none V2>V1 none V1 V (R) 2-V1 V2 V (G) 2 -V3 V1 V (G) 1-V3 V1 – V2 none Arc examined Value deleted Graph Coloring Initial Domains B R G V2 V3 V1 Arcs to examine IF examination queue is empty THEN arc (pairwise) consistent