Constraint programming is one of the most successful practical applications of Artificial Intelligence. Constraint programming (CP) has successfully been applied to many real-world problems since these problems can easily be modelled in terms of constraints, such as: scheduling, planning, configuration, layout, resource allocation, and decision support. Other areas where CP is used are: Concurrent computing, database systems, graphical interfaces, hardware verification, operations research and combinatorial optimisation. In the eighties, constraint logic programming appeared; the first general-purpose computational framework based on combining constraints and logic programming.

 

Constraint Satisfaction techniques attempt to find solutions to constraint satisfaction problems (CSPs). There are a number of efficient toolkits and languages available especially designed to handle these problems. The definition of a Constraint Satisfaction Problem (CSP) is: 

• A set of variables X={X1,..., Xn},
• For each variable Xi, a finite set Di of possible values (its domain), and
• A set of constraints C<j> Í Dj1 × Dj2 × …× Djt, restricting the values that subsets of the variables can take simultaneously.

A solution to a CSP is the assignment of a value from its domain to every variable, in such a way that all constraints are satisfied. The main CSP solution technique interleaves consistency enforcement, in which unfeasible values are removed from the problem through reasoning about the constraints, and various forms of backtracking search.