Four Color Theorem

Four Color Theorem The four color theorem states that any map in a plane can be colored using at most four colors in such a way that regions sharing a common boundary (other than a single point) do not share the same color. Wikipedia

Original work

• Kenneth Appel, Wolfgang Haken (1977): Every planar map is four colorable. Part I: Discharging (the theorem)
• Neil Robertson, Daniel Sanders, Paul Seymour, Robin Thomas (1997): The Four-Colour Theorem

How it works

The map is built on a grid: one seed per 30 cells is placed at a random free position. All seeds grow at the same time by breadth-first search (one shared queue) until every cell belongs to a region. Two regions are neighbors when two of their cells share an edge.

• Data structure: a list of regions, each with a set of its neighbor ids (adjacency list). The grid stores only region id and color per cell.
• Solving: backtracking. The solver always takes the most constrained region first (DSATUR): the one whose neighbors already use the most distinct colors, on a tie the one with the most neighbors. For it the colors 1 to 4 are tried; if none fits, the solver steps back. Attempts count every color assignment, including the ones undone later.
• The default map (25 × 25, 20 regions) solves in under 1 ms. Usually it needs exactly one attempt per region. So the page never freezes, the solver gives up after 100,000 attempts (about 1 in 3,000 maps at the largest size) and says so; then generate a new map.
• Checking: walk all regions and compare each color with its neighbors, O(regions + borders).

Source code:four-color.service.ts

Note This algorithm uses backtracking to find a valid coloring for the generated regions.

• Map Generation: Regions are generated using a random seed growth algorithm (Voronoi-like) on a grid.
• Adjacency: Two regions are considered neighbors if they share at least one edge in the grid.
• Backtracking: The solver tries colors 1-4 for each region, backtracking when a conflict is found.
• Interactive: You can also click on regions to cycle through colors manually.

Click to color the region. Click again to change the color.