Constraint Satisfaction Problems - CSP

• The constraint network model
– Variables, domains, constraints, constraint graph, solutions
• Examples:
– graph-coloring, 8-queen, cryptarithmetic, crossword puzzles, vision
problems,scheduling, design
• The search space and naive backtracking,
• The constraint graph (nodes=variables, edges=constraints, solution=assignment of value to variable such that constraint is not violated)
• Like DFS, go deep, called backtracking search
- state = assignment of values to variables while constraints are satisfied
- operator = assignment to next variable such that constraints are not violated
- goal = consistent assignment of all variables
- depends on variable ordering, so d={z,x,y} gives different tree when d={x,y,z}

Maybe:
• Consistency enforcing algorithms
– arc-consistency, AC-1,AC-3

Eg. map-coloring
variables - locations / countries / regions
values - colors in domain of red, green, blue
constraints - adjacent countries are colored differently
graph - nodes are variables (locations), edges are constraints so put an edge between two adjacent regions

Eg. 9x9 sudoku
variables - cells / squares that hold numbers, 81 variables for 9x9 problem
values - numbers in domain 1 to 9
constraints (27 constraints) -
a) each row has unique numbers ie all numbers from 1 to 9, 'Not-equal', AllDiff(a11, a12, a13, ..., a19) - 9 constraints
b) each col has unique numbers ie all numbers from 1 to 9, AllDiff(a11, a21, a22, ..., a29) - 9 constraints
c) each 3x3 grid (9 of them) sums contains all numbers from 1 to 9 - AllDiff(a11, a12, a13, a21, a22, a23, a31, a32, a33) 9 constraints

Eg. Four queen
variables - rows (x1, x2, x3, x4)
values - columns {1,2,3,4}
constraint ((4 choose 2) = 6 constraints)
- graph - (x1-x2), (x1-x3), (x1-x4), ..., (x4-x2), (x4-x3) (a box with a cross inside)
- so each variable constrains all other variables

Look-ahead schemes:
• Value ordering/pruning (choose a least restricting value),
• Variable ordering (choose the most constraining variable)
• Constraint propagation (take decision implications forward)

Heuristics:
1. Minimum Remaining Values (MRV) heuristic - choose the variable with the fewest legal values
2. Degree heuristic: MRV tie breaker, choose the variable with the most constraints on remaining variables
3. Given a variable, choose the least constraining value:
– the one that rules out the fewest values in the remaining variables
4. min-conflicts

Forward checking
- Idea: Keep track of remaining legal values for unassigned variables
Terminate search when any variable has no legal values
- constraint propagation

Arc-consistency (AC-3)
Arc ( X i ,X j ) is arc-consistent if for any value of X i there exist a matching (allowed) value of X j
Begin
1. For each a in Di if there is no value b in Dj that matches a then delete a from the Dj.
End.
X → Y is consistent iff
for every value x of X there is some allowed y
- detects error earlier than forward checking

• Time complexity: O(ed3)
• e = # edges, d = variable domain size)

Local search for CSPs - h(n) = min-conflicts
• Variable selection: randomly select any conflicted variable
• Value selection by min-conflicts heuristic:
– choose value that violates the fewest constraints
– i.e., hill-climb with h(n) = total number of violated constraints

WalkSAT - adds random walk to GSAT ( hill climbing )

Simulated Annealing
Theoretically, with a slow enough cooling schedule, this algorithm will find the optimal solution. But so will searching randomly.

Tree structured CSPs (eg by cutset) can be solved in linear time (O(d^C*d^2) c = cut-set size

conditioning - instantiate a variable, prune its neighbours' domain