\chapter{Constraints satisfaction}

\begin{description}
    \item[Constraints satisfaction problem (CSP)] \marginnote{Constraints satisfaction problem (CSP)}
        Problem defined on a finite set of variables\\$(X_1, \dots, X_n)$,
        each belonging to a domain $(D_1, \dots, D_n)$ 
        (notation: $X_i :: [d_{i,1}, \dots, d_{i,m}]$ or $X_i \in [d_{i,1}, \dots, d_{i,m}]$).

        A constraint is a relationship between variables (e.g. $X < Y$). 
        Formally, a constraint $c(X_{k_1}, \dots, X_{k_m})$ is a subset of the cartesian product
        $D_{k_1} \times \dots \times D_{k_m}$ of the admissible values of the variables.

        A solution to a CSP is an admissible assignment of all the variables.

        CSP can be solved as a search problem.
        \begin{descriptionlist}
            \item[A posteriori algorithms] \marginnote{A posteriori algorithms}
                Constraints are checked after the construction of the search tree.
        
            \item[Propagation algorithms] \marginnote{Propagation algorithms}
                Once a variable has been assigned, 
                constraints are propagated to the unassigned variables to prune part of the search space.
        
            \item[Consistency techniques] \marginnote{Consistency techniques}
                Constraints are propagated to derive a simpler problem.
        \end{descriptionlist}
\end{description}



\section{A posteriori algorithms}

\subsection{Generate and test}
\marginnote{Generate and test}

The search tree is constructed depth-first. 
At level $i$, a value is assigned to the variable $X_i$.
Constraints are only checked when a leaf has been reached.

In other words, it computes all the permutations of the values of the variables.


\subsection{Standard backtracking}
\marginnote{Standard backtracking}

The search tree is constructed depth-first. 
At level $i$, a value is assigned to the variable $X_i$ and 
constraints involving $X_1, \dots, X_i$ are checked.
In case of failure, the path is not further explored.

A problem of this approach is that it requires to backtrack in case of failure
and reassign all the variables in the worst case.



\section{Propagation algorithms}

\subsection{Forward checking}
\marginnote{Forward checking}

The search tree is constructed depth-first. 
At level $i$, a value is assigned to the variable $X_i$ and 
constraints involving $X_i$ are propagated
to restrict the domain of the remaining unassigned variables.
If the domain of a variable becomes empty, the path is considered a failure and the algorithm backtracks.