Chapter 8: Coloring graphs with backtracking search

Introduction

Introduces graph coloring as an adjacency-constrained assignment problem and previews using immutable data structures and backtracking search to solve it and related problems.

• Graph-coloring constraint: Explain the graph-coloring problem: assign a color to every node of a graph so that directly connected, or adjacent, nodes never receive the same color. Mention that nodes and vertices are alternative names for the same graph element, although this chapter uses node.
  Why it matters: This constraint is the problem that the chapter’s graph and backtracking code is designed to solve.
• Backtracking search strategy: Describe backtracking search as making a candidate guess, checking it, returning to make a different guess when it fails, and continuing until a solution is found or the available guesses are exhausted. State that the chapter applies this strategy to graph coloring and develops a general-purpose backtracking engine for other problems.
  Why it matters: Backtracking turns a problem with many possible assignments into a systematic search that can recover from wrong choices.
• Immutable backtracking support: State that the chapter uses immutable data structures and explain that they are particularly well suited to backtracking search. Identify the chapter’s planned components as an immutable multidictionary, an immutable undirected graph, and applications including maps, Sudoku, and register-spill avoidance.
  Why it matters: Immutable representations fit a search that needs to preserve and revisit alternative states.

Key terms: graph coloring, node, edge, adjacent nodes, vertex, backtracking search algorithm, guess, solution, general-purpose engine, immutable data structures

8.1 Coloring South America

This section introduces map coloring, explains why real maps can need extra constraints, and models the problem with an immutable undirected graph.

• Map-coloring constraints: Explain the map-coloring problem as assigning colors to regions so that regions sharing a border do not receive the same color. Describe why Argentina, Bolivia, Brazil, and Paraguay demonstrate that at least four colors are needed for that part of South America.
  Why it matters: This is the concrete problem that graph coloring will turn into a programmable search problem.
• Four-color theorem and exceptions: State that four colors suffice for any ordinary map of regions on a plane or sphere, while explaining why practical political maps may use or require more colors because of presentation choices and extra political constraints.
  Why it matters: The distinction prevents the mathematical four-color result from being mistaken for a rule that every real-world political map can directly follow.
• Undirected graph abstraction: Describe the immutable undirected graph used to represent map coloring: nodes stand for regions, and edges connect adjacent regions that must have different colors. Distinguish an undirected edge, which only records connection, from a directed edge with identifiable from and to nodes.
  Why it matters: This abstraction removes geographic details and provides the data model needed to write a coloring program.

Key terms: map coloring, adjacent regions, sharing a border, four-color theorem, plane, sphere, noncontiguous political regions, French Guiana, abstract data type, immutable undirected graph

8.2 An immutable multidictionary

This section chooses and implements an immutable multidictionary as the adjacency representation needed for immutable graphs.

• Graph representation alternatives: Describe the incidence matrix, adjacency matrix, and adjacency dictionary representations for a graph, including what each one maps or records. Explain why the adjacency-dictionary approach is selected here.
  Why it matters: Choosing the representation determines how graph nodes, edges, and neighbor lookups can be implemented immutably.
• Immutable multidictionary structure: Explain that the multidictionary wraps an ImmutableDictionary whose keys map to immutable sets of values, allowing each key to have zero or more associated values.
  Why it matters: This wrapper provides the multivalue adjacency information required to represent graph neighbors without mutation.
• Multidictionary operations and cost: Describe the multidictionary API: forwarding basic dictionary operations, checking a particular value with HasValue, updating value sets with Add(K,V) and Remove(K,V), and using SetSingle or SetEmpty as helpers. State that immutable dictionary and immutable hash-set additions, removals, and lookups are O(1).
  Why it matters: The API supplies the updates and membership tests needed to build and query graph adjacency efficiently.

Key terms: incidence matrix, adjacency matrix, adjacency dictionary, multidictionary, immutable graph, ImmutableDictionary, immutable hash set, System.Collections.Immutable, IsEmpty, ContainsKey

8.3 An immutable undirected graph

