Constraint Satisfaction Problem

Constraint Satisfaction Problem (CSP)

• Variables: $x_1,x_2,\dots ,x_n$
• Constraints: $c_1,c_2,\dots ,c_n$

Assign value at each variable, making sure constraints are respected.

• Assign a value to a variable
• Then, remove available values for other variable to still respect the constraints
• If a variable has no more value available, we return an error

We use backtracking is a recursive method used in CSP: it gradually finds candidate solutions and abandons candidates (backtracks) when a candidate cannot be a good solution.

Heuristics

CSPs can involve high complexity, it often need heuristics to have a reasonable solving time.

Problems example

• Sudoku
• Map coloring problem
• Eight queens puzzle
• Type inference
• Maximum cut problem