Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 46 ยท Constraint Satisfaction

Backtracking Search for CSPs

Solve constraint satisfaction problems with backtracking search: assignment-by-assignment search, MRV and degree variable ordering, LCV value ordering and measured backtrack counts.

Once a problem is written as a CSP, the simplest complete solver is backtracking search. It builds a solution one variable at a time, checks the constraints after every choice, and when it reaches a dead end it undoes the most recent choice and tries something else. It is plain depth-first search, specialized in two ways that matter a great deal: it assigns only one variable per level, and it rejects a partial assignment the moment it breaks a constraint.

The basic version is already far better than brute force. But the real lesson is how much further two cheap ideas push it: choose which variable to assign next with a smart rule, and choose which value to try first with another. You will implement both and measure the effect by counting backtracks.

Search over assignments

A general search algorithm for CSPs would branch on every variable and every value at every node, which wastes enormous effort because the order of assignment does not matter. Instead:

  • A node is a partial assignment.
  • At each node choose one unassigned variable, then branch on its values.
  • Skip any value that conflicts with the variables already assigned.
  • If a variable has no legal value left, return failure; the caller will try its next value.

With n variables and domain size d, the tree has depth n and branching factor at most d, so there are d^n leaves at most, not n! * d^n as there would be if the order of variables mattered.

graph TD
    R["Start: nothing assigned"] --> A["Q1 = row 0"]
    R --> B["Q1 = row 1"]
    A --> A1["Q2 = row 2"]
    A --> A2["Q2 = row 3"]
    A1 --> X1["Q3: no legal row<br/>dead end, backtrack"]
    A2 --> A21["Q3 = row 1"]
    A21 --> X2["Q4: no legal row<br/>dead end, backtrack"]

Part of the backtracking tree for 4-queens (one queen per column, values are rows). A node with no legal value sends the search back to the previous choice.

The algorithm

TEXT
backtrack(assignment):
    if assignment is complete: return it
    var = pick an unassigned variable
    for value in ordered legal values of var:
        add var = value
        result = backtrack(assignment)
        if result is not failure: return result
        remove var = value
    return failure

Two functions are left open, and they are the subject of this lesson: how to pick the variable and in which order to try the values.

Watching backtracking work

Here is the plain version on 4-queens, with variables in a fixed order. Each variable is a column and its value is the row of the queen in that column. The trace prints every assignment and every undo.

Python Tracing plain backtracking on 4-queens

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the indentation as depth. Whenever a column runs out of legal rows the function simply returns False, which makes the previous column undo its row and try the next one. That is the whole mechanism.

Choosing the next variable

The default is to take variables in a fixed order. This ignores a crucial fact: a variable with only one or two legal values left is the most likely to fail soon, so we should assign it now and find out early.

  • Minimum remaining values (MRV) picks the variable with the fewest legal values given the assignments so far. It is called the fail-first heuristic: if a branch is doomed, discover that near the root, where pruning saves a whole subtree.
  • Degree heuristic is a tie-breaker: among variables with equally few values, choose the one involved in the most constraints with unassigned variables. It constrains the future as much as possible. It is especially useful at the start, when every variable has a full domain and MRV alone cannot decide.

Choosing the order of values

After picking the variable, you must try its values in some order. Here the opposite philosophy applies: fail-last. The least constraining value (LCV) heuristic tries first the value that rules out the fewest choices for neighboring variables, keeping the most options open. If a solution exists, you want to find it without exploring bad branches.

The asymmetry is worth remembering. For variables, pick the most constrained one (all of them must eventually be assigned, so detect trouble early). For values, pick the least constraining one (you only need one value to work, so choose the one most likely to succeed).

Measuring the heuristics

The next program implements all four combinations and counts two numbers: the number of assignments made (nodes in the search tree) and the number of backtracks (assignments undone). The solver stops after 20,000 assignments so that a hopeless run does not hang the page.

Python Comparing variable and value ordering

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The pattern is striking. On Australia no heuristic is needed: the map is easy and every strategy needs exactly 7 assignments and no backtracking. On 12-queens, MRV cuts the work compared with fixed order from 261 assignments to 153, and adding LCV brings it down to 51, about a fifth of the original. On the two random graph-colouring puzzles the fixed order is still running when it hits the 20,000-assignment cap: it gets stuck exploring a doomed subtree below an early bad choice, and chronological backtracking cannot see that the real mistake was made far above. MRV finds a solution straight away, making exactly one assignment per variable.

Notice that MRV and MRV + degree give identical numbers on the queens and the graphs here. In these examples the tie-breaker rarely changes which variable is chosen. Degree matters most in problems whose constraint graph is irregular and where many variables tie at the start; it never hurts, so it is the usual default.

Warning: A heuristic is not a guarantee. MRV and LCV change the order of the search, not what is correct, so the solver still finds a solution whenever one exists. But on some instances a heuristic order can be slower than a plain one. Measure on problems like yours.

Where backtracking is still weak

Plain backtracking checks constraints only against variables that are already assigned. It does not notice that an unassigned variable has just lost all its legal values until it gets around to choosing that variable. In the failed runs above, the search spent tens of thousands of assignments deep in branches where some future variable was already doomed.

The cure is to look ahead after each assignment and remove values that can no longer work. This is called inference or constraint propagation, and it is the topic of the next lesson. Combined with MRV it turns problems that look impossible into trivial ones.

Two more ideas are worth knowing by name:

  • Intelligent backtracking (conflict-directed backjumping) jumps back to a variable that actually caused the failure, instead of the most recent one.
  • Nogood learning records the reason for a failure so the same mistake is never repeated, an idea that powers modern SAT solvers.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is a node in the backtracking search tree for a CSP?

    Each node is a partial assignment. Going down one level assigns one more variable, and a dead end is a node where some variable has no legal value.
  2. 2. What does the MRV heuristic choose?

    Minimum remaining values is the fail-first rule: assign the most constrained variable next, so doomed branches are discovered early.
  3. 3. Why is the least-constraining-value rule a fail-last strategy?

    You only need one value to work, so you try the one most likely to succeed: the one that leaves neighbors the most remaining choices.
  4. 4. When is the degree heuristic mainly used?

    Degree prefers the variable involved in the most constraints with unassigned variables, which is useful when MRV leaves a tie, especially at the start.
  5. 5. What is the main weakness of plain backtracking that constraint propagation fixes?

    Looking ahead and pruning domains after each assignment detects dead ends earlier, often avoiding enormous subtrees.

Summary

  • Backtracking search builds a partial assignment variable by variable and undoes the last choice at a dead end.
  • Assignment order does not change the solutions, so the solver is free to choose which variable to assign next.
  • MRV (fail-first) picks the most constrained variable; the degree heuristic breaks ties.
  • LCV (fail-last) tries the value that leaves neighbors the most freedom.
  • In the measured runs, good ordering cut the work on 12-queens to about a fifth and solved graph-colouring puzzles on which a fixed order gave up.
  • Plain backtracking cannot see doomed future variables; inference, covered next, fixes that.

Next: Constraint Propagation: Forward Checking and AC-3.