8 Coloring graphs with backtracking search
In this chapter
- Some surprising applications of coloring maps
- The benefits of simplicity
- Backtracking search
- A multi-dictionary data structure
Graph theory – the mathematical study of what happens when you have a bunch of “nodes” connected with a bunch of “edges” - is an enormous part of combinatorics and has had a huge impact on computer programming. In this chapter we’ll look at one of the classic graph theory problems: given some number of colors and a graph, can we assign a color to each node such that two adjacent nodes -- that is, two nodes directly connected by an edge -- are never the same color? If yes, how? Node coloring has direct bearing on many real-world problems, such as coloring regions on a map, solving sudoku puzzles and avoiding register spills.
The backtracking search algorithm is a fundamental problem-solving strategy. You make a guess at the solution and check if you guessed right. If you guessed wrong, go back and make a different guess. Repeat until you either run out of guesses or find the solution. We’ll apply the backtracking search algorithm to solve the graph coloring problem and create a general-purpose engine for backtracking solutions to other problems.
Once again, we will take full advantage of the power of immutable data structures, as they are particularly well-suited to backtracking search.