display | more...

(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.

Log in or register to write something here or to contact authors.