Many puzzles, such as Sudoku and N-Queens, are constraint satisfaction problems. Plain backtracking can solve them, but adding inference turns an impractical search into a quick one.
The ingredients
A constraint satisfaction problem has variables, a domain of allowed values for each variable, and constraints that restrict which combinations are allowed. A solution assigns a value to every variable without breaking any constraint.
Backtracking alone
Backtracking assigns variables one at a time and retreats when a constraint fails. It works, but it can waste enormous effort exploring branches that were doomed several steps earlier.
Smarter ordering
- Minimum remaining values: choose the variable with the fewest legal values left. It is the most likely to fail, so fail early.
- Least constraining value: try the value that removes the fewest options from neighboring variables.
Inference removes doomed branches early
After each assignment, forward checking removes inconsistent values from neighbors' domains. Arc consistency (AC-3) goes further: for every pair of connected variables, it deletes any value that has no compatible partner value in the other variable. If a domain becomes empty, the search backtracks immediately.
The trade-off
Inference costs time at each step, but it usually pays back by shrinking the search dramatically. On many Sudoku puzzles, repeated propagation alone fills in most cells before any guessing is needed.
Continue with the book
Explore the full treatment, worked examples, and exercises in The AI Algorithms Compendium.
Adapted from The AI Algorithms Compendium, published by Choral Software. Article text and original examples © 2026 Choral Software. All rights reserved.