In a CSP with 10 variables, variable A has only 1 legal value remaining while variable B has 8 legal values remaining. The MRV heuristic assigns which variable next, and why?
AVariable B, because more legal values means more flexibility to find a solution
BVariable A, because a variable with fewer legal values is most likely to cause failure soon, and it is better to detect failure early
CEither variable — MRV only matters when breaking ties between equally constrained variables
DVariable B, because exploring more options first reduces backtracking later
MRV selects the variable with the fewest remaining legal values — variable A with 1 remaining value. The intuition is 'fail early': if A has only one valid value and it conflicts with the current partial assignment, you want to discover that failure immediately rather than after assigning B and all other variables. Backtracking is expensive; the earlier you detect a dead end, the fewer nodes you explore. Variable A is the 'most constrained' variable, and assigning it first maximizes pruning of the search tree.
Question 2 Multiple Choice
A backtracking search without heuristics explores 1,000,000 nodes on a CSP. After adding the MRV heuristic, the same problem is solved in 500 nodes. What has the heuristic actually changed?
AThe heuristic changed the set of valid solutions found — it finds a better solution in fewer steps
BThe heuristic changed the order in which variables are assigned, causing failures to be detected earlier and pruning large subtrees
CThe heuristic changed the constraint definitions, making the problem easier to solve
DThe heuristic reduced domain sizes by eliminating illegal values before search begins
MRV is an ordering heuristic — it changes nothing about the problem's constraints, domains, or the set of valid solutions. It only changes which variable is assigned next. By tackling the most constrained variable first, failures are detected as early as possible in the search tree. When a variable with few legal values runs out of options, the algorithm backtracks immediately rather than continuing to assign other variables that could never lead to a solution. This collapses exponential subtrees, reducing node count dramatically while guaranteeing the same correct solutions.
Question 3 True / False
Backtracking search with MRV is not expected to find a solution if one exists — the heuristic ordering may cause it to give up and report failure incorrectly.
TTrue
FFalse
Answer: False
Backtracking search is complete — if a solution exists, it will find one. MRV is an ordering heuristic that changes which variable is assigned next but never skips a variable or permanently removes a value from consideration. Backtracking ensures that when a dead end is reached, the algorithm backtracks to a previous decision point and tries alternative values. MRV affects efficiency (how many nodes are explored), not completeness (whether a solution is found if one exists).
Question 4 True / False
The least constraining value (LCV) heuristic for value ordering selects the value that rules out the fewest choices for neighboring unassigned variables.
TTrue
FFalse
Answer: True
LCV is designed to keep options open for the rest of the search. When assigning a value to the current variable, choosing a value that eliminates many values from neighboring domains makes those neighbors harder to assign — possibly causing failures that force backtracking. LCV selects the most cooperative value: the one that imposes the least restriction on remaining variables, giving the overall search the best chance of succeeding without backtracking. LCV complements MRV: MRV chooses which variable to assign; LCV chooses which value to try first for that variable.
Question 5 Short Answer
Explain why 'fail early' is the core principle behind the MRV heuristic, and how it reduces the total number of nodes explored.
Think about your answer, then reveal below.
Model answer: MRV selects the variable with the fewest remaining legal values because that variable is most likely to fail soon. If it has only one value left and that value conflicts, failure is detected immediately. Without MRV, the algorithm might assign many other variables first — exploring a large subtree — only to discover that the constrained variable has no legal values and all that work must be undone. By assigning the most constrained variable first, any failure causes immediate backtracking, pruning every assignment that would have followed it. This fail-early strategy collapses exponential subtrees at their roots rather than exploring them fully before detecting failure.
The key insight is that backtracking's cost is not detecting failure — it is the wasted work of exploring subtrees that are doomed from the beginning. MRV minimizes wasted work by making the search tree fail as shallowly as possible. In map-coloring, assigning the most tightly constrained region first means failures at that region immediately eliminate large portions of the search space — the difference can be from millions of nodes down to hundreds.