**arc consistency**The domains of a variable V

_{i}is such that for each constraint C_{i,j}V_{i}is consistent with the constraint for some permissible value of V_{j}for every value in the domain of V_{i}That is for every value*x*in D_{i}(the domain of*i*) there exists some*y*in D_{j}such that C_{i,j}is satisfied. It is important to note that arc consistency is directional (that is (V_{i}, V_{j}) being arc consistent does not mean (V_{j}, V_{i}) is arc consistent).**binary constraint satisfaction problem**The binary constraint satisfaction problem, as used in this paper, involves finding a solution such that a set of variables { V

_{1}, V_{2}, ... , V_{n}}, each having a domain D_{i}such that V_{i}takes on a value from D_{i}, does not conflict with a set of binary constraints { C_{1,1}, C_{1,2}, ..., C_{1,n}, ..., C_{2,1}, C_{2,2}, ..., C_{2,n}, ..., C_{n,1}, C_{n,2}, ..., C_{n,n}} where C_{i,j}is a constraint (relation) between V_{i}and V_{j}that must be true, and if C_{i,j}is null there is no constraint between V_{i}and V_{j}.**K–consistent**Choose any K – 1 variables that satisfy the constraints among those variables. Then choose any Kth variable. If there exists a value for this variable that satisfies all the constraints among these K variables then the constraint problem can be said to be K consistent. Paraphrased from [Kumar92]

**Strongly K–consistent**A constraint problem is strongly K-consistent if it is J–consistent for all J ≤ K. [Kumar92]