Suppose you must color a graph so that adjacent nodes never share a color. A simple coloring method works for some graphs but cannot solve every case. Backtracking handles the harder ones: choose a candidate color, explore its consequences, and return to the choice if it cannot lead to a legal coloring. The same search can find a solution or establish that none exists. section 8.0 section 8.7
Represent an attempt as a multidictionary mapping each node to its remaining possible colors. A node with no possible color makes the attempt broken; one possible color for every node makes it a solution. Before guessing, a reducer removes colors ruled out by known choices. For graph coloring, a node fixed to one color rules that color out for its neighbors. Repeat reductions when they create further fixed nodes. section 8.5.2
The backtracker then follows three cases:
- If reduction leaves any node with no possible color, abandon this attempt. section 8.5.2
- If every node has exactly one possible color, return the solution. section 8.5.2
- Otherwise, pick a node with multiple colors, make a separate attempt fixing it to each color, and recursively solve each attempt. The resulting sequence may contain multiple solutions or be empty. section 8.5.2
Listing 8.7 A general backtracking algorithm
sealed class Backtracker<N, C> where N : notnull where C : notnull
{
private readonly IReducer<N, C> reducer;
public Backtracker(IReducer<N, C> reducer) => this.reducer = reducer;
public IEnumerable<ImMulti<N, C>> Solve(ImMulti<N,C> attempt)
{
attempt = reducer.Reduce(attempt);
if (attempt.Keys.Any(k => attempt[k].IsEmpty))
return [];
if (attempt.Keys.All(k => attempt[k].Count == 1))
return [attempt];
N guessKey = attempt.Keys.Where(k => attempt[k].Count > 1).First();
return attempt[guessKey]
.SelectMany(v => Solve(attempt.SetSingle(guessKey, v)));
}
}
The C# implementation puts reduction before both termination checks, then uses SetSingle to branch and SelectMany to combine recursive results. section 8.5.2
Sudoku as graph coloring
Give each of the 81 cells a node and treat digits 1–9 as colors. Connect cells that share a row, column, or three-by-three box; they cannot receive the same digit. Start with the given digits fixed and search over the remaining possibilities. Every node has 20 neighbors but only nine colors, so the earlier simple coloring method cannot get started; reduction and guessing provide a stronger approach. section 8.5 section 8.5.2
Backtracking explores a space of candidate solutions, not necessarily a stored tree. With two unconnected nodes and four colors, there is nothing to prune: the search enumerates all 16 pairs, the Cartesian product of their choices. Constraints make reduction valuable because it can discard entire branches early. That does not remove the exponential worst case for general graph coloring, an NP-complete problem; a useful reducer can nevertheless make practical instances manageable. section 8.5.4 section 8.5.1 section 8.7
The pattern extends beyond colors. In logic programming, unification can produce several possible bindings for a goal; search tries one binding, solves the resulting subproblem, then backtracks to try another. Here, too, the key question is which choices can be ruled out before further recursion. section 10.3 section 10.7
