Combine Backtracking Limited Constraint Propagation Initially: Prune domains using constraint propagation If complete consistent assignment, then return Choose unassigned variable Choose assignment from pruned domain Prune domains using constraint propagation if a domain has no remaining elements, then backtrack Question: Full propagation is O(ed3) How much propagation should we do? Very little Just check arc consistency for those arcs terminating on the new assignment o(ed) called forward checking(FC) Backtracking with Forward Checking (BT-FC) 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment V, assignments R, G 1. Perform initial pruning13 Combine Backtracking & Limited Constraint Propagation Initially: Prune domains using constraint propagation Loop: • If complete consistent assignment, then return. • Choose unassigned variable • Choose assignment from pruned domain • Prune domains using constraint propagation • if a domain has no remaining elements, then backtrack. Question: Full propagation is O(ed3), How much propagation should we do? Very little: •Just check arc consistency for those arcs terminating on the new assignment O(ed). • called forward checking (FC). 14 Backtracking with Forward Checking (BT-FC) R, G R, G R, G, B V1 V3 V2 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment. R V1 assignments V2 assignments V3 assignments 1. Perform initial pruning