# Constraints Satisfaction Problem (CSP) Some problems could be classified as CSP when we can define these elements: - A set of variables $X_1 ... X_n$ - For each variable $X_i$ we associate a domain $X_i$ = set of values that $X_i$ can assume - The set of constraints $C_1 ... C_n$ which specifies allowable combinations of values. The constaints can be: - unary (they involve only one variable), - binary (they involve two variables) - n-nary It's proved that any n-nary constraint can be turned into a set of binary constraints. #### Constraint propagation. We use constraints in order to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable, and so on. - 1-consistency (node-consistency): that is based basically on the domains of variables. - 2-consistency (**Arc-consistency**): the one we will check using the **AC-3** algorithm. $X_i \rightarrow X_j$ is arc consistency if for each value of $X_i$ exists a value in $X_j$ . - Path-consistency: extension of the previous to more variables AC-3 arc consistency algorithm that can be applied only to all CSPs formulated with binary constraints. The algorithm is very intuitive and simple. ## CSP as Search Problem An important behavour of the CSPs is that they are commutative! This reduces a lot the branching factor on our trees when we try to perform a search tree to solve this kind of problems. With this consideration with ended up we can perform a depth search tree giving possible values from the domain to the variables. Also we could perform the DFS with some variants: - **Backtracking** - **Forward Checking**: using **AC-3** each time a variable is assigned. For each variable not assigned that involves X (which is just assigned) is checked the **arc-consistency**. - **MRV (Minimum Remaing Values)**: When we try to assign a value to a variable we follow a policy to choose which variables assign and not just take a random one. So we choose the variable with minimum 'legal' values in the domain. - **LCV (Least Constraints Value)** : the MRV policy interest the variable choosen for the next assigment. The LCV policy tells us which value assign to the variable: we choose the value that is involved in the less numbe of constraints with other values.