Three questions make backtracking fast: which variable next, which value first, and what can we infer after each assignment. Good answers turn exponential searches into near-linear ones.

Heuristic	Rule	Intuition
MRV — minimum remaining values	Pick the variable with the fewest legal values left	Fail first: tackle the most constrained variable before it becomes impossible
Degree heuristic	Tie-break by the variable involved in the most constraints with unassigned variables	Reduces future branching (SA first in Australia)
LCV — least constraining value	Try the value that rules out the fewest choices for neighbours	Fail last: leave maximum flexibility — we only need one solution

Inference: forward checking and arc consistency

Python

def solve(n, mrv=False, forward_check=False):
    nodes = 0
    def backtrack(assign, domains):
        nonlocal nodes
        if len(assign) == n:
            return dict(assign)
        free = [c for c in range(n) if c not in assign]
        var = min(free, key=lambda c: len(domains[c])) if mrv else free[0]
        for row in sorted(domains[var]):
            if any(row == r or abs(row - r) == abs(var - c) for c, r in assign.items()):
                continue
            nodes += 1
            assign[var] = row
            new = domains
            if forward_check:              # prune neighbours' domains; empty domain → dead end
                new = {c: d if c in assign else {x for x in d if x != row and abs(x - row) != abs(c - var)}
                       for c, d in domains.items()}
            if all(new[c] for c in new if c not in assign) and (res := backtrack(assign, new)):
                return res
            del assign[var]
        return None
    backtrack({}, {c: set(range(n)) for c in range(n)})
    return nodes

print(solve(16))                                  # 10052 ← plain backtracking
print(solve(16, forward_check=True))              # 7560
print(solve(16, mrv=True, forward_check=True))    # 44 ← MRV + forward checking

AC-3

Queue every arc
For each binary constraint between X and Y add both arcs (X, Y) and (Y, X).
Revise
Pop an arc (X, Y); delete each value of X that has no compatible value in Y's domain.
Propagate
If X's domain shrank, re-queue every arc (Z, X) for neighbours Z ≠ Y.
Stop
When the queue is empty (arc-consistent) — or a domain becomes empty (no solution).

Python

from collections import deque

def ac3(domains, constraints):
    """constraints: {(X, Y): predicate(x, y)} — both directions must be listed."""
    queue = deque(constraints)
    while queue:
        x, y = queue.popleft()
        ok = constraints[(x, y)]
        removed = {vx for vx in domains[x] if not any(ok(vx, vy) for vy in domains[y])}
        if removed:
            domains[x] -= removed
            if not domains[x]:
                return False                                  # inconsistency detected
            queue.extend((z, w) for (z, w) in constraints if w == x and z != y)
    return True

# X < Y < Z with values 1..3: propagation alone solves it
doms = {v: {1, 2, 3} for v in "XYZ"}
lt, gt = (lambda a, b: a < b), (lambda a, b: a > b)
print(ac3(doms, {("X", "Y"): lt, ("Y", "X"): gt, ("Y", "Z"): lt, ("Z", "Y"): gt}), doms)   # True {'X': {1}, 'Y': {2}, 'Z': {3}}

# Australia after WA = red, Q = green: forward checking leaves NT = SA = {blue} and doesn't notice…
edges = [("WA", "NT"), ("WA", "SA"), ("NT", "SA"), ("NT", "Q"), ("SA", "Q"), ("SA", "NSW"),
         ("SA", "V"), ("Q", "NSW"), ("NSW", "V")]
ne = lambda a, b: a != b
cons = {**{(a, b): ne for a, b in edges}, **{(b, a): ne for a, b in edges}}
doms = {v: {"red", "green", "blue"} for v in ["WA", "NT", "SA", "Q", "NSW", "V", "T"]}
doms["WA"], doms["Q"] = {"red"}, {"green"}
print(ac3(doms, cons))       # False ← …AC-3 proves there is no solution with this partial assignment

AC-3 runs in O(c·d³) for c arcs and domain size d. Arc consistency alone doesn't always find a solution (map colouring with 2 colours on a triangle stays arc-consistent), but combined with search it removes most dead ends early.

Local search for CSPs: min-conflicts

Start from a complete (inconsistent) assignment; repeatedly pick a conflicted variable and give it the value with the fewest conflicts. Remarkably effective on large, loosely constrained problems — started from a greedy initial assignment it solves the million-queens problem in about 50 steps on average, and it is used for real-time rescheduling.

Python

import random

def min_conflicts(n, max_steps=1000):
    rows = [random.randrange(n) for _ in range(n)]
    def conflicts(c, r):
        return sum(1 for c2 in range(n) if c2 != c and (rows[c2] == r or abs(rows[c2] - r) == abs(c2 - c)))
    for step in range(max_steps):
        bad = [c for c in range(n) if conflicts(c, rows[c])]
        if not bad:
            return rows, step
        c = random.choice(bad)
        rows[c] = min(range(n), key=lambda r: (conflicts(c, r), random.random()))   # random tie-break
    return None, max_steps

random.seed(0)
rows, steps = min_conflicts(40)
print(steps)     # 152 ← steps to solve 40-queens from a random start

Exploiting problem structure

Structure	Technique	Cost
Independent sub-problems (Tasmania)	Solve connected components separately	`O(dᶜ · n/c)` instead of `O(dⁿ)`
Tree-structured constraint graph	Order topologically, make arcs consistent backwards, assign forwards	`O(n·d²)` — linear in `n`
Nearly a tree	Cutset conditioning: assign a small cycle cutset, solve the remaining tree	`O(dᶜ · (n − c)·d²)`
Symmetric values	Symmetry-breaking constraints (e.g. NT < SA < WA)	Removes equivalent solutions

Explain MRV and LCV — why is one 'fail first' and the other 'fail last'?

Forward checking vs arc consistency?

What is the time complexity of AC-3?