Backtracking

• Order matters since variable assignments are cumulative → better branching factor
• Check constraints as you go

Forward Checking

• cross off values that violate a constraint when added to existing assignment

Filtering

• Keep track of domains for unassigned variables and cross off bad options

Arc Consistency

• An arc X → Y is consistent if for every x in the tail there is some y which does not violate constraints

For an Entire CSP:

• if X loses a value, all neighbors of X need to be checked
• detects failure earlier than forward checking, WHY? Because if just one of X’s neighbors violates a constraint we can immediately rule failure

Properties

• can have one, multiple, or no solutions left
• Still runs inside a backtracking search
• If after a run of arc consistency during the backtracking search we end up with the filtered domains of all of the not yet assigned variables being empty, this means the search should backtrack because this particular branch in the search tree has no solution.
• If after a run of arc consistency during the backtracking search we end up with the filtered domain of one of the not yet assigned variables being empty, this means the search should backtrack because this particular branch in the search tree has no solution.
• If after a run of arc consistency during the backtracking search we end up with the filtered domains of all of the not yet assigned variables each having exactly one value left, this means we have found a solution.
• If after a run of arc consistency during the backtracking search we end up with the filtered domains of all of the not yet assigned variables each having more than one value left, this means we can’t know yet whether there is a solution somewhere further down this branch of the tree, and search has to continue down this branch to determine this.
• When a domain changes after enforcing an arc, all arcs that end at that variable must be re-added to the queue