CSP Sudoku Solver

The problem

Brute-forcing a hard Sudoku is slow. With the right constraint propagation, most puzzles collapse to a solution with little or no backtracking.

Approach

Constraint satisfaction with backtracking, AC-3 arc consistency preprocessing, and MRV heuristic for intelligent variable ordering.

Decisions

1. 01

   AC-3 arc consistency before any search

   Propagating constraints first strips impossible values from every cell up front. Many puzzles fall out from propagation alone, and the rest start from a much smaller search space.

2. 02

   MRV heuristic for variable ordering

   When search is still needed, filling the cell with the fewest remaining candidates first fails fast on dead ends and keeps the branching factor low, instead of marching through the grid in row order.

Results

Solve any grid in the browser. The Solve button runs the CSP solver and fills a valid solution in well under a second.

Try it