Problem to be solved Given a set of n variables where the ith variable 1<=k<=n, has a discrete domain of values it can take, domain/i and a set of binary relations C 1nC21…C2n…Cnn, find the first consistent instantiation of these variables which satisfies all the relations Notation Current variable is indexed with 1, Vi Past variables will be variables that have already been instantiated (those whose index is <1) Future variables will be those yet to be instantiated (those whose index is >1) Why Binary CSPs Every higher order(multiple variables), finite domain constraint can be reduced to a set of binary constraints if enough auxillary variables are introducedProblem to be solved Given a set of n variables where the ith variable, 1<= i<=n, has a discrete domain of values it can take, domain[i], and a set of binary relations C = {C1,1 … C1,n C2,1 … C2,n … Cn,n}, find the first consistent instantiation of these variables which satisfies all the relations. Notation: Current variable is indexed with i, Vi Past variables will be variables that have already been instantiated (those whose index is <i ) Future variables will be those yet to be instantiated (those whose index is >i ) Why Binary CSP’s Every higher order (multiple variables) , finite domain constraint can be reduced to a set of binary constraints if enough auxillary variables are introduced