Constraint Satisfaction Problems

Ref [Russell2003Constraints].

The CSP is a tree with binary constraints.

1. function Backtracking-Search(csp) returns a solution or failure
   1. return Recursive-Backtracking({}, csp)

1. function Recursive-Backtracking(assignment, csp) returns a solution or failure
   1. if assignment is complete then return assignment
      1. var ← Select-Unassigned-Variables(Variables(csp),assignment,csp)
      2. for each value in Order-Domain-Values(var,assignment,csp) do
         1. if value is consistent with assignement according to Constraints(csp) then
            1. add {var = value} to assignement
            2. result ← Recursive-Backtracking(assignment, csp)
            3. if result != failure then return result
            4. remove {var = value} from assignment
2. return failure

• Minimum Remaining Values (selecting the variable with the most reduced legal values set) ;
• Degree heuristic (selecting the variable involved in the largest number of constraints).

• Least constraining value (choose the value that rules out the fewest choices in the neighboring variables of the constraint graph).

When assigning a value to X, remove the colliding values from the domain of each variable Y connected by a constraint. AC-3_algorithm

Redundant with backjumping.

A (directed) arc from one variable X to a connected one Y is consistent if, for every value in the domain of X, the domain of Y is not empty. Costlier than forward checking.

1. function AC-3(csp) returns the CSP, possibly with reduced domains
   1. queue ← all the arcs in csp
   2. while queue is not empty
      1. (X_i, X_j) ← Remove-First(queue)
      2. if Remove-Inconsistent-Values(X_i, X_j) then
         1. for each X_k in Neighbors(X_i) do
            1. add (X_k, X_i) to queue

1. function Remove-Inconsistent-Values(X_i, X_j)) returns true iff a value has been removed
   1. removed ← false
   2. for each x in Domain(X_i) do
      1. if no value y in Domain(X_i) allows (x,y) to satisfy the constraint between X_i and X_j then
         1. delete x from Domain(X_i)
         2. removed ← true
   3. return removed

1. function Min-Conflicts(csp,max_steps) returns a solution or failure
   1. current ← initial complete assignment for csp
   2. for i = 1 to max_steps do
      1. if current is a solution for csp then return current
      2. var ← random conflicted variable from Variables(csp)
      3. value ← the value for var that minimizes Conflicts(var,v,current,csp)
      4. set {var = value} in current

return failure