(computer science) A Constraint Satisfaction Problem (CSP) is defined as:
A solution to a CSP is an assignment of values to all the variables, such that:
- Each variable is assigned a value from its domain.
- All the constraints are satisfied.
CSP is studied as a field of artificial intelligence. CSP formalism and solution techniques are used in various domains (no pun intended), such as machine vision, scheduling, temporal reasoning, and test-case generation for hardware verification.
The n-queens problem is a classic example for a CSP: given a chessboard of size NxN, place N queens on the board such that none of them can hit any other in one move. This problem can be formulated as a CSP in various ways. In one of them, a variable V(i,j) is defined for each cell of the board. The domains of all these variables is {true, false}: true if a queen is present at cell (i,j), and false otherwise. The constraints forbid two queens from being on the row, column, or diagonal.