graph coloring by search
Picture a map where you must color each country so that no two countries sharing a border get the same color, using as few colors as possible. Abstract the countries to dots (vertices) and the shared borders to lines (edges), and you have graph coloring: assign a color to each vertex so that the two endpoints of every edge differ. The k-coloring question asks whether this can be done with only k colors.
Searching for a coloring is backtracking on a CSP. The variables are the vertices, the domain of each is the k colors, and each edge is a constraint saying its two endpoints must differ. Process the vertices in some order; for the current vertex, try each color, and before recursing check that it conflicts with no already-colored neighbor. If a color is legal, assign it and recurse to the next vertex; if no color is legal, backtrack to the previous vertex and try its next color. The feasibility check (does this color clash with a neighbor?) prunes hard: a bad early color can make a whole region uncolorable, and detecting that immediately cuts off every completion below it. Good vertex ordering helps a lot — coloring the most-constrained vertices first tends to fail fast and prune more.
Graph coloring is a classic NP-complete problem (deciding 3-colorability is already NP-complete), so no known algorithm colors every graph quickly, and the backtracking search is exponential in the worst case. Yet it is enormously useful in practice for exactly the structured cases that arise: register allocation in compilers (variables that are simultaneously live must get different registers), scheduling (events that overlap need different time slots), and frequency assignment all reduce to coloring, and the pruned search handles real instances that the 2^n-style enumeration of all colorings never could.
A 4-cycle A-B-C-D-A is 2-colorable: color A red, B (neighbor of A) green, C (neighbor of B) red, D (neighbor of C and A) must differ from both red and green's positions — green works. A triangle A-B-C is not 2-colorable: A red, B green, C neighbors both, no color of the two left, so the search backtracks through every option and reports failure — you need 3 colors.
Vertices are variables, colors are the domain, edges are not-equal constraints — a textbook CSP solved by pruned backtracking.
A graph is 2-colorable exactly when it is bipartite, which a single BFS/DFS decides in linear time — but for k = 3 and up, coloring is NP-complete and the search can blow up; the easy case is special, not the rule.