Map coloring
The four-color theorem says any planar map can be colored with at most four colors so that no two adjacent regions share the same color. Click regions to paint them with the selected color. Can you solve the map without conflicts?
About this lab
The four-color theorem states that any map on a plane (or sphere) can be colored using at most four colors so that no two adjacent regions share the same color. It was first conjectured by Francis Guthrie in 1852, and resisted proof for over a century.
In 1976, Kenneth Appel and Wolfgang Haken finally proved the theorem — but controversially, their proof required a computer to check 1,936 reducible configurations. It was the first major theorem proved with substantial computer assistance, sparking debate about what constitutes a valid mathematical proof. Since then, simpler (but still computer-assisted) proofs have been found.
The map here is generated using a Voronoi diagram: random seed points are scattered on the canvas, and each region consists of all points closer to its seed than to any other. This always produces a valid planar graph. The dual graph — where each region becomes a node and edges connect adjacent regions — can be toggled for visualization.
The auto-solver uses a greedy graph-coloring algorithm: it processes regions in order of decreasing degree (most neighbors first) and assigns each region the smallest color not used by any of its already-colored neighbors. For planar graphs, greedy coloring with a good ordering often uses only four colors, though it is not guaranteed to be optimal in general.