Constraint Satisfaction
Constraint Satisfaction is a method that attempt to solve problems by assigning values (that are part of the Domain) to variables which must satisfy certain constraints to create an acceptable solution. An example of a problem that could be solved with constraint satisfaction is soduku. In soduku each cell is a variable, the domain (acceptable values that can be assigned) is the set of numbers 1 to 9 and the constraints are all variables in a single row/column/3 × 3 square are different.
Terminology
If an assignment of variables does not violate the constraints of the problem, it is known as consistent. If all variables are assigned a value from the domain, it is known as complete. If an assignment is complete and consistent, then it is a solution. Partial asignments are those that only some variables have values. Partial solutions are partial assignments that are consistent.
Variables in CSP can be discrete (finite or infinite) or continuous. Constraints can be unary (involving only one variable e.g. x ≠ 2), binary (involving 2 variables e.g. x < y) or global (involving an arbitrary number of variables e.g. all variables cannot equal another variable). Constraints can also be hard (must not be broken e.g. two events occuring at the same time cannot have the same priority) or soft (preferable but can be broken e.g. try to schedule lessons in the afternoon rather than in the morning).
Solving Constraint Satisfaction Problems
CSP can be formulated as a constraint graph (where nodes are variables and arcs are the constraints). This allows CSP to be solved as a state-space search problem. However, CSP may solve problems with many nodes much quicker than regular search algorithms and all heuristics for CSP are domain independant (as opposed for things like A* Search). However, solving CSP by just satisfying constraints may also not be very good, especially for more complex problems. Therefore, a 3rd way that combines the two is wanted - backtracking search.
Backtracking Search
Backtracking search is a type of depth first search that is used for CSP. It differs from DFS by changing only one variable at a time and by checking the constraints are satisfied at every level (i.e. do not consider impossible states).
Improving Backtracking Search
Forward Checking
When a variable is assigned, remove inconsistant options from the domains of remaing variables (filtering). When the domain of a variable is empty, you know that this attempt will not yield a solution, so you must backtrack. This allows bracktracking to occur earlier and thus saves time.
This can be improved even further with constraint propogation aka arc consistency (this assumes there are only binary constraints). A variable X is called arc-consistent with respect to variable Y if for every value x there exists some value y such that a pair (x,y) does not violate any constraint. Arc consistency is directional (so X may be arc consistent with Y but not the other way around). By enforcing arc consistency with all variables, forward checking can be vastly improved.
Ordering
By choosing which variables to assign first, we can increase the efficiency of backtracking search. We may order by variables or by values. There are 2 ways of ordering by variables, 1 way is to choose the variable with the fewest legal values left (aka minimum remaing values or fail-first). The other way of ordering by variables is called degree heuristic and involves choosing the variable which is involved in the most number of constraints (i.e. the node with the most direct connections). In order to order by value, you would use the least-constraining value heuristic. This means that the value that is chosen should be one that results in the least effect on the other unassigned variables (i.e. dont pick a value that eliminates all possible options for another variable). This however requires computation to use as it involves filtering.
Local Search
Many CSP can be solved with Local Search as well using the minimum conflicts heuristic. Essentially, all variables are assigned a value (assignment is complete) and while this assignment is not consistent, random conflicting variables are changed to become less conflicting until a solution is reached.