Constraint Satisfaction

• The general problem is to find a solution that satisfies a set of constraints.
• heuristics used not to estimate the distance to the goal but to decide what node to expand nest.
• Examples of this technique are design problem, labelling graphs, robot path planning and cryptarithmetic puzzles (see last year).

Algorithm:

1. Propagate available constraints:
   • Open all objects that must be assigned values in a complete solution.
   • Repeat until inconsistency or all objects assigned valid valid values:
     • select an object and strengthen as much as possible the set of constraints that apply to object.
     • If set of constraints different from previous set then open all objects that share any of these constraints.
     • remove selected object.
2. If union of constraints discovered above defines a solution return solution.
3. If union of constraints discovered above defines a contradiction return failure

1. Make a guess in order to proceed. Repeat until a solution is found or all possible solutions exhausted:
   • select an object with a no assigned value and try to strengthen its constraints.
   • recursively invoke constraint satisfaction with the current set of constraints plus the selected strengthening constraint.

For further detail and examples on Constraint Satisfaction see (Last year's AI1 notes Lecture 13).