8 Coloring graphs with backtracking search
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 influence 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 so that two adjacent nodes (two nodes connected directly 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.
Though the implementation details can be complex, the backtracking search algorithm is, at its core, a basic problem-solving strategy. You make a guess at the solution and check whether you guessed right. If you guessed wrong, go back and make a different guess; repeat until you run out of guesses or find the solution.
In this chapter, 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’ll take full advantage of the power of immutable data structures, which are particularly well suited to backtracking search.