Questions: Backtracking and Constraint Satisfaction

Question 1

A backtracking algorithm is solving an 8-Queens problem. After placing queens in rows 1–5, it finds that every column in row 6 conflicts with an existing queen. What does backtracking do next?

• A. It tries all column assignments for rows 7 and 8 before giving up on the current partial solution
• B. It immediately backtracks to row 5 and tries the next unused column there
• C. It restarts the search from row 1 with a different initial column
• D. It marks the problem unsolvable and terminates

Answer: (B)

The power of backtracking is immediate abandonment of a branch the moment a constraint cannot be satisfied. Since no valid placement exists for row 6, every extension of this partial solution is guaranteed to fail — there is no point exploring rows 7 or 8. The algorithm backtracks to the most recent decision (row 5) and tries the next option. Option A describes brute-force generation, not backtracking; the whole point is to prune rather than enumerate.

Question 2

In a CSP with 9 variables, variable A has 4 remaining legal values, variable B has 1, and variable C has 7. Which should the MRV (most constrained variable) heuristic assign next?

• A. Variable C, because more options provide greater flexibility to satisfy constraints later
• B. Variable A, as a balanced middle choice
• C. Variable B, because it has the fewest remaining legal values
• D. Whichever variable appears first in the problem's variable list

Answer: (C)

MRV stands for 'minimum remaining values' — also called 'fail-first' because you assign the variable most likely to hit a dead end. Variable B has only one legal value: assigning it now costs almost nothing (there is only one option) and immediately reveals whether this branch survives. If B has zero legal values, the algorithm would backtrack right away instead of wasting effort assigning A and C first. Option A reverses the logic: a variable with many options can be assigned later without risk.

Question 3

Backtracking is more efficient than brute-force enumeration because it checks constraints after each partial assignment rather than only after all variables have been assigned.

• T. True
• F. False

Answer: True

This is the defining efficiency gain of backtracking. By checking constraints at each step, the algorithm detects infeasible partial solutions early and prunes entire subtrees from consideration. A brute-force approach generates all complete assignments and checks each one — exponential in the number of variables. Backtracking avoids enumerating every extension of a failed partial assignment.

Question 4

Constraint propagation in backtracking mainly updates the domain of the variable currently being assigned; it leaves most other variables' domains unchanged.

• T. True
• F. False

Answer: False

Constraint propagation does the opposite: when you assign a value to one variable, it removes that value — and any values made illegal by the assignment — from the domains of all constrained neighbor variables. This forward propagation can eliminate values from many variables simultaneously, detecting future failures early without even trying to assign those variables. If propagation reduces a neighbor's domain to zero values, the algorithm backtracks immediately.

Question 5

Explain why checking constraints on partial assignments — before a complete solution is formed — makes backtracking more efficient than generating all complete assignments and checking each one.

Model answer: Each partial assignment that violates a constraint represents the root of a subtree of complete assignments, all of which are guaranteed to also violate that constraint. By detecting the violation in the partial assignment, backtracking prunes the entire subtree at once rather than exploring every node within it. In an N-Queens problem, detecting a conflict in row 3 avoids generating all placements for rows 4 through N under that partial configuration — potentially billions of nodes pruned from a single early detection.

The key insight is that constraints are inherited downward through partial solutions: if partial assignment P violates a constraint, every complete assignment extending P also violates it. Brute force ignores this structure; backtracking exploits it. Combined with heuristics like MRV and constraint propagation, this can reduce exponential search to near-linear in well-constrained problems like Sudoku.