In 1976, Kenneth Appel and Wolfgang Haken used a brute force of over 1,900 maps to prove that any map can be filled using four colors such that no two adjacent regions share the same color. It was the first proof done by a computer, and opened up a new world of computationally intense mathematics!

 

Generally, maps are solved using a depth-first search algorithm. For this project, I instead rewrote the problem as a linear optimization question, and used AIMMS built-in algorithms to output a solution.

 

The Four Color Theorem is a fun problem because it requires a paradigm shift in visualization of a map, regardless of what algorithm you use. Rather than visualize a series of states, one must instead think of each state as a node and develop a method to ensure that no two states that share a border (in this case, nodes that share a connection) end up the same color. 

To create a four color map, simply input a list of all the adjacent connections into AIMMS, optimize by disallowing neighboring nodes to share the same value, and run! You will receive an output where each state is given a numerical value [1, 4], with each value corresponding to a different color. Make sure to double check your mapping by actually inputting it into the map! It's very easy to overlook neighboring states in more complex map regions.