Constraint Satisfaction Problems

Many real-world AI problems are not about finding a single path, but about finding a solution that satisfies a set of rules or restrictions. These problems are called Constraint Satisfaction Problems (CSP).

CSPs are widely used in scheduling, planning, configuration systems, and decision-making tasks where multiple conditions must be met at the same time.

What Is a Constraint Satisfaction Problem?

A Constraint Satisfaction Problem consists of three core components:

• Variables: The elements that need values
• Domains: The possible values for each variable
• Constraints: Rules that restrict which values are allowed together

The goal is to assign values to all variables such that all constraints are satisfied.

Real-World Examples of CSP

CSPs appear naturally in many practical systems:

• Timetable scheduling: Classes must not overlap, rooms must be available
• Exam scheduling: A student cannot attend two exams at the same time
• Sudoku: Numbers must follow strict placement rules
• Map coloring: Neighboring regions must have different colors

In all these cases, the solution is not a path, but a valid assignment.

How CSP Is Different from Search

Unlike traditional search problems, CSP focuses on valid combinations rather than sequences of actions.

• Search problems explore paths
• CSPs explore assignments
• Constraints prune invalid options early

This makes CSP approaches very efficient for structured problems.

Basic CSP Solving Idea

A simple CSP solver works as follows:

• Select an unassigned variable
• Try a value from its domain
• Check whether constraints are violated
• If violated, backtrack and try another value

This process is called backtracking search.

Simple CSP Example: Map Coloring

Let’s consider a simple map coloring problem where neighboring regions must have different colors.

regions = ["A", "B", "C"]
colors = ["Red", "Green", "Blue"]

constraints = {
    ("A", "B"),
    ("B", "C")
}

def is_valid(assignment, region, color):
    for (r1, r2) in constraints:
        if region == r1 and assignment.get(r2) == color:
            return False
        if region == r2 and assignment.get(r1) == color:
            return False
    return True

def backtrack(assignment):
    if len(assignment) == len(regions):
        return assignment

    region = regions[len(assignment)]
    for color in colors:
        if is_valid(assignment, region, color):
            assignment[region] = color
            result = backtrack(assignment)
            if result:
                return result
            del assignment[region]
    return None

solution = backtrack({})
print(solution)
  

Code Explanation

This example models regions as variables and colors as domain values.

• The is_valid function checks constraints
• The backtrack function tries assignments recursively
• Invalid choices are discarded early

Output Explanation

The output shows one valid assignment where no neighboring regions share the same color. Multiple solutions may exist, but this is one correct solution.

Why CSP Matters in AI

CSP techniques allow AI systems to solve problems efficiently without brute force. They are foundational for planning systems, scheduling software, and decision engines.

Advanced AI systems use optimized CSP techniques such as constraint propagation and heuristics to scale to large problems.

Practice Questions

Quick Quiz