Constraint Satisfaction is a search procedure that operates in a space of constraint sets. The initial state contains the constraints that are originally given in the problem description.
A goal state is any state that has been constrained “enough” were “enough” must be defined for each problem.
For example, in cryptarithmetic problems, enough means that each letter has been assigned a unique numeric value.
Constraint Satisfaction problems in AI have goal of discovering some problem state that satisfies a given set of constraints.
Design tasks can be viewed as constraint satisfaction problems in which a design must be created within fixed limits on time, cost, and materials.
Constraint Satisfaction is a two-step process:
- First constraints are discovered and propagated as far as possible throughout the system.
- Then if there is still not a solution, search begins. A guess about something is made and added as a new constraint.
Example: Cryptarithmetic Problem
Constraints:
- No two letters have the same value
- The sums of the digits must be as shown in the problem
Goal State:
- All letters have been assigned a digit in such a way that all the initial constraints are satisfied.
Input State
The solution process proceeds in cycles. At each cycle, two significant things are done:
- Constraints are propagated by using rules that correspond to the properties of arithmetic.
- A value is guessed for some letter whose value is not yet determined.
Solution:
Algorithm: Constraint Satisfaction
Propagate available constraints. To do this first set OPEN to set of all objects that must have values assigned to them in a complete solution. Then do until an inconsistency is detected or until OPEN is empty:
- Select an object OB from OPEN. Strengthen as much as possible the set of constraints that apply to OB.
- If this set is different from the set that was assigned the last time OB was examined or if this is the first time OB has been examined, then add to OPEN all objects that share any constraints with OB.
- Remove OB from OPEN.
If the union of the constraints discovered above defines a solution, then quit and report the solution.
If the union of the constraints discovered above defines a contradiction, then return the failure.
If neither of the above occurs, then it is necessary to make a guess at something in order to proceed. To do this loop until a solution is found or all possible solutions have been eliminated:
- Select an object whose value is not yet determined and select a way of strengthening the constraints on that object.
- Recursively invoke constraint satisfaction with the current set of constraints augmented by strengthening constraint just selected.
