Constraint Satisfaction Problems (CSP)

Introduction

Constraint Satisfaction Problems (CSPs) are a class of problems in which the goal is to assign values to a set of variables in a way that satisfies a given set of constraints. Each variable has a domain (a set of possible values), and the constraints restrict the values that the variables can simultaneously take. CSPs are used in various fields such as AI, scheduling, planning, resource allocation, and more.

1. Backtracking Search for CSPs

• Backtracking is the simplest and most common algorithm for solving CSPs. It assigns values to variables one at a time and checks if the assignment is consistent with the constraints.
• Process:
  1. Assign a value to a variable.
  2. Check if the current assignment satisfies the constraints.
  3. If the assignment is consistent, proceed to the next variable.
  4. If not consistent, backtrack by undoing the last assignment and trying a different value.
• Example:

  • Variables: A and B, with domains {1, 2}, and constraint A=B.

    AA

    BB

    A≠B

  • Steps:

    • Try A=1,B=1 (violates the constraint A=B), so backtrack.

      A=1,B=1A = 1, B = 1

      A≠B

    • Try A=1,B=2 (satisfies the constraint), solution found.

      A=1,B=2A = 1, B = 2

2. Variable and Value Ordering

• Efficiency in backtracking can be greatly improved by choosing variables and values smartly.
  • Variable Ordering:
    • Most Constrained Variable (Minimum Remaining Values): Choose the variable with the fewest remaining legal values to assign.
  • Value Ordering:
    • Least Constraining Value: Choose the value that rules out the fewest options for the remaining variables.
• Example:

  • Variables X,Y,Z, with X having only one possible value left, while Y and Z have two values. Assign X first to improve the chances of finding a solution quickly.

    X,Y,ZX, Y, Z

    XX

    YY

    ZZ

    XX

3. Propagating Information Through Constraints

• Information about assigned values can be propagated to other variables to reduce the size of their domains, preventing early constraint violations.

  • Forward Checking:

    • After assigning a value to a variable, eliminate values from the domains of neighboring variables that would violate constraints.

    • Example: For variables X and Y with the constraint X<Y, assigning X=2 removes values ≤2 from Y’s domain.

      XX

      YY

      X<YX < Y

      X=2X = 2

      ≤2\leq 2

      YY

  • Arc Consistency:

    • Ensures that for every value of a variable, there exists a consistent value in all its neighboring variables. If a variable’s domain becomes empty, backtracking occurs.

4. Intelligent Backtracking

• Standard backtracking can be inefficient as it may undo irrelevant assignments. Intelligent backtracking (or conflict-directed backjumping) improves efficiency by backtracking to the variable responsible for the conflict.
• Example:

  • Variables A, B, and C with constraints A=B and B=C.

    AA

    BB

    CC

    A≠BA \neq B

    B≠CB \neq C

  • If assigning C=3 leads to a conflict due to B=3, intelligent backtracking skips A and directly backtracks to B.

    C=3C = 3

    B=3B = 3

    AA

    BB

5. Local Search for CSPs

• Local search is a heuristic-based approach that starts with an initial assignment and improves it iteratively by making small changes until a solution is found.
  • Hill Climbing: Adjust the value of a variable to reduce the number of violated constraints.
  • Min-Conflicts Heuristic: Select the value for a variable that results in the fewest constraint violations.
• Example:

  • CSP with variables X,Y,Z from domain {1, 2, 3} and the constraint that no two variables can have the same value. Local search might start with X=1,Y=1,Z=3, then iteratively change Y’s value to 2 or 3 to satisfy the constraints.

    X,Y,ZX, Y, Z

    X=1,Y=1,Z=3X = 1, Y = 1, Z = 3

    YY

6. Case Study: Map Coloring Problem

The Map Coloring Problem is a classic example of a CSP where the objective is to assign colors to regions on a map such that no two adjacent regions have the same color.