AI Problem Solving — Problem 5

Map Coloring
CSP Solver

Constraint Satisfaction Problem solver using backtracking with degree heuristic. No two adjacent regions share the same color.

CSPAlgorithm

4Max Colors

∞Regions

map-coloring-csp.py — interactive

01 — Add Regions

02 — Define Adjacency

03 — Select Colors

Graph Visualization

Algorithm

Uses CSP Backtracking with degree heuristic — assigns colors to the most-constrained region first, backtracking when a conflict is found.

Four Color Theorem

Any planar map can be colored using at most 4 colors such that no two adjacent regions share the same color. Proven in 1976.

How to Use

Add region names
Link neighboring regions
Select available colors
Click Solve CSP

Sample Input

Regions: A, B, C, D
A↔B, A↔C, B↔C
B↔D, C↔D
Colors: Red, Green, Blue