Writing Colorful Code
The downloadable example program for this article
is rather involved and contains a lot of code that isn't related to map coloring so I haven't shown it all here. For example, it includes a simple map editor (not discussed) that lets you draw regions to color.
The program represents regions on the map with the MapRegion class. This class provides basic support for adding and removing a region from a list of MapRegion objects.
The code in Listing 1
shows the most important parts of the main program's map-coloring code. I've used VB.NET for the code in this article, but the download includes a C# version.
The code begins by declaring a list called m_Regions that holds the MapRegions that comprise the map: Private
m_Regions As New List(Of MapRegion)
It then declares a RuleTypes enumeration that defines values representing the two rules for simplifying the map.
' The two rules for simplifying the map.
Private Enum RuleTypes
method controls the map coloring process. It creates a stack named action_stack to keep track of the rules the program follows and the objects that are involved when the map is manipulated.
Private Sub AssignColors()
' The removed regions.
Dim action_stack As New Stack()
' Simplify the map.
Do While m_Regions.Count > 0
' Rebuild the map.
Do While action_stack.Count > 0
While the m_Regions
collection holds any MapRegion objects, AssignColors
calls the SimplifyMap
method (see Listing 1
) which appliesthe two rules. It continues calling SimplifyMap
Next the subroutine calls RestoreRegion to undo one of the rules stored in action_stack. It continues calling RestoreRegion until the stack is empty and all of the MapRegion objects have been restored to the map and colored properly.
first attempts to apply Rule 1, searching the regions list for a region with a degree less than five. If it finds such a region, it removes it from the regions list and adds it to the stack. It also adds the RuleTypes value DegreeUnderFive
to the stack to remember that it used Rule 1 on this node.
cannot apply Rule 1, it applies Rule 2, searching for a region with a degree of exactly five that has neighbors N1 and N2 that are not neighbors of each other. The MapRegion class's FindNonAdjacents
function returns True
when a region satisfies these conditions.
After finding the necessary node and its neighbors, the subroutine removes the node. It makes a new node to represent the neighbors, makes the new node adopt the neighbors' lists of neighbors, and adds the new node to the regions list. It then removes the original neighbors from the list and pushes all the relevant objects onto the stack. It finishes by adding the RuleTypes value NonAdjacentNeighbors
to the stack to record the fact that it used Rule 2 on these objects.
reverses the most recent simplification. It pops the most recent RuleTypes value off the stack to determine which rule was used at this point in the simplification process.
If the most recent simplification was made with Rule 1, the subroutine pops the node that was removed under Rule 1 off the stack. It puts the node back in the map and calls its AssignColor
method to give it a color. The MapRegion class's AssignColor
method picks a color for the node that isn't used by its neighbors. Because the region has degree less than five, there is at least one unused color available.
' Assign a color to this region.
Public Sub AssignColor()
Me.ColorIndex = 0
' Try each color (skipping the "unassigned" color).
For test_color As Integer = 1 To BackColor.Length - 1
' See if neighbor is using this color.
Dim is_used As Boolean = False
For Each nbr As MapRegion In Neighbors
If nbr.ColorIndex = test_color Then
is_used = True
' See if the color is available.
If Not is_used Then
Me.ColorIndex = test_color
' Make sure we found a color.
Debug.Assert(Me.ColorIndex > 0, _
"Error assigning a color to the region")
If instead the most recent simplification was made with Rule 2, the subroutine pops all the relevant objects off the stack. It restores the neighbors to the map and sets their colors to the color previously assigned to the combined region. It then removes the combined region, restores the original node X that had degree exactly five, and calls its AssignColor
As you can see, coloring a map with five colors isn't too hard. In fact, because the MapRegion class's AssignColor
method considers the five available colors in the same order every time, it picks the fifth color only when it mustso it often finds four-colorings "accidentally." However, if you really need to produce four-color maps reliably every time, you can always check the 1,476 special cases used in Appel and Haken's proof!