Constraint Satisfaction Problems (CSPs): Map Coloring

This page generates a random planar map, splits it into labelled regions (A, B, C, ...), and colors it with 4 colors using a constraint satisfaction solver. The objective is to color each region so that no two adjacent regions have the same color.

A Constraint Satisfaction Problem (CSP) consists of a set of variables (the regions), each with a domain of possible values (colors), and a set of constraints (no adjacent regions can have the same color). In this problem, each region starts with all four colors as its domain. The constrainst satisfaction solver enforces a type of consistency (arc consistency) between neighbouring regions. As each region's color is decided, the domains of neighboring regions shrink. These changes in turn have ripple effects.

In this demonstration, watch the domain of each variable change as the map is colored.