# Constraint Satisfaction

Constraint satisfaction is a general framework for expressing many
computational problems including scheduling, graph colouring, and
vision processing. A Constraint Satisfaction Problem (CSP) consists of a
domain, a number of variables and a number of constraints restricting
combinations of values of the variables . A solution of a CSP is an
assignment of a domain value to
each variable which satisfies all the constraints simultaneously.
A constraint problem can
have many mutually conflicting constraints. For example suppose we
have:
- the finite domain
*{1,2,3,4,5,6}*;
- three variables
*x,y,z*;

and two constraints expressing that the sum of *x,y* must be 6
and that the product or *y,z* must be at least 20. There are only 5
solutions which satisfy both constraints:
- x=1 , y=5 , z=4
- x=1 , y=5 , z=5
- x=1 , y=5 , z=6
- x=2 , y=4 , z=5
- x=2 , y=4 , z=6

One technique for solving constraint problems is to iterate through
each possible solution checking if it satisfies each constraint. Such
a solution technique has the disadvantage that the number of possible
solutions grow exponentially with the number of variables.
Some constraint problems are inherently easy to solve. For example if
each variable in the constraint is only constrained by at most two
constraints and there are no cyclic dependencies, then the problem is
easy to solve. The solution can be found by identifying a root node
and assigning values in a backtrack free manner.

My current research in constraint satisfaction is in identifying
algebraic conditions on constraint problems that make them easy to
solve. Earlier work was done at Royal Hollow College where using
techniques from universal algebra and database theory many tractable
classes where identified. A summary can be found .
Currently I am working on understanding the role of symmetry in
solving CSPs.

Justin Pearson