## Basic Definitions

A Constraint Satisfaction Problem (CSP), , is defined as a tuple , where:

• is a finite set of variables.
• is a set of initial domains. For each variable , 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 , we denote by the current domain of that at any time consists of values that have not been removed from . We assume that for every , a total ordering can be defined on .

• is a set of constraints. Each constraint is defined as a pair , where 1) is an ordered subset of called the constraint scheme, 2) is a subset of the Cartesian product that specifies the allowed combinations of values for the variables in .
The size of is called the arity of the constraint . Constraints of arity 2 are called binary. Constraints of arity greater than 2 are called non-binary (or n-ary). Each tuple is an ordered list of values such that ,. A tuple = is valid if , . 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 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 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.

Subsections
Nikolaos Samaras 2005-11-09