Step by Step
V
Variables — the things needing an assigned value
The individual elements that need values assigned to them, such as cells in a Sudoku puzzle or regions on a map.
Example: each empty cell in a Sudoku grid is a variable needing a value assigned to it.
D
Domains — the possible values each variable can take
The set of legal candidate values available for each variable, such as the digits 1-9 in Sudoku or the set of available colors in a map-coloring problem.
Example: each Sudoku cell's domain is the digits 1 through 9, before any constraints narrow it down further.
C
Constraints — the rules that must all be satisfied simultaneously
The rules restricting which combinations of variable assignments are valid, such as "no repeated digit in a row/column/box" in Sudoku, or "adjacent regions must have different colors" in map coloring.
Example: the Sudoku constraint that no digit can repeat within the same row, column, or 3x3 box.
⚡
MRV heuristic — assign the most constrained variable first
The Minimum Remaining Values heuristic chooses to assign the variable with the fewest remaining legal options first, since these variables are most likely to fail quickly if a bad assignment was made earlier — failing fast saves significant backtracking time.
Example: if one Sudoku cell only has 1 remaining legal digit while others have 5+, assigning that most-constrained cell first quickly reveals whether the current partial solution is even viable.
Applied Walkthrough
1
A Sudoku-solving algorithm using plain backtracking assigns variables in a fixed, arbitrary order, regardless of how constrained each one currently is.
2
This means the algorithm might spend significant time filling in easy, loosely-constrained cells before discovering deep into the puzzle that an earlier assignment was actually invalid.
3
Switching to the MRV heuristic instead means always assigning the most constrained (fewest remaining legal values) variable next.
4
This surfaces failures much earlier in the search process, since the most constrained variables are the most likely to reveal a contradiction quickly, saving substantial backtracking time overall.
Exam Application
Exams test whether you can correctly identify the Variables/Domains/Constraints in a described CSP scenario (Sudoku, map coloring, scheduling) and whether you understand WHY the MRV heuristic improves efficiency — by failing fast on the most constrained variables rather than wasting time on easy ones first.
⚠ Common Trap
The most common trap is assuming any variable ordering works equally well in backtracking search. The MRV heuristic specifically improves efficiency precisely because assigning highly constrained variables first surfaces failures earlier, avoiding wasted effort on assignments that will later turn out to be part of an invalid solution.
✓ Quick Self-Check
1. What are the three core components of a Constraint Satisfaction Problem?
Variables, Domains, and Constraints.
Tap to reveal / hide
2. What does the MRV heuristic prioritize?
Assigning the variable with the fewest remaining legal values (most constrained) first.
Tap to reveal / hide
3. Why does the MRV heuristic save time compared to arbitrary variable ordering?
Because highly constrained variables are more likely to fail quickly if a contradiction exists, surfacing problems earlier and reducing wasted backtracking.
Tap to reveal / hide
4. What is AC-3 Arc Consistency used for?
Preprocessing that removes domain values with no compatible assignment, narrowing the search space before backtracking begins.
Tap to reveal / hide
5. Name two real-world problems commonly modeled as CSPs.
Sudoku and map coloring (or scheduling problems).
Tap to reveal / hide