Lecture 07.2: Backtracking and Local Search for CSPs

When Constraint Propagation (like AC-3) isn't enough to solve a CSP outright, we must resort to search. For CSPs, we use Backtracking Search, a depth-first search that chooses values for one variable at a time and backtracks when a variable has no legal values left.

Improving Backtracking with Heuristics

Instead of assigning variables in a random or static order, we can drastically improve performance using Look-Ahead heuristics:

1. Minimum Remaining Values (MRV) Heuristic

• Concept: Choose the variable with the fewest legal values left in its domain.
• Why it works: Also known as the "Fail-Fast" heuristic, if a variable has 0 or 1 legal values left, MRV selects it immediately. This prunes dead-end branches of the search tree instantly rather than wasting time searching other variables first.

Visual Example: Imagine we have already assigned WA = Red and NT = Green. What should we color next?

MRV immediately selects SA because it is the most constrained and closest to failing.

2. Degree Heuristic

• Concept: Choose the variable that is involved in the largest number of constraints on other unassigned variables.
• Why it works: Often used as a tie-breaker for MRV, it reduces the branching factor on future choices by tackling the most restrictive variables early.

Visual Example: At the very start of the map coloring problem, every territory has 3 remaining values (Red, Green, Blue). MRV ties across all of them. Instead, we look at the constraint graph's connections (degrees):

• WA is connected to 2 territories (NT, SA).
• SA is connected to 5 territories (WA, NT, Q, NSW, V).

The Degree Heuristic selects SA first because assigning it will constrain the most neighbors, drastically reducing the search space right from the beginning.

3. Least Constraining Value (LCV) Heuristic

• Concept: Once a variable is selected, choose the value that rules out the fewest values in the remaining variables.
• Why it works: While MRV tries to fail-fast on variables, LCV tries to succeed by leaving maximum flexibility for subsequent assignments.

Visual Example: Suppose we selected Q to color next, and we have two valid options left: Red or Blue. Let's look at how that impacts its neighbor, SA.

• If we assign Q = Red, it removes Red from SA's domain, leaving SA with 0 options (Failure).
• If we assign Q = Blue, it removes Blue from SA's domain, leaving SA with 1 option (Red).

LCV evaluates the consequences and chooses Blue for Q because it leaves more options open for SA.

Interleaving Search and Inference

Instead of performing inference only as a preprocessing step, we can interleave constraint propagation with the backtracking search.

Forward Checking

Whenever a variable $X$ is assigned a value, Forward Checking looks at all unassigned variables $Y$ that are directly connected to $X$ by a constraint. It prunes any values from $D_Y$ that are incompatible with $X$'s new assignment.

If any domain becomes empty, a Domain Wipe Out (DWO) occurs, and the search immediately backtracks, saving substantial computation.

Concrete Example: The 4-Queens Problem

Let's see how Forward Checking works on the 4-Queens problem (placing 4 queens on a $4 \times 4$ board such that no two queens attack each other).

• Variables: $Q_1, Q_2, Q_3, Q_4$ (representing the row position of the queen in column 1, 2, 3, and 4).
• Initial Domains: $D_i = \{1, 2, 3, 4\}$ for all $i$.

Explanation of Step 2: Assigning $Q_1 = 1$ removes row 1 from the domains of $Q_2, Q_3, Q_4$. It also removes diagonal positions (row 2 for $Q_2$, row 3 for $Q_3$, row 4 for $Q_4$). Explanation of Step 3: Assigning $Q_2 = 3$ removes row 3 from the domains of $Q_3, Q_4$. It also removes diagonal positions from $Q_2=3$ (row 2 for $Q_3$, since $3-1=2$, and row 4 for $Q_3$, since $3+1=4$). This leaves $Q_3$ with an empty domain ($\emptyset$), causing an immediate DWO! The algorithm immediately backtracks.

Maintaining Arc Consistency (MAC)

While Forward Checking is fast, it has a major limitation: it only looks one step ahead (local neighbors). It does not detect inconsistencies that arise between unassigned variables.

Maintaining Arc Consistency (MAC) is strictly more powerful. When a variable $X$ is assigned a value:

1. MAC starts a queue of arcs with $(X_j, X)$ for all unassigned neighbors $X_j$ of $X$.
2. It runs the AC-3 algorithm to recursively propagate constraints throughout the entire network.
3. If any domain becomes empty during this propagation, AC-3 returns false, and MAC backtracks immediately.

Why MAC beats Forward Checking (Australia Map Example)

Imagine the Australia map coloring problem.

