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.

This is my personal blog. All ideas, opinions, examples, and other information that can be found here are my own and belong entirely to me. This is the result of my personal efforts and activities at my free time. It doesn't relate to any professional work I've done and doesn't have correlations with any companies I worked for, I'm currently working, or will work in the future.