Constraint Satisfaction Problem (CSP): Simple Guide

What Is a Constraint Satisfaction Problem?

A constraint satisfaction problem (CSP) is a problem where you must pick a value for each item. All the values together must follow a set of rules.

Sudoku is one example. Every empty box needs a number. The numbers must follow Sudoku's rules.

Variables, Domains, and Constraints

Now that you know what a CSP is in general, here are the three specific parts that make one up. Once you can spot these three in a problem, you can turn almost any puzzle into a CSP.

Every CSP has three parts:

• Variables: the things you need to fill in. In Sudoku, each empty box is a variable.
• Domain: the list of values a variable can take. In Sudoku, the domain is 1 to 9.
• Constraints: the rules. In Sudoku, no row, column, or 3×3 box can repeat a number.

You solve a CSP by giving each variable a value from its domain, without breaking any constraint.

How Backtracking Search Works

You now know the three parts of a CSP. The next question is: how does a computer actually find an answer using them? Backtracking search is the normal way to solve a CSP.

It works like this:

1. Pick a variable that has no value yet.
2. Try a value that does not break any rule.
3. Move to the next variable.
4. If you get stuck, go back one step and try a different value.
5. Stop when every variable has a value, or when no value works anywhere.

Example: Coloring a Map in Python

Here is a short example in Python. It colors five regions so that no two connected regions share a color:

def solve(variables, domains, neighbors):
    assignment = {}
    def is_ok(var, value):
        for n in neighbors[var]:
            if assignment.get(n) == value:
                return False
        return True
    def backtrack():
        if len(assignment) == len(variables):
            return dict(assignment)
        var = next(v for v in variables if v not in assignment)
        for value in domains[var]:
            if is_ok(var, value):
                assignment[var] = value
                result = backtrack()
                if result:
                    return result
                del assignment[var]  # go back and try another value
        return None
    return backtrack()
variables = ["A", "B", "C", "D", "E"]
domains = {v: ["red", "green", "blue"] for v in variables}
neighbors = {
    "A": ["B", "D"], "B": ["A", "C", "D"], "C": ["B", "E"],
    "D": ["A", "B", "E"], "E": ["C", "D"]
}
print(solve(variables, domains, neighbors))

Output:

{'A': 'red', 'B': 'green', 'C': 'red', 'D': 'blue', 'E': 'green'}

Explanation:

Each key in this output is a region (a variable), and each value is the color the backtracking search gave it. Notice A and C both got red — that's fine, because A and C are not neighbors, so no constraint was broken. B, which touches both A and D, had to pick a color different from both.

Sudoku Example

With backtracking search explained, here's how those same five steps play out on a real Sudoku grid.

In a 9×9 Sudoku:

• Variables: the 81 boxes on the grid.
• Domain: numbers 1 to 9.
• Constraints: no repeated number in any row, column, or 3×3 box.

A Sudoku app fills a box with a number that breaks no rule, then moves on. If it gets stuck, it goes back and tries a different number. This is backtracking search.

Example: Filling One Box

Here's a trace of the app trying to fill a single empty box:

Trying box (1,1)...
  1 -> conflicts with row  -> skip
  2 -> conflicts with column -> skip
  3 -> conflicts with 3x3 box -> skip
  4 -> no conflicts -> place 4
Box (1,1) = 4

Output:

Box (1,1) = 4

Explanation:

This is exactly step 2 and step 3 of backtracking search: the app tries values in order, throws out any that break a rule, and keeps the first one that works before moving to the next box.

Map Coloring Example

The Sudoku example showed variables that are boxes on a grid. Map coloring shows the same three parts applied to a completely different kind of problem — regions on a map.

Map coloring asks: can you color every region on a map so that no two regions that touch have the same color?

• Variables: each region on the map.
• Domain: the colors you can use, like red, green, and blue.
• Constraints: two regions that share a border must not have the same color.

Computers use this same idea to keep nearby phone towers from using the same signal frequency.

Example: Running the Solver

This is the same problem the Python example above already solved.

Output

{'A': 'red', 'B': 'green', 'C': 'red', 'D': 'blue', 'E': 'green'}

Explanation:

Each letter is a region, and each color is the answer the search picked — a valid map coloring where no two touching regions share a color.

Quick Comparison

To tie everything together, here's how Sudoku and map coloring line up side by side using the same three CSP parts.