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, 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*. Hence, 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 Bases System where relations between variables are stated in a form of constraints. Hence, this defines certain specifics:

- the paradigm doesn't tell a certain sequence of steps to execute to find a solution, but rather declares the solution's properties.
- it's usually characterized by non-directional computation when to satisfy constraints, computations are propagated through a system accordingly to changed conditions or variables' values.

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

## Top comments (0)