# Constraint Satisfaction Problem (CSP)

### A mathematical question that is defined by variables, domains, and constraints

Constraint Satisfaction Problem (CSP) is a class of problems that can be used to represent a large set of real-world problems. In particular, it is widely used in Artificial Intelligent (AI) as finding a solution for a formulated CSP may be used in decision making. There are a few adjacent areas in terms that for solving problems they all involve *constraints*: SAT (Boolean satisfiability problem), and the SMT (satisfiability modulo theories).

Generally speaking, the complexity of finding a solution for CSP is NP-Complete (takes exponential time), because a solution can be guessed and *verified* relatively fast (in polynomial time), and the SAT problem (NP-Hard) can be translated into a CSP problem. But, it also means, there is no known polynomial-time *solution*. Thus, the development of efficient algorithms and techniques for solving CSPs is crucial and appears as a subject in many scientific pieces of research.

The simplest kind of CSPs are defined by a set of *discrete variables* (e.g. X, Y), *finite non-empty domains* (e.g. 0<X<=4, Y<10), and a set of *constraints* (e.g. Y=X^2, X<>3) which involve some of the variables. There are distinguished two related terms: the *Possible World* (or the *Complete Assignment*) of a CSP is an assignment of values to all variables and the *Model* (or the *Solution* to a CSP) is a possible world that satisfies all the constraints.

Within the topic, there is a programming paradigm - Constraint Programming. It allows building a Constraint Based System where relations between variables are stated in a form of constraints. Hence, this defines certain specifics:

- the paradigm doesn't specify a sequence of steps to execute for finding a solution, but rather declares the solution's properties and desired result. This makes the paradigm a sort of
*Declarative Programming* - it's usually characterized by non-directional computation when to satisfy constraints, computations are propagated throughout a system accordingly to changed conditions or variables' values.

The example of using this paradigm can be seen in another my article "A converter of a character's case and Ascii codes".

A CSP can be effectively applied in a number of areas like mappings, assignments, planning and scheduling, games (e.g. sudoku), solving system of equations, etc. There are also a number of software frameworks which provide CSP solvers, like python-constraint and Google OR-Tools, just to name a few.

Share on Twitter