Skip to content
Map coloring, using four colors
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.
iran.jpg Check image dimensions Jun 22, 2019
usa.png Add samples Jan 14, 2019


Map coloring, using four colors

This program gets a map image as an input and produces all possible valid colorings of that map using backtracking.

The input image background and borders should be white.

Some Basic Stuff to Know

  1. Map coloring
  2. Four color theorem


  1. Detecting all non-white regions (eg. provinces or states).
  2. Converting the input map to a simple planar graph: There will be a node for each region. Two nodes will be adjacent, if and only if their correspondent region have a common border on the map.
  3. Using backtracking for coloring that graph (it's a recursive function that produces all valid colorings).
  4. Displaying all produced colorings on the given map.


Install numpy, matplotlib and opencv using pip.

pip install -r requirements.txt


python3 map_image_file_name


python3 iran.jpg

The original image:

A part of the program output:

python3 tehran_province.jpg

The original image:

A part of the program output:

python3 usa.png

The original image:

A part of the program output:


It runs slowly on large images. It can be improved by changing the second part of its algorithm (about setting the graph edges). Some computational geometry knowledge about polygons may be needed for this part.

Any contributions are welcomed.

You can’t perform that action at this time.