Constraint Satisfaction Problem (CSP)

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.