Smart Heuristics for CSPs

Unit 4: Optimization and Constraint Satisfaction — Section 4.5

Backtracking search with arc consistency (Section 4.4) is already far more powerful than naive enumeration. But the algorithm still faces a critical choice at every step: which variable to assign next, and which value to try first. A bad choice here can send the search deep into a dead-end branch, wasting time that good heuristics could have saved. Intelligent ordering can reduce search by factors of 100 to 1,000.

In Section 4.4, the backtracking algorithm called select_unassigned_variable() and order_domain_values() as abstract helper functions. This section defines those functions using three proven heuristics: MRV, degree heuristic, and LCV.

The Variable Selection Problem

At each step of backtracking, multiple variables remain unassigned. Choosing which one to assign next is a free decision — the algorithm’s correctness does not depend on this choice. But efficiency depends on it enormously.

The guiding principle for variable selection is fail first: choose the variable most likely to cause a failure. Detecting failure early means backtracking early, before wasted effort on downstream assignments.

Minimum Remaining Values (MRV)

Minimum Remaining Values (MRV) Heuristic: A variable selection strategy that chooses the unassigned variable with the fewest legal values remaining in its domain. Also called the "most constrained variable" or "fail-first" heuristic.

Why MRV Works

A variable with only one legal value left will cause failure if that value is wrong — and we will discover this immediately, triggering an early backtrack. A variable with many legal values left is unlikely to cause immediate failure and can be assigned later, when the search has narrowed down the options naturally.

By always assigning the most constrained variable first, we put the "hardest" decisions at the top of the search tree, where backtracking is cheapest.

MRV Variable Selection:

Current state of an Australian map coloring problem (partial assignment: WA=Red, NT=Green):

Q: domain = {Red, Blue} → 2 values
NSW: domain = {Red, Green, Blue} → 3 values
V: domain = {Red, Green, Blue} → 3 values
SA: domain = {Blue} → 1 value
T: domain = {Red, Green, Blue} → 3 values

MRV selects SA (only 1 legal value remaining).

Reasoning: SA is the most constrained variable. Assigning it now either succeeds immediately (Blue is valid) or fails immediately (Blue is not valid, triggering an early backtrack). Either way, we learn something useful without committing to additional assignments.

MRV Compared to Arbitrary Ordering

A dramatic illustration comes from the n-queens problem. Arbitrary variable ordering requires exploring thousands of states to place 8 queens. MRV ordering (always assign the column with fewest valid row options) reduces this to tens of states on the same problem.

Algorithm	8-Queens Steps	100-Queens Steps
Naive backtracking	~876	~10^50
+ Forward checking	~144	~10^25
+ MRV + LCV	~39	~1,000
+ MAC (full arc consistency)	~15	~200

Algorithm

8-Queens Steps

100-Queens Steps

Naive backtracking

~876

~10^50

+ Forward checking

~144

~10^25

+ MRV + LCV

~39

~1,000

+ MAC (full arc consistency)

~15

~200

The Degree Heuristic

MRV requires knowing how many legal values each variable has — which in turn depends on which values have been propagated away by constraint checking. But when multiple variables tie for fewest legal values, a tiebreaker is needed.

Degree Heuristic: A variable selection tiebreaker that chooses the unassigned variable involved in the greatest number of constraints with other unassigned variables. Also called the "most constraining variable" heuristic.

Why the Degree Heuristic Works

A variable constrained by many other unassigned variables has more downstream impact. Assigning it now reduces the domains of more future variables, increasing the chance of detecting contradictions early.

Degree Heuristic Tiebreaking:

Suppose Q and NSW both have 2 legal values remaining (tied on MRV).

Q is constrained with: NT, SA, NSW → 3 unassigned neighbors
NSW is constrained with: Q, SA, V → 3 unassigned neighbors (also tied)

Suppose instead V has 2 legal values but only 2 unassigned neighbors. The degree heuristic would choose Q or NSW over V, since they participate in more active constraints.

In practice, the degree heuristic is applied first at the start of a problem (before any assignments, when all variables have full domains) and used as a tiebreaker for MRV throughout.

Least Constraining Value (LCV)

Variable selection heuristics (MRV and degree) tell us which variable to assign next. Value ordering tells us which value to try first for that variable.

The guiding principle for value ordering is the opposite of fail-first: fail last. We want to try the value most likely to succeed — the value that preserves the most options for future variables.

Least Constraining Value (LCV) Heuristic: A value ordering strategy that tries values in order of how many values they eliminate from neighboring variables' domains. The value that rules out the fewest options is tried first.

Why LCV Works

Consider that we will try every consistent value for the selected variable anyway if needed. If a value rules out many options for neighboring variables, it is more likely to lead to a dead end, requiring backtracking. By trying the least constraining value first, we maximize the chance that the first value we try leads to a complete solution.

LCV and MRV have opposite philosophies but complementary effects:

MRV (fail-first for variables): Choose the variable that will most quickly reveal failures
LCV (fail-last for values): Choose the value that most keeps future options open

LCV Value Ordering:

