Does MRV choose a value or a variable?

It chooses the next unassigned variable. Value selection is separate.

What happens if a domain is empty?

The current search branch has no solution under the maintained constraints and requires failure handling or backtracking.

Does MRV always make search faster?

No. It is a useful heuristic, but performance depends on the instance, propagation, tie rules, and the cost of maintaining legal-value counts.

AI Glossary / Graphs and symbolic AI / Intermediate

Minimum-remaining-values

Definition

Minimum-remaining-values, usually abbreviated MRV, is a variable-selection heuristic for constraint satisfaction. It chooses an unassigned variable with the fewest currently legal values. The aim is to address the most constrained choice early, exposing failure before spending effort on choices that still have many alternatives.

What it means

A constraint problem has variables, possible values called domains, and rules restricting combinations. During search, earlier assignments and propagation can shrink those domains. MRV uses the remaining possibilities at the current point in the search, not merely the domains listed when the problem was first created.
The heuristic answers which variable to assign next. It does not answer which value to try for that variable. A separate value-ordering rule, such as least-constraining-value, can be used afterward. Keeping those two decisions distinct makes a solver's behavior much easier to explain.

How it works

Inspect the unassigned variables and count their currently legal values. Choose one with the smallest count, breaking ties according to an explicit rule. After trying a value and propagating consequences, recompute the relevant counts for the next choice.
A variable with no legal value indicates failure of the current branch rather than a normal choice to assign. A variable with one legal value is forced under the current information. MRV is often described as a fail-first strategy: it seeks a constrained part of the problem where an inconsistency is likely to become visible quickly, although that is a heuristic rationale rather than a universal performance guarantee.

Three practical examples

A timetable solver can choose the session with the fewest remaining feasible time slots.
A configuration solver can assign a component whose compatible options have already been reduced by previous selections.
A puzzle solver can fill a cell with very few legal symbols before a cell whose domain is still large.

Think of it this way

Think of arranging appointments by first dealing with the person who has only one available time, rather than someone available all week. The analogy is limited because a formal solver must account for interactions among choices and may backtrack; the person with the fewest options is not necessarily the most valuable or highest-priority person.

Worked example

Consider an invented constraint problem with three unassigned variables. A has domain {1, 2, 3, 4}, B has {2, 3}, and C has {3}. Require A, B, and C to take pairwise different values. The domain sizes are 4, 2, and 1.
MRV chooses C first because its domain is smallest. Assign C = 3. Propagating the pairwise-difference constraints removes 3 from A and B. Their remaining domains become A = {1, 2, 4} and B = {2}.
MRV now chooses B, which has one remaining value, rather than A, which has three. Assign B = 2 and propagate again. A becomes {1, 4}. Either A = 1 or A = 4 completes a valid assignment, so the original problem has two solutions under these domains and constraints.
MRV itself does not decide between 1 and 4. That requires a value-ordering policy or an application preference. If the goal is simply to find any solution, either is acceptable. If the goal is to enumerate all solutions, both branches must be considered by the complete search procedure.
Now imagine an additional branch assumption had already removed 3 from C. C's domain would be empty. The solver should report that branch inconsistent and backtrack, not ignore C because it has nothing convenient to assign.
The trace also explains why counts must be updated. B started with two choices but had only one after C was assigned. A fixed ranking based only on the initial domain sizes would miss changes in more complicated problems.

Illustrative case study

In a fictional room-booking project, Birch Schedule labels sessions with the shortest durations as most constrained. A review finds that a long session has only one feasible room-time combination, while several short sessions have many.
The team separates duration-based priorities from MRV and calculates remaining legal combinations after each assignment. It compares solver effort on representative cases before adopting the change. This invented case illustrates the heuristic's meaning; it does not claim a guaranteed reduction in runtime or better business priorities.

Common misconceptions and mistakes

MRV does not mean choose the smallest numeric value. It chooses the variable with the smallest number of options. It also differs from least-constraining-value, which orders values after a variable has been chosen.
Small initial domains are not always the smallest remaining domains. Also, counting stored domain values is only meaningful if those values reflect the intended legality checks or propagation state. MRV does not by itself prove a solution exists, eliminate the need for backtracking, or optimize a cost objective. It changes search order while the underlying constraint model defines what is allowed.

Business use

For a business constraint model, MRV can help direct search toward scarce flexibility. Define variables and domains so that remaining choices correspond to real alternatives. For example, a room-time pair may need to be treated as one option when room and time constraints interact.
Record how ties are resolved and how propagation maintains domains. Compare the cost of updating counts with the search effort saved, especially when evaluating legal values is expensive. Explain the resulting order as a solver strategy rather than a judgment about task importance. If some choices carry business priorities, represent those priorities explicitly in the problem or objective.

Check your understanding

After assigning C = 3 in the example, why does MRV choose B next?

Answer: Propagation leaves B with only {2}, while A still has {1, 2, 4}. MRV compares these updated counts, so B is the most constrained remaining variable.

Related terms

Learn next

Modify the example so that C has {2, 3} instead of {3}. Identify the MRV tie and choose a documented tie rule. Then trace how different first assignments change the remaining domains, keeping variable selection separate from value selection at every step.

Sources

University of California, Berkeley, original CS188 textbook, variable and value ordering: https://inst.eecs.berkeley.edu/~cs188/textbook/csp/ordering.html

Previous: Minimum norm estimation Next: Minimum slack