Constraint Satisfaction Problem in Artificial Intelligence

A Constraint Satisfaction Problem (CSP) is a program that requires its solution within some limitations or conditions that is called Constraints. It consists of:

1. A finite set of variables which store the solution V={V1,V2,V3,…,Vn}
2. A set of discrete values known as Domain Form which the solution is picked. D={D1,D2,D3,…,Dn}
3. A finite set of constraints C={C1,C2,C3,…,Cn}

Constraint Satisfaction

1. Until a complete solution is found or until all path has led to dead ends, do:

(i) Select an unexpected node of the search graph.
(ii) Apply the constraints inference rules to the selected node to generate all possible new constraints.
(iii) If the set of constraints contains a contradiction then report that this path is a dead-end.
(iv) If the set of constraints describes a complete solution then report success.
(v) If neither a contradiction nor a complete solution has been found then apply the problem space rules to generate new partial solutions that are consistent with the current set of constraints. Insert these partial solutions into the search graph.