Assign variable SA (domain = {Blue, Green}).

Neighbor domains before assignment: * Q: {Red, Blue} (constraints: SA ≠ Q) * V: {Red, Blue, Green} (constraints: SA ≠ V) * NSW: {Red, Blue, Green} (constraints: SA ≠ NSW)

Option 1: SA = Blue * Remove Blue from Q’s domain: {Red, Blue} → {Red} (1 value removed from Q) * Remove Blue from V’s domain: no Blue in V’s constraint…

Wait — let’s count correctly. SA ≠ Q means we remove whatever SA is from Q’s domain: * SA = Blue → remove Blue from Q → Q: {Red} (removes 1 value) * SA = Green → remove Green from Q → Q: {Red, Blue} (removes 0 values from Q; Green wasn’t there anyway)

Now check all neighbors: * SA = Blue: removes Blue from each neighbor that has it → Q loses 1, V loses 1, NSW loses 1 → total: 3 values ruled out * SA = Green: removes Green from each neighbor → V loses 1, NSW loses 1 → total: 2 values ruled out

LCV selects SA = Green (only 2 values ruled out across all neighbors, vs. 3 for Blue).

When LCV Matters Most

LCV has the greatest impact when:

The remaining search tree is large (many unassigned variables with large domains)
The selected variable has many neighbors
Choosing the wrong value would cascade and eliminate many options

For problems where the domain is small or few neighbors exist, LCV’s benefit is negligible. In practice, the combination of MRV + degree heuristic + LCV is the standard configuration for backtracking CSP solvers.

Combining All Three Heuristics

The three heuristics work together in a natural sequence:

Smart Backtracking with All Three Heuristics:

Select variable: Use MRV — choose the unassigned variable with the fewest legal values
Break ties: Use degree heuristic — among variables with equal MRV, choose the one with the most constraints on unassigned neighbors
Order values: Use LCV — try values in order from least to most constraining for neighbors
Propagate: After each assignment, run forward checking (or full MAC with AC-3)
Detect failure: If any domain becomes empty during propagation, backtrack immediately

def smart_backtrack(assignment, csp):
    if len(assignment) == len(csp.variables):
        return assignment

    # Step 1 & 2: MRV with degree heuristic tiebreaking
    var = select_mrv_variable(csp, assignment)

    # Step 3: LCV value ordering
    values = order_by_lcv(var, assignment, csp)

    for value in values:
        if csp.is_consistent(var, value, assignment):
            assignment[var] = value

            # Step 4 & 5: Forward checking / MAC
            saved_domains = copy_domains(csp)
            if propagate_constraints(var, value, csp):
                result = smart_backtrack(assignment, csp)
                if result is not None:
                    return result

            # Undo assignment and domain changes
            del assignment[var]
            restore_domains(csp, saved_domains)

    return None

Performance Comparison

The cumulative impact of these heuristics is striking. Each addition independently reduces search:

Algorithm Configuration	8-Queens Backtracks	100-Queens Backtracks
Backtracking only	~876	astronomical
+ Forward checking	~144	~10^25
+ MRV + LCV	~39	~1,000
+ MAC (full AC-3 after each step)	~15	~200

Algorithm Configuration

8-Queens Backtracks

100-Queens Backtracks

Backtracking only

~876

astronomical

+ Forward checking

~144

~10^25

+ MRV + LCV

~39

~1,000

+ MAC (full AC-3 after each step)

~15

~200

The heuristics in this section are general-purpose — they work on any CSP, not just map coloring or Sudoku. This is the power of the CSP framework: a small investment in formulating a problem as a CSP gives you access to decades of research on how to solve CSPs efficiently. You get MRV, LCV, AC-3, and more for free.

When Heuristics Help Most

These heuristics provide the greatest benefit when:

The problem is highly constrained (domains shrink quickly after assignments)
Many variables share constraints (rich constraint graph)
The solution, if it exists, is hard to find (many invalid partial assignments)

For loosely constrained problems — where almost any assignment works — the overhead of computing MRV and LCV may outweigh their benefit. But for realistic scheduling, configuration, and puzzle-solving problems, these heuristics are essential.

Consider the Sudoku puzzle. Which variable would MRV select first in a puzzle where one cell already has only one legal value? Which value would LCV select for that cell?

Now consider the opposite: a cell in an empty corner of the grid, with all 9 values still in its domain. Why does MRV tell us to avoid assigning this cell until later in the search?

The three heuristics — MRV, degree, and LCV — transform backtracking from a brute-force enumeration into an intelligent search. They embody a deep principle of problem solving: solve the hardest parts first, and keep your options open as long as possible. This principle applies far beyond CSPs — you will see it again in every planning and scheduling algorithm you encounter.

Practice applying MRV, degree heuristic, and LCV to a constraint satisfaction problem.

Next: 4.6 Choosing the Right Tool →

Based on the UC Berkeley CS 188 Online Textbook by Nikhil Sharma, Josh Hug, Jacky Liang, and Henry Zhu, licensed under CC BY-SA 4.0.

This work is licensed under CC BY-SA 4.0.