Constraint Satisfaction Problem are special type of search in which, a state is defined by variables X with values from the domain D and goal test is a set of constraints specifying allowable combinations of values for subsets of variables.

Many real problems in AI can be modeled as Constraint Satisfaction Problems. CSP allows useful general purpose algorithms with more power than standard search algorithms. CSP are solved through search.

Example:

Eight Queens Problem: How one can put 8 queens on a (8×8) chess board such that no queen can attack any other queen?

Solution: The puzzle has 92 distinct solutions. If rotations and reflections of the board are counted as one, the puzzle has 12 unique solutions.

Real -World CSPs:

1. Assignment problems: e.g. who teaches what class?

2. Timetabling problems: e.g. which class is offered when and where

Varieties of CSPs:

1. Continuous variables: e.g. start/end times for Hubble Space Telescope observations

2. Linear constraints solvable in polynomial time by linear programming.

Variables of constraints:

1. Unary constraints involve single variable.

E.g. SAgreen

Backtracking in CSP:

1. Initial state: The empty assignment

2. Successor function: Assign a value to an unassigned variable that doesn’t conflict with current assignment; fail if no legal assignment.

3. Goal test: The current assignment is complete.

Improving Backtracking Efficiency:

Most constrained variable:

It choose the variable with fewest legal values. By assigning this variable first, we can get a fair idea of other assignment variables.

Most constraining variable:

This is tie breaker among most constrained variables. In most constraining variable strategy we first choose the variable with the most constraints on remaining variables.

Least constraining value:

Chose the value that rules out the fewest values for the remaining variables.

Forward checking:

It keeps track of reaming legal values for unassigned variables. Terminates search when any variable has no legal values.