This section defines an immutable undirected graph as a graph-oriented wrapper around an immutable multidictionary that enforces graph invariants and supports nodes, edges, and cliques.

• Graph abstraction rationale: Explain why an undirected graph needs its own type rather than exposing an immutable multidictionary directly. Include both invariant enforcement and the benefits of graph-specific terminology and hiding the storage implementation.
  Why it matters: A dedicated abstraction prevents invalid graphs and lets graph code remain clear even if the representation changes.
• Undirected adjacency representation: Describe how ImGraph<N> represents an immutable undirected graph with an ImMulti<N,N>: dictionary keys are nodes and each node's values are its adjacent nodes. State that an edge must appear in both nodes' adjacency sets.
  Why it matters: Storing adjacency symmetrically is the representation rule that makes graph operations behave as undirected operations.
• Invariant-preserving graph updates: Trace how AddNode, AddEdge, and RemoveNode preserve graph invariants in the immutable graph. State that AddNode creates an empty adjacency set when needed, AddEdge records both directions and introduces missing nodes, and RemoveNode removes the node's edges before removing the node.
  Why it matters: These update rules ensure that graph construction and deletion cannot leave dangling or one-way relationships.
• Clique construction support: Describe a clique as a set of nodes in which every node is adjacent to every other node, and explain that AddClique adds edges for every pair in an indexed list. State that this takes O(n2) time in the number of listed nodes.
  Why it matters: Cliques compactly represent groups of mutually constrained nodes, which is useful in later graph problems.

Key terms: ImGraph<N>, ImMulti<N,N>, invariants, nodes, edges, adjacency matrix, node, edge, adjacent nodes, adjacency set

8.4 Coloring simple graphs

This section develops a recursive graph-coloring algorithm that removes low-degree nodes, colors the remaining graph, and restores the nodes with available colors.

• Map coloring constraints: Explain how a map such as South America is modeled as a graph-coloring problem, with countries as nodes and shared borders as edges. State that adjacent nodes must receive different colors and that a node’s degree is its number of incident edges.
  Why it matters: This graph model makes a geographic coloring puzzle into a problem an algorithm can solve.
• Low-degree recursive coloring: Describe the recursive algorithm for coloring a graph with c colors: use the empty graph as the base case, remove a node whose current degree is less than c, recursively color the smaller graph, then give the removed node any color unused by its neighbors. State that the algorithm reports failure when no node has degree less than c.
  Why it matters: Removing a safely colorable-last node turns graph coloring into smaller instances of the same problem.
• Performance and failure limits: State that successful runs take between O(n+e) and O(n²+e) time for n nodes and e edges: node searches range from O(n) total in the best case to O(n²) in the worst case, while removing all nodes and edges costs O(n+e). Explain that the method is useful for graphs with many low-degree nodes but cannot proceed when every remaining node has degree greater than the number of available colors.
  Why it matters: The complexity and failure condition show when this simple algorithm is a practical choice and when a more general search is needed.

Key terms: graph coloring, adjacent nodes, degree, degree-zero node, empty graph, base case, degree less than c, available color, immutable dictionary, O(n+e)

8.5 Solving Sudokus with backtracking search

This section models Sudoku as graph coloring and introduces recursive backtracking as the stronger search needed when simple graph coloring cannot proceed.

• Sudoku graph-coloring model: Explain how a nine-by-nine Sudoku becomes a graph-coloring problem: each cell is a node, digits 1 through 9 are colors, and cells that cannot share a digit are connected by edges.
  Why it matters: This translation lets a puzzle with rows, columns, and boxes be solved using graph algorithms.
• Clique constraints and algorithm limit: Describe why each Sudoku row, column, and three-by-three box forms a clique, and explain why the simple coloring algorithm from section 8.4 cannot start: every node has degree 20 while only nine colors are available.
  Why it matters: It motivates replacing a local simple-coloring strategy with a search that can make and test choices.
