Python · Course navigation

Constraint satisfaction: coloring a map

Assign values to variables so that every constraint holds, using backtracking search.

On this page

Before you start

Recursion and dictionaries.

Assign values to variables so that every constraint holds, using backtracking search.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

A constraint satisfaction problem (CSP) is defined by variables, a domain of possible values for each, and constraints that restrict which combinations of values are allowed. A solution is a complete assignment that satisfies every constraint. Scheduling, timetabling, sudoku, and circuit layout are all CSPs.

Backtracking search builds an assignment one variable at a time. After choosing a value it checks the constraints, and if a variable has no legal value it backs up and tries something else. Because each step is checked immediately, whole branches of the search are discarded early. Stronger methods add heuristics such as choosing the most constrained variable first, and inference such as forward checking or arc consistency, which remove impossible values before they are tried.

The example is the standard map-coloring problem for the states of Australia: adjacent regions must receive different colors. South Australia touches five other regions, so two colors are not enough, and the search correctly reports that no solution exists. With three colors it finds one, and the program independently checks every adjacent pair. Tasmania has no neighbors, so it can take any color. The exact solution depends on the order in which variables and colors are tried.

Code example

Python

NEIGHBORS = {
    "WA": ["NT", "SA"],
    "NT": ["WA", "SA", "Q"],
    "SA": ["WA", "NT", "Q", "NSW", "V"],
    "Q": ["NT", "SA", "NSW"],
    "NSW": ["Q", "SA", "V"],
    "V": ["SA", "NSW"],
    "T": [],
}


def solve(colors):
    regions = list(NEIGHBORS)

    def backtrack(assignment):
        if len(assignment) == len(regions):
            return assignment
        region = next(r for r in regions if r not in assignment)
        for color in colors:
            if all(assignment.get(neighbor) != color for neighbor in NEIGHBORS[region]):
                result = backtrack({**assignment, region: color})
                if result:
                    return result
        return None

    return backtrack({})


solution = solve(["red", "green", "blue"])
print(dict(sorted(solution.items())))
print(all(solution[a] != solution[b] for a in NEIGHBORS for b in NEIGHBORS[a]))
print(solve(["red", "green"]))

Output

{'NSW': 'green', 'NT': 'green', 'Q': 'red', 'SA': 'blue', 'T': 'red', 'V': 'red', 'WA': 'red'}
True
None

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1NEIGHBORS = {

2 "WA": ["NT", "SA"],

3 "NT": ["WA", "SA", "Q"],

4 "SA": ["WA", "NT", "Q", "NSW", "V"],

5 "Q": ["NT", "SA", "NSW"],

6 "NSW": ["Q", "SA", "V"],

7 "V": ["SA", "NSW"],

8 "T": [],

9}

12def solve(colors):

13 regions = list(NEIGHBORS)

15 def backtrack(assignment):

16 if len(assignment) == len(regions):

17 return assignment

18 region = next(r for r in regions if r not in assignment)

19 for color in colors:

20 if all(assignment.get(neighbor) != color for neighbor in NEIGHBORS[region]):

21 result = backtrack({**assignment, region: color})

22 if result:

23 return result

24 return None

26 return backtrack({})

29solution = solve(["red", "green", "blue"])

30print(dict(sorted(solution.items())))

31print(all(solution[a] != solution[b] for a in NEIGHBORS for b in NEIGHBORS[a]))

32print(solve(["red", "green"]))

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Pick the next unassigned variable.	`WA first`	—
The constraint check: a color is legal only if no neighbor already has it.	`WA first`	—
Extend the assignment and recurse. If the recursion fails the loop tries the next color: that is backtracking.	`WA first`	—
An independent check that every pair of adjacent regions differs.	`WA first`	{'NSW': 'green', 'NT': 'green', 'Q': 'red', 'SA': 'blue', 'T': 'red', 'V': 'red', 'WA': 'red'} True
With two colors South Australia and its neighbors cannot all differ, so the search exhausts every option and returns None.	`WA first`	{'NSW': 'green', 'NT': 'green', 'Q': 'red', 'SA': 'blue', 'T': 'red', 'V': 'red', 'WA': 'red'} True None

Behind the scenes

How Python processes this code

Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.

Cost and common mistakes

Worst case O(d^n) for n variables with domain size d. Constraint checking and ordering heuristics make most practical instances much faster.

A CSP solution depends on variable and value ordering. Different orders can give different valid answers.
Plain backtracking can be exponential. Heuristics (most constrained variable) and inference (forward checking, arc consistency) are what make real solvers fast.
The adjacency lists must be symmetric: if A lists B, B must list A, otherwise a constraint is only checked in one direction.

Try it yourself

Why is two colors impossible for this map?

Reveal answer and reasoning

South Australia, Western Australia, and the Northern Territory all touch each other, forming a triangle. A triangle needs three different colors.