Forward Checking and ARC Consistency.. Now for Rao's version

[Subbarao Kambhampati <rao@asu.edu>]

Looks like the confusions are begetting more confusions in the FC/AC discussion. Let me stop the buck...

Terminology: If you have n variables x1...xn; and if you have assigned x1,x2...xi-1; and are about to assign xi, 
then current variable: xi? ; past variables: x1...xi-1? ; future variables xi+1....xn

Forward checking: 

The idea: For each *future* variable, remove from its domain any values that are conflicting with the assignments you have done? until now (i.e., past variables and current variable).

In the special case of binary CSPs, notice that the only way a value can be deleted from the domain of the future variable is if it conflicts with the assignments made to the current variable. 

In the case of n-ary CSPs, it is possible that the current variable's assignment along with some of the past variable assignments will rule out a value from the future variable's domain.
(e.g. suppose we have a constraint? x1=a& x4=b => x9 !=c ; so if x1 is a past variable and was assigned a; and x4 is the current variable and got assigned b, we can remove c from the domain of x9)


ARC Consistnency:


?The idea: Make sure that for every variable, xi; and every other variable xj (different from xi), for every value that
? xi can take, there is a value that xj can take without conflicting with xi. 
?
So, if you find that when xi takes a, xj cannot take *any value*, then you *remove* a from the domain of xi. In this sense of? "pruning values from domains" ARC Consistency is similar to Forward checking.

?However, unlike FC, which is with respect to a given search branch--with past, current and future variables, Arc Consistency is a *preproessing technique* and does not differentiate between past/current/future variables)


It is easy to see that if you have a binary CSP and you already ensured ARC consistency on it, then doing Forward checking will not remove any more values--no matter in what order you wind up assigning variables. 


hope this helps
Rao


ps: So is sudoku a binary CSP or not?

-----------------

? "My student came to me with a desire to know the time, and 
??? I taught her how to make a watch" 
?
??????????????????????????????? -Chris in the morning (Northern Exposure)