Given a set $\mathcal{C}$ of constraints, find a state $X = \{X_1 =x_1, \dots, X_n = x_n\} \in S$, $x_i \in \mathcal{D}_i$, that satisfies $\mathcal{C}$.
Note. Constraint satisfaction problems are a subset of search problems where states are explicitly defined in terms of a list of variables and the goal test is parameterized by $\mathcal{C}$.
An assignment is a set of variable-value pairs denoting which value each variable has been assigned; it is a complete assignment when all variables have been assigned. A constraint is $n$-ary if it relates $n$ variables.
Binary Constraint Graph. Nodes are adjacent if the variables they correspond to are related under a constraint.
CSPs are typically formulated as search problems in the following way.
Initial State $x_0$. This is the state with no assignments to any of its variables.
Transition Model $t : S \times A\rightarrow S$. Assign a value to an unassigned variable.
Goal Test $g : S \rightarrow \{0, 1\}$. Return $1$ if the assignment is complete and satisfies $\mathcal{C}$.
A consequence of this formulation is that all solutions are at the same level in the search tree.
Uninformed search algorithm used for solving CSPs. It is defined in the following way.
Backtracking Search (**problem**, **partial assignment**) -> **complete assignment** or **failure**:
if **partial assignment** is complete:
return **partial assignment**
**variable** <- select_var(**problem**.variables, **partial assignment**, **problem**)
for each **value** in order_values(**variable**.domain, **partial assignment, problem)**:
if **value** is consistent with **problem**.constraints:
insert (**variable, value**) into **partial assignment
result** <- Backtracking Search (**problem**, **partial assignment**)
if **result** != **failure**:
return **result**
else:
remove (**variable, value**) from **partial assignment**
return **failure**