• Variables: WA, NT, Q, NSW, V, SA, T (all domains start as $\{Red, Green, Blue\}$).
• Sequence of Assignments:
  1. Assign WA = Red. Forward checking updates:
     • $D(NT) = \{Green, Blue\}$
     • $D(SA) = \{Green, Blue\}$
  2. Assign Q = Green. Forward checking updates:
     • $D(NT) = \{Blue\}$ (since NT is adjacent to Q)
     • $D(SA) = \{Blue\}$ (since SA is adjacent to Q)
     • $D(NSW) = \{Red, Blue\}$

• Forward Checking Failure: Forward checking stops here because all direct neighbors of Q have non-empty domains. It does not notice that both $NT$ and $SA$ are adjacent and have both been reduced to $\{Blue\}$, which is an impossible configuration since they must have different colors!
• MAC Success: When Q is assigned Green, MAC runs AC-3. Since $D(NT)$ changed to $\{Blue\}$, the arc $(SA, NT)$ is evaluated. REVISE checks if there is any value in $D(SA) = \{Blue\}$ that is compatible with $D(NT) = \{Blue\}$. There is none! $Blue$ is removed from $D(SA)$, leaving $D(SA) = \emptyset$ (DWO). MAC detects this failure immediately and backtracks, avoiding a completely useless search tree branch.

Intelligent Backtracking: Backjumping

Standard chronological backtracking is "blind"—it always backs up to the most recently assigned variable. This can lead to massive inefficiencies if that variable has no relation to the failure.

Backjumping addresses this by maintaining a Conflict Set for each variable. The conflict set of a variable $X$ is the set of previously assigned variables that directly caused values in $D_X$ to be eliminated. When a variable's domain wipes out, backjumping jumps back to the most recent variable in its conflict set, completely skipping irrelevant intermediate variables.

Walkthrough: The Tasmania Example

Consider assigning variables in the following order: WA = Red, NT = Green, Q = Blue, NSW = Green, V = Red, and finally T = Red.

• Now we try to assign SA.
• Neighbors of SA are WA (Red), NT (Green), Q (Blue), NSW (Green), and V (Red).
• Every possible color for SA violates a constraint! SA fails.

• Chronological Backtracking: Backtracks to the last assigned variable: T (Tasmania). It tries changing T to Green, then Blue. Each time, it re-attempts to assign SA and fails again. Chronological backtracking wastes time re-coloring Tasmania, even though Tasmania is completely disconnected from the rest of Australia and has absolutely no impact on SA's constraints!
• Backjumping: Computes the conflict set for SA:

$\text{Conflict Set}(SA) = \{WA, NT, Q, NSW, V\}$

The most recent variable in this set is V. Backjumping bypasses T entirely and jumps straight back to V, re-evaluating its color to resolve the conflict.

Local Search for CSPs

When the state space is too large for systematic tree searches, Local Search is a powerful alternative. It works with a complete assignment (every variable has a value, but some constraints are violated) and tries to resolve conflicts by moving to neighboring states.

The Min-Conflicts Algorithm

The core heuristic is to choose a value for a conflicted variable that minimizes the total number of constraint violations.

function MIN-CONFLICTS(csp, max_steps) returns a solution or failure
    inputs: csp, a constraint satisfaction problem
            max_steps, the number of steps allowed before giving up
            
    current = an initial complete assignment for csp (often random or greedy)
    for i = 1 to max_steps do
        if current is a solution for csp then 
            return current
        var = a randomly chosen conflicted variable from csp.VARIABLES
        value = the value v for var that minimizes CONFLICTS(var, v, current, csp)
        set var = value in current
    return failure

Walkthrough: Solving 8-Queens in 2 Steps

Let's see a classic walkthrough of Min-Conflicts solving an 8-Queens problem starting from an initial configuration:

Step 0: Initial complete assignment (with multiple conflicts).
We randomly select a conflicted queen, say the queen in Column 6 (Q6).

Step 1: Evaluate Column 6.
We count the number of conflicts (attacks) if Q6 is placed in each row of Column 6:
- Row 1: 3 conflicts
- Row 2: 2 conflicts
- Row 3: 1 conflict (Minimum!)
- Row 4: 3 conflicts
- ...
We move the queen in Column 6 to Row 3. This resolves several diagonal attacks.

Step 2: Choose another conflicted queen, say in Column 2 (Q2).
Evaluate conflicts for each row in Column 2. Move Q2 to the row with the minimum conflicts.
In just a few local adjustments, all conflicts are reduced to 0, yielding a valid solution!

[!TIP] Why Min-Conflicts is Amazing: For the N-Queens problem, the run time of Min-Conflicts is practically independent of problem size. It can solve a 1,000,000-queens problem in an average of 50 steps! This is why it is used in complex real-world scheduling (like for the Hubble Space Telescope), reducing weekly scheduling times from 3 weeks to 10 minutes.