A Constraint Satisfaction Problem (CSP), , is defined as a tuple , where:
The assignment of value to variable will be denoted by . Any tuple can be viewed as a set of value to variable assignments . The set of variables over which a tuple is defined will be denoted by . For any subset of , denotes the sub-tuple of that includes only assignments to the variables in . Any two tuples and of can be ordered by the lexicographic ordering . In this ordering, iff there a exists a subset of such that and . An assignment is consistent, if for all constraints , where , . A solution to a CSP is a consistent assignment to all variables in . If there exists a solution for a given CSP, we say that the CSP is soluble. Otherwise, it is insoluble.
A basic way of solving CSPs is by using backtracking search. This can be seen as a traversal of a search tree which comprises of the possible assignments of values to variables. Each level of the tree corresponds to a variable. A node in the search tree corresponds to a tuple (i.e. an assignment of values to variables). The root of the tree corresponds to the empty tuple, the first level nodes correspond to 1-tuples (an assignment of a value to one variable), the second level nodes correspond to 2-tuples (assignment of values to two variables generated by extending the first level 1-tuples) etc. At each stage of the search tree traversal, the variables that have been already assigned are called past variables. The most recently assigned variable is called current variable. The variables that have not been assigned yet are called future variables.
In the rest of this paper we will use the notation for the number of variables in a CSP, for the number of constraints in the problem, for the maximum domain size of the variables, and for the maximum arity of the constraints.