Constraint Satisfaction Problem (CSP)

on 2019-07-22 in note about cs programming ai ~2 min read

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