In CSPs, states are defined by the values assigned so far (partial assignments)
-
Initial state : the empty assignment {}.
-
Successor function : assign a value to an unassigned variable.
-
Goal : the current assignment is complete and satisfies all the constraints.
-
Solving CSPS by BFS is not a a good idea since the solutions are always present in the bottom layer, BFS needs to traverse all nodes (partial assignments).
-
Solving CSPs by Backtracking involves checking constraints as you go and considering one variable at a time.
Improving Backtracking
General-purpose ideas give huge gain in speed. Two ideas :
- Filtering : Can we detect inevitable failure early.
- Ordering : Which variable should be assigned next.
Filtering
-
Keep track of domains for unassigned variables and cross off bad options. There are different filtering methods. Forward Checking is one of them.
-
Forward Checking : cross off values of neighbouring variables that violet a constraint when added to the existing assignment. That is, when assign a variable, cross off anything that is now violated on all its neighbours’ domain. Example : Example: There are three variables A, B, and C, all with domain . The constraint is B>A>C. Tie is broken alphabetically and numerically.
When A is assigned 0, domains of its neighbours B and C are reduced, so it is quick to know this assignment is not legal (as C is empty now).
Ordering
-
Consider the variable with minimum number or remaining values to explore i.e., choose the variable with the fewest legal value left in its domain.
-
Example : Example: There are three variables A, B and C, all with domain . The constraint is . Tie is broken alphabetically and numerically.
-
Once A is assigned 0, after forward checking C will be assigned since its domain is smaller than B’s domain.
-
Also called “most constrained variable” or “fail fast” ordering.
Example Backtracking + Forward Checking + Ordering
Example :Example: There are three variables A, B, C, all with domain .. The constraints: and . Tie is broken alphabetically and numerically . Use backtracking, forward checking and ordering to solve the problem.
