Basic Definitions

A Constraint Satisfaction Problem (CSP), $P$, is defined as a tuple $(X,D,C)$, where:

• $X=\{x_1,\ldots,x_n\}$ is a finite set of $n$ variables.
• $D=\{D_{in}(x_1),\ldots,D_{in}(x_n)\}$ is a set of initial domains. For each variable $x_i\in X$, $D_{in}(x_i)$ is the initial finite domain of its possible values. CSP algorithms remove values from the domains of variables through value assignments and propagation. For any variable $x_i$, we denote by $D(x_i)$ the current domain of $x_i$ that at any time consists of values that have not been removed from $D_{in}(x_i)$. We assume that for every $x_i\in X$, a total ordering $<_d$ can be defined on $D_{in}(x_i)$.

• $C=\{c_1,\ldots,c_e\}$ is a set of $e$ constraints. Each constraint $c_i\in C$ is defined as a pair $(vars(c_i),rel(c_i))$, where 1) $vars(c_i)=\{x_{j_1},\ldots,x_{j_k}\}$ is an ordered subset of $X$ called the constraint scheme, 2) $rel(c_i)$ is a subset of the Cartesian product $D_{in}(x_{j_1})\textrm{x}\ldots\textrm{x}D_{in}(x_{j_k})$ that specifies the allowed combinations of values for the variables in $vars(c_i)$.

The size of $vars(c_i)$ is called the arity of the constraint $c_i$. Constraints of arity 2 are called binary. Constraints of arity greater than 2 are called non-binary (or n-ary). Each tuple $\tau\in rel(c_i)$ is an ordered list of values $(a_{1},\ldots,a_{k})$ such that $a_j\in D_{in}(x_j)$,$j=1,\ldots,k$. A tuple $\tau$ = $(a_{1},\ldots,a_{k})$ is valid if $\forall\ a_j , j \in\ 1,\ldots ,k$, $a_j\in D(x_j)$. That is, a tuple is valid if all the values in the tuple are present in the domains of the corresponding variables. The process which verifies whether a given tuple is allowed by a constraint $c_i$ or not is called a consistency check. A constraint can be either defined extensionally by the set of allowed (or disallowed) tuples or intensionally by a predicate or arithmetic function. A binary CSP can be represented by a graph (called constraint graph) where nodes correspond to variables and edges correspond to constraints. A non-binary CSP can be represented by a constraint hyper-graph where the constraints correspond to hyper-edges connecting two or more nodes.

The assignment of value $a$ to variable $x_i$ will be denoted by $(x_i,a)$. Any tuple $\tau=(a_1,\ldots,a_{k})$ can be viewed as a set of value to variable assignments $\{(x_1,a_1),\ldots,(x_{k},a_{k})\}$. The set of variables over which a tuple $\tau$ is defined will be denoted by $vars(\tau)$. For any subset $vars'$ of $vars(\tau)$, $\tau[vars']$ denotes the sub-tuple of $\tau$ that includes only assignments to the variables in $vars'$. Any two tuples $\tau$ and $\tau'$ of $rel(c_i)$ can be ordered by the lexicographic ordering $<_{lex}$. In this ordering, $\tau <_{lex} \tau'$ iff there a exists a subset $\{x_{1},\ldots, x_{j}\}$ of $c_i$ such that $\tau[x_{1},\ldots, x_{j}]=\tau'[x_{1},\ldots, x_{j}]$ and $\tau[x_{j+1}]<_{lex}\tau'[x_{j+1}]$. An assignment $\tau$ is consistent, if for all constraints $c_i$, where $vars(c_i)\subseteq vars(\tau)$, $\tau[vars(c_i)]\in rel(c_i)$. A solution to a CSP $(X,D,C)$ is a consistent assignment to all variables in $X$. 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 $n$ for the number of variables in a CSP, $e$ for the number of constraints in the problem, $d$ for the maximum domain size of the variables, and $k$ for the maximum arity of the constraints.