The idea: search that undoes its latest choice
A constraint satisfaction problem (CSP) has variables, a domain of possible values for each, and constraints that say which combinations are allowed. Coloring the map of Australia is the classic example: the 7 regions are the variables, each domain is {R, G, B}, and every shared border is a constraint "these two regions differ". Tasmania (T) borders nobody, so any color works for it.
The canvas shows the same graph. The chips under each region are its current domain: a grey chip is a value that has been removed. The right panel is the search: one row per level, the variable chosen at that level, and what happened to each of its values (✓ in use, ✗ tried and failed, – not in the domain any more).
Backtracking search
Backtracking search is depth-first search over partial assignments. It picks an unassigned variable, tries its values in order, and checks each one against the neighbours that already have a color. If a value fits, it goes one level deeper. If a variable has no value left, that is a dead end: the search goes back to the level above and tries that variable's next value.
BACKTRACK(assignment):
if every variable is assigned: return assignment
X = choose an unassigned variable
for each value v in DOMAIN(X):
if v is consistent with the assignment:
assign X = v (and prune / propagate)
if BACKTRACK(assignment) succeeds: return it
undo X = v (and the pruning)
return failure (dead end: go back up)
With the static order WA, NT, NSW, Q, V, SA, T, the search colors WA = R, NT = G, NSW = R, Q = B and V = G, then finds SA bordered by all three colors. V = B fails the same way, Q and V run out of values, and the search goes all the way back to NSW = G, which works. That takes 11 assignments, 4 of them undone (Demo 1: plain backtracking, dead end at SA).
Forward checking
Plain backtracking only notices a problem when it reaches the variable that has no value. Forward checking looks ahead one step: after X = v, it removes v from the domains of X's unassigned neighbours. If some domain becomes empty, the assignment is undone at once.
In the same order, Q = B now leaves SA with an empty domain (∅), so the search undoes Q = B without ever trying V. It solves the map in 9 assignments (Demo 2: forward checking finds it earlier).
Choosing the variable: MRV and degree
The order of the variables matters a lot. The minimum remaining values heuristic (MRV, also called "most constrained variable" or "fail first") picks the variable with the fewest values left in its domain. It needs forward checking to know the domain sizes. When several variables tie, the degree heuristic picks the one with the most unassigned neighbours.
At the start every region has 3 values, so the degree heuristic decides: SA borders 5 regions and goes first. After SA = R, every neighbour has 2 values left; NT, Q and NSW tie on degree 2 as well, and NT comes first in the static order. From then on every mainland region has exactly one value left when its turn comes. The map is solved in 7 assignments, one per region, with no backtracking (Demo 3: MRV picks SA first). Values are still tried in the order R, G, B; a value-ordering heuristic such as least constraining value is not used here.
Arc consistency and AC-3
An arc X → Y is consistent if every value left in X's domain has some value in Y's domain that satisfies the constraint between them. AC-3 keeps a queue of arcs. It takes one arc X → Y, removes the values of X that have no support in Y (revise), and if X lost anything, puts every arc Z → X back on the queue, because Z may have lost its support too.
AC-3(queue):
while queue is not empty:
(X, Y) = queue.pop()
if REVISE(X, Y): (removed a value from X)
if DOMAIN(X) is empty: return failure
for each neighbour Z of X, Z ≠ Y:
queue.add((Z, X))
return success
Running AC-3 after every assignment is called MAC (maintaining arc consistency). The first wave of arcs, the ones into the variable just assigned, does the same work as forward checking. The difference is what comes after: a removal travels on.
The page's AC-3 strategy is MRV + MAC. After SA = R and NT = G, AC-3 pins every other mainland region to a single value, and their assignments are forced (Demo 4: AC-3 propagation). On this small map that saves no assignments compared with MRV, but it saves the search from ever making a choice that has to be undone; on harder problems the gap is large.
Counting the work
The table on the canvas counts assignments (values actually given to a variable) for each strategy and number of colors, from the same search the animation runs:
| strategy | 3 colors | 2 colors (no solution) |
|---|---|---|
| plain backtracking | 11 | 12 |
| + forward checking | 9 | 4 |
| + MRV heuristic | 7 | 4 |
| AC-3 (MAC) | 7 | 2 |
Plain backtracking does more than its count suggests: every value it rejects needs a check against the colored neighbours. AC-3 does extra work of its own: it counts the arc checks it makes, which are cheap compared with a wrong assignment deep in the search.
When there is no solution
With 2 colors the map cannot be colored: WA, NT and SA all border each other, and a triangle (any odd cycle) needs 3 colors. Backtracking cannot know that in advance; it has to try every branch before it may report failure. Plain search makes 12 assignments, all undone (Demo 5: 2 colors, unsolvable). With AC-3, SA = R leaves WA and NT with only G each, and the arc NT → WA then empties NT. SA = G fails the same way, so failure is proved after 2 assignments (Demo 6: 2 colors, AC-3 fails fast).
Map coloring is the same problem as graph coloring, which colors greedily without undoing anything and so may use more colors than needed. The N-Queens page uses the same backtracking pattern, one queen per row. Game-tree search in Minimax is another depth-first search over choices.
What the page leaves out
Real CSP solvers add value ordering (least constraining value), smarter backtracking that jumps straight to the variable that caused the conflict (backjumping, conflict-directed backjumping), learning of no-goods, stronger consistency (path consistency, k-consistency), global constraints such as all-different, symmetry breaking (here every solution has 5 color-swapped twins), and local search such as min-conflicts for very large problems. The page also runs AC-3 only during the search, not once before it, because on this map with all domains full it would remove nothing.