Regarding Forward Checking and Arc Consistency

[Yunsong Meng <Yunsong.Meng@asu.edu>]

Since so many students asked questions about Forward Checking and Arc Consistency today, 
I think it is necessary to make sure everyone are on the same boat. Let me try to clarify, correct me if 
I am wrong:

Forward Checking: 
Keep a list of all possible values for each unassigned variables, every time before assigning a value to a variable, 
check whether that value is the only possible value for neighbor variables (Don't permanently delete that 
value from neighbor's possible value), if none of them is the case, make the assignment, and update the possible 
values for other variables (Now you can delete the value just assigned). And keep going. 

Arc Consistency:
Keep all possible values for unassigned variables, and propagate constraints to each of the variable. 
Remove any possible value that has no support from neighbors, and check all variables each round. 
End if no value was removed in one round. (For one round, I mean update all variables)? 


-- 
Meng,Yunsong
Teaching Assistant