Constraint satisfaction problem

A constraint satisfaction problem (CSP) is a special class of computational search problem. A CSP consists of three components, $\mathcal{V},\mathcal{D},\mathcal{C}$.

• $\mathcal{V}$ is a set of variables, $\{V_1,\cdots ,V_n\}$.
• $\mathcal{D}$ is a set of domains, $\{D_1,\cdots ,D_n\}$ for each variable $V_i$. This is a set of allowable values for the variable $V_i$. Different variables can have different domains of different sizes.
• $\mathcal{C}$ is a set of constraints $\{C_1,\cdots ,C_m\}$. Each constraint $C_j$ has a set of variables it operates over, called its scope. Given an assignment to the variables in the scope of a constraint, it would be evaluated to true if and only if the assignment satisfies the constraints.

We represent states as values assigned to feature vectors (features are a set of $k$ variables). A state is specified by an assignment of values to all variables. A partial state is specified by an assignment of a value to some of the variables. Then, a goal state (solution) is defined such that we have values for the variables (a state) that satisfies all specified constraints. A CSP is unsatisfiable if no solution exists.

In CSPs (compared to regular search problems), we’re not interested in how we get there (the path), just in the final solution configuration. We take advantage of a general (instead of problem-specific) state representation, that allows us to design more efficient algorithms.

The main idea is that we can eliminate large amounts of the search state by identifying variable/value combinations that violate the constraints.

Formulation

Constraints can be formulated in a few different ways.

• A unary constraint is over one variable, i.e., $C(Y):Y>5$.
• A binary constraint is over two variables, i.e., $C(X,Y):X+Y<6$.
• A higher-order constraint is over 3 or more variables.
  • All-diff constraints essentially require that all $k$ variables in the constraint’s scope must be different. Note that we can express this with $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ binary not-equal constraints.

For example, we can formulate Sudoku as a CSP:

• Variable: represents a cell, i.e., $V_{11},V_{12},\cdots$.
• Domain: a single value for cells already filled in; the set $\{1,\cdots ,9\}$ for empty cells.
• State: any completed board given by specifying the value in each cell.
• Partial state: some incomplete filling out of the board.
• Constraints: the values assigned to the variables that form a {column, row, sub-square} must be distinct. For a row constraint: $\text{All}-\text{Diff}(V_{11},V_{12},\cdots ,V_{19})$.

The problem formulation determines how feasible finding a solution is. There might be a drastic difference in the number of configurations we might have to solve, i.e., we could bake a constraint into the problem formulation.

As a search problem

We can also formulate a CSP as a search problem. The initial state is an empty assignment. The successor function are assigned values to an unassigned variable. And the goal test checks that the assignment is complete and no constraints are violated.

A CSP search tree has children of a node being all possible value assignments for a particular unassigned variable. The tree stops descending if an assignment violates a constraint.

Solutions

The general class of CSPs are NP-complete. This is essentially because they are the same as SAT problems (circuit-SAT, bool-sat, formula-SAT) and can be reduced from them.

For backtracking, its worst-case time complexity is exponential, $\mathcal{O}(d^n)$. We use constraint propagation techniques to solve these problems faster.