Sudoku (MRV + LCV)

This visualization shows an advanced Sudoku solver that uses two powerful heuristics from constraint satisfaction theory: Minimum Remaining Values (MRV) for choosing which cell to fill next, and Least Constraining Value (LCV) for choosing which number to try first. While naive backtracking processes cells in a fixed order and tries values sequentially, MRV + LCV makes intelligent decisions at every step, often reducing the search space by orders of magnitude. These heuristics represent core ideas from artificial intelligence research that transform brute-force search into practical problem solving.

The Intelligence Behind the Heuristics

MRV (Minimum Remaining Values), also known as the "fail-first" heuristic, is rooted in a counterintuitive insight: you should tackle the hardest decisions first. By choosing the cell with the fewest remaining legal values, the algorithm reaches contradictions sooner. A cell with only one legal value is a forced move that requires no branching at all. A cell with two legal values creates at most two branches, while a cell with eight legal values could create eight. MRV ensures the search tree stays narrow at its top levels, where branching has the greatest impact on total work.

LCV (Least Constraining Value) applies the opposite philosophy when choosing a value: prefer the value that rules out the fewest options for neighboring cells. While MRV constrains the problem aggressively, LCV keeps the remaining problem as flexible as possible, maximizing the chance of finding a solution without needing to backtrack.

How It Works

1. MRV (variable ordering): Instead of filling cells left to right, choose the empty cell with the fewest legal values remaining. This cell is most constrained and most likely to fail, so trying it first prunes the search tree early. If any cell has zero legal values, the algorithm backtracks immediately without further exploration.
2. LCV (value ordering): For the chosen cell, calculate how many legal values each candidate would eliminate from neighboring cells (peers in the same row, column, and box). Try values in ascending order of their constraining impact, starting with the value that leaves the most flexibility for neighbors.
3. Place and recurse: Place the chosen value, update the constraint records for all affected peers, and recursively solve the remaining puzzle.
4. Backtrack: If no value works for the selected cell, undo the placement, restore the constraint records, and return to the previous decision point.

Complexity

MRV + LCV dramatically reduces the number of nodes explored compared to naive backtracking. On hard Sudoku puzzles, naive backtracking might explore hundreds of thousands of states, while MRV + LCV often solves the same puzzle exploring only a few hundred. The combination is particularly effective because MRV tightens the search structure while LCV reduces the likelihood of wrong turns at each node.

Connection to AI and CSP Theory

These heuristics were formalized in the context of general-purpose CSP solvers during the 1970s and 1980s. MRV was described by Robert Haralick and Gordon Elliott in their 1980 paper on constraint satisfaction. LCV was developed as part of research into value ordering strategies. Together with techniques like forward checking and arc consistency (AC-3), they form the foundation of modern CSP solving frameworks such as Google OR-Tools and Choco Solver. The Sudoku puzzle serves as an ideal teaching example because it is simple enough to understand yet complex enough to demonstrate the dramatic performance differences between uninformed and informed search strategies.

When to Use

These heuristics are standard tools in constraint satisfaction problem (CSP) solvers. MRV (also called "fail-first") and LCV are taught in AI courses as examples of how intelligent search ordering transforms intractable problems into practical ones. The same principles apply to scheduling, map coloring, timetable generation, resource allocation, and any problem modeled as a CSP. Watching this visualization side by side with the naive Sudoku solver reveals the power of heuristic guidance.