Constraint Satisfaction Problems (CSP) in AI

A Constraint Satisfaction Problem is a mathematical formulation in which values must be assigned to variables so that every constraint holds. Many AI systems rely on CSPs for decision-making. Typical CSP applications include:

Scheduling: Assigns resources such as staff or equipment while honoring time and availability limits.
Planning: Arranges tasks under deadlines or ordering requirements.
Resource Allocation: Distributes resources efficiently without overuse

Components

Variables: The items that need values. In Sudoku, each blank cell is a variable awaiting a digit.

Domains: The allowed values for each variable. In Sudoku, every cell’s domain is the integers 1 through 9.

Constraints: Rules that limit how values may be assigned. Constraint kinds include:

Unary: Concern one variable, e.g. “this cell cannot be 5”.
Binary: Concern two variables, e.g. “these two cells cannot share a number”.
Higher-order: Concern three or more variables, e.g. “each Sudoku row must contain 1–9 with no repeats”.

Types

CSPs can be grouped by how many variables constraints involve and by how strict those constraints are:

Binary CSPs: Every constraint links exactly two variables. In scheduling, a constraint might require that task A finish before task B.
Non-Binary CSPs: Constraints involve more than two variables. In seating, a rule might forbid three people from sitting adjacent.
Hard and Soft Constraints: Hard constraints must always hold; soft constraints may be broken at a cost. Real applications often treat constraints with unequal priority.

Representation

A constraint is described by a scope and a relation:

Scope: The variables the constraint covers.
Relation: The allowed value combinations for those variables.

Example: For variables V1 and V2, a constraint such as \(V1 \neq V2\) means the two may not share the same value.

Solving CSPs Efficiently

CSPs combine search with constraint techniques to find satisfying assignments. Common methods:

1. Backtracking Algorithm

A depth-first approach that assigns values to variables and retreats when an assignment breaks a constraint.

Working:

Choose an unassigned variable and give it a value.
Keep assigning values to remaining variables.
If a constraint fails, backtrack and try a different value.
Stop when a full solution appears or every option is exhausted.

Backtracking is straightforward and works for many CSPs, but large spaces can make it costly.

2. Forward-Checking Algorithm

Strengthens backtracking by updating domains of unassigned neighbors after each assignment.

Working:

Assign a value to a variable.
Drop inconsistent values from neighboring variables’ domains.
If any domain empties, backtrack at once.
Continue until a solution is found.

This avoids more wasted search than plain backtracking.

3. Constraint Propagation Algorithms

Shrink the search space by repeatedly discarding values that cannot meet the constraints.

Working:

Enforce constraints among related variables.
Remove values that cause inconsistency.
Carry those removals over to other variables.
Stop when no further values can be removed or a solution appears.

Constraint propagation is often paired with backtracking for faster CSP solving.

Example: Solving Sudoku with CSP (Backtracking Approach)

Step 1: Define the Problem (Sudoku Puzzle Setup)

The Sudoku board is a 9×9 grid; 0 marks an empty cell. The print_sudoku() function renders the puzzle clearly.

puzzle = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
          [6, 0, 0, 1, 9, 5, 0, 0, 0],
          [0, 9, 8, 0, 0, 0, 0, 6, 0],
          [8, 0, 0, 0, 6, 0, 0, 0, 3],
          [4, 0, 0, 8, 0, 3, 0, 0, 1],
          [7, 0, 0, 0, 2, 0, 0, 0, 6],
          [0, 6, 0, 0, 0, 0, 2, 8, 0],
          [0, 0, 0, 4, 1, 9, 0, 0, 5],
          [0, 0, 0, 0, 8, 0, 0, 7, 9]]

def print_sudoku(puzzle):
    for i in range(9):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - ")
        for j in range(9):
            if j % 3 == 0 and j != 0:
                print(" | ", end="")
            print(puzzle[i][j], end=" ")
        print()

print("Initial Sudoku Puzzle:\n")
print_sudoku(puzzle)

Notifications

Constraint Satisfaction Problems (CSP) in AI