2. General Definitions

arc consistency

The domains of a variable Vi is such that for each constraint Ci,j Vi is consistent with the constraint for some permissible value of Vj for every value in the domain of Vi That is for every value x in Di (the domain of i) there exists some y in Dj such that Ci,j is satisfied. It is important to note that arc consistency is directional (that is (Vi, Vj) being arc consistent does not mean (Vj, Vi) 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 { V1, V2, ... , Vn }, each having a domain Di such that Vi takes on a value from Di, does not conflict with a set of binary constraints { C1,1, C1,2, ..., C1,n, ..., C2,1, C2,2, ..., C2,n, ..., Cn,1, Cn,2, ..., Cn,n } where Ci,j is a constraint (relation) between Vi and Vj that must be true, and if Ci,j is null there is no constraint between Vi and Vj.


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]