3.1. Constraint Satisfaction Problems

Constraint Satisfaction Problem

Constraint Satisfaction Problems (CSPs) are a class of identification problems where the task is to assign values to variables that satisfy a set of constraints. Unlike search algorithms, CSPs care only about whether an assignment meets all constraints, not the sequence of steps to reach it.

CSPs are formally defined by:

• Variables $X_1,\dots ,X_N$, each with a domain of possible values.
• A domain $\{x_1,\dots ,x_d\}$ specifying allowable values.
• Constraints restricting variable combinations.

There are $O(d^N)$ combinations that could be assigned to the variables.

CSPs are NP-hard, meaning no known polynomial-time algorithm guarantees solutions. To make solving feasible, CSPs are often reformulated as search problems, traditionally as an optimization on DFS known as backtracking search with the following optimizations:

• States are a snapshot of the current assignments. Some variables already have values, others don’t yet.
• The successor function is the “next move”: pick one more variable and give it a value.
• The goal test checks if every variable has a value and all constraints are satisfied.

Examples

N-Queens

Consider the $N$-queens identification problem: given an $N\times N$ chessboard, can we find a configuration in which to place $N$ queens on the board such that no two queens attack each another?

We can formulate this problem as a CSP as follows:

1. The variables are the grid positions $X_{ij}$ on the $N\times N$ chess board.
2. The domain is $\{0,1\}$, such that each $X_{ij}$ is a boolean value representing whether there is a queen at position $(i,j)$.
3. The constraints are as follows:

• $\forall i,j,k[(X_{ij},X_{ik})\in \{(0,0),(0,1),(1,0)\}]\wedge [(X_{ij},X_{kj})\in \{(0,0),(0,1),(1,0)\}]$, stating that no two queens can be on the same row or column.
• $\forall i,j,k[(X_{ij},X_{i+k,j+k})\in \{(0,0),(0,1),(1,0)\}]\wedge [(X_{ij},X_{i+k,j-k})\in \{(0,0),(0,1),(1,0)\}]$, stating that no two queens can be on the same diagonal.
• A constraint ensuring that there are exactly $N$ positions marked with $1$, such that ${\sum }_{i,j}^{}{X}_{ij}=N$.