• Recursive backtracking search: Trace the backtracking algorithm: fail when an uncolored node has no possible color, succeed when the graph is legally colored, otherwise choose a node with at least two possible colors and recursively try guesses until one succeeds or all fail. State that it backtracks by returning to a failed guess and trying another color, and that it eventually finds a solution if one exists.
  Why it matters: Backtracking systematically explores alternatives rather than abandoning a constrained problem when no immediate deterministic choice is available.

Key terms: graph coloring, nodes, edges, colors, Sudoku, clique, degree 20, nine colors, simple coloring algorithm, backtracking

8.5.1 Graph coloring is NP-complete

This section defines NP-completeness, shows why graph coloring belongs to that class, and explains why a complete backtracking solver has exponential worst-case time.

• Polynomial versus exponential performance: Distinguish polynomial worst-case performance, O(n^c) for a constant c, from exponential performance, O(c^n). State that exponential algorithms are not polynomial.
  Why it matters: This distinction is needed to understand why a solver can be correct but still become impractical on large inputs.
• NP-complete problem characteristics: Describe the defining characteristics given for NP-complete problems: they are yes-or-no questions, a proposed yes solution can be verified in polynomial time, no polynomial-time solver is known, and a polynomial solver for one would provide one for all NP-complete problems.
  Why it matters: NP-completeness explains both what makes these problems special and why a universally fast solution would be a major breakthrough.
• Graph coloring verification and hardness: Explain how graph coloring becomes a yes-or-no question by asking whether a graph has a coloring using a specified number of colors, such as four for South America. Describe verifying a proposed coloring by checking every edge has differently colored endpoints, which is polynomial because a graph with n nodes has at most O(n^2) edges.
  Why it matters: Being easy to verify is the key connection between a concrete coloring and the NP-complete classification.
• Backtracking search performance: Explain that backtracking search can solve arbitrary graph-coloring instances or report failure, but its worst-case performance must be exponential because graph coloring is NP-complete and no polynomial-time solution algorithm is known. Describe the practical strategy of reducing the number of possibilities the algorithm must guess.
  Why it matters: This sets realistic expectations for a complete backtracking solver and motivates heuristics that shrink its search space.

Key terms: polynomial performance, exponential, O(n^c), O(c^n), NP-complete, polynomial time, yes-or-no questions, verification, complete, graph coloring

8.5.2 Implementing a general backtracker

This section builds a reusable backtracking solver by representing possible assignments as attempts, reducing them without guesses, and recursively exploring the remaining choices to solve Sudoku.

• Attempt state representation: Describe an attempt as a multidictionary mapping each key or graph node to its remaining possible values or colors, and state how an attempt indicates a solution or a broken state.
  Why it matters: This representation lets the solver recognize completed and impossible branches before making further guesses.
• Constraint reduction fixed point: Explain how the reducer removes impossible colors without guessing: ReduceOnce removes a singleton node's color from its neighbors, and Reduce repeats this operation until no further progress is made.
  Why it matters: Propagating forced consequences before branching can solve or reject an attempt while avoiding many guesses.
• General backtracking control flow: Trace the general backtracker: reduce an attempt first, return no solutions if it is broken, return the one attempt if it is solved, otherwise branch on a key with multiple values and recursively combine the solutions from each guessed value using SelectMany.
  Why it matters: This control flow makes the solver reusable for any constrained mapping problem, not only graph coloring.
• Sudoku solver initialization: Describe how Sudoku is supplied to the general solver by giving every cell all nine digits initially, restricting given cells to their supplied digits, and taking the first returned solution because the puzzle is designed to have one solution.
  Why it matters: It shows how a concrete puzzle is expressed as an initial constrained attempt for the reusable solver.

Key terms: attempt, multidictionary, solution, broken attempt, reducer, ReduceOnce, Reduce, possible colors, neighbors, backtracker

8.5.3 How could we improve?

This section identifies several ways a graph-coloring reducer could prune Sudoku search faster and explains why richer Sudoku-specific deductions can greatly reduce backtracking.

• Early contradiction detection: Explain that the reducer should detect a broken coloring attempt as soon as a reduction leaves a node with no possible colors, rather than continuing work and leaving the backtracker to reject it later.
  Why it matters: Rejecting an impossible branch immediately avoids wasting reduction and search effort.
• Incremental reduction work: Describe how repeated calls to ReduceOnce redo much of the same scanning and adjacency checking, and explain that the reducer could retain information about earlier reductions to avoid repeating that work.
  Why it matters: Avoiding repeated graph scans can make propagation substantially more efficient.
• Clique-based Sudoku deductions: Explain that a clique containing as many nodes as available colors guarantees that those colors must be assigned within the clique, enabling further reductions; relate this to Sudoku boxes and deductions such as knowing that a 7 must occur somewhere in the bottom-middle box.
  Why it matters: Clique reasoning can eliminate possibilities without guessing, dramatically shrinking the search that backtracking must perform.
• Sudoku-specific reduction strategies: State that Sudoku enthusiasts use many clique-based tricks to reduce cell possibilities without bifurcation, and explain that encoding such tricks in a graph-coloring reducer could speed backtracking enormously, though this section does not implement them.
  Why it matters: It clarifies that better constraint propagation can often replace brute-force guessing with deductions.

Key terms: reducer, broken attempt, remaining possible colors, backtracker, ReduceOnce, single colors, adjacent nodes, reductions, clique, available colors

8.5.4 Backtracking and the Cartesian product

This section reframes backtracking as Cartesian-product enumeration that prunes impossible partial solutions early through reduction.

• Backtracking as Cartesian-product search: Explain that backtracking search enumerates the Cartesian product of the possible choices for each part of a solution. Relate an unconstrained coloring problem with two independent islands and four colors to the 16 combinations of four colors with themselves.
  Why it matters: This view makes clear what backtracking explores before constraints eliminate possibilities.
• Early pruning by reduction: Describe the reduction step as aggressively filtering a partial attempt as soon as it is known to be broken, so the search avoids exploring regions of the possible-solution space that cannot lead to a valid solution. Distinguish this abstract search from ordinary lookup in a table or descent through a tree for a known item.
  Why it matters: Early pruning is why backtracking can work well when constraints rule out many candidate solutions.

Key terms: Cartesian product, SelectMany, backtracking search, possible solutions, reduction step, constraints, broken attempts, space of possible solutions

8.6 Scheduling problems are graph-coloring problems

This section shows how real scheduling and register-allocation constraints can be modeled and solved as graph-coloring problems.

• Scheduling as graph coloring: Explain how a scheduling problem can be represented as graph coloring: items to schedule become nodes, incompatible items become adjacent nodes, and available resource-and-time choices become colors.
  Why it matters: This translation lets a general graph-coloring solver handle conflicts in practical scheduling tasks.
• Airport gate scheduling model: Describe the airport example in which airplanes are nodes, airplanes using the airport in the same hour are adjacent, and each gate-hour combination is a color.
  Why it matters: It gives a concrete example of turning a limited set of gates and hours into a finite set of nonconflicting assignments.
• Class scheduling constraints: Describe class scheduling as a coloring problem in which room-and-time combinations are colors and edges encode conflicts such as shared students, while other requirements constrain suitable assignments.
  Why it matters: School timetabling illustrates that scheduling includes both direct conflicts and requirements for particular kinds of resources.
• Register allocation graph: Explain register scheduling as graph coloring: local variables are nodes, overlapping lifetimes create edges, and registers are colors, so a complete coloring avoids memory spills.
  Why it matters: Compiler code generators use this model to make efficient use of a processor's limited registers.
• Spill fallback strategy: Describe the fallback when available register colors cannot color every variable: choose the local variable cheapest to spill, remove its node, and try coloring the reduced graph again.
  Why it matters: It explains what the compiler must do when limited registers cannot accommodate all overlapping live variables.

Key terms: graph coloring, nodes, adjacent, colors, scheduling problems, gates, airplanes, classrooms, time slots, adjacencies

8.7 Summary

This section recaps graph coloring, recursive and backtracking approaches to solving it, and the problem's general computational difficulty.