sudoku
A number puzzle on a 9-by-9 grid where each row, column and 3-by-3 box must contain the digits 1 to 9 exactly once.
In more detail
It is a textbook constraint problem for backtracking: fill a cell, check the constraints, and undo on a conflict. Constraint propagation solves many cells without any guessing.
Related terms
- backtracking — A search technique that builds a solution one choice at a time and undoes the latest choice as soon as it cannot lead to a valid solution.
- constraint propagation — Using one decision to rule out other options immediately, so a single choice narrows the rest of the search.
Taught in
- Backtracking: Search With Pruning — Algorithms & Data Structures for Working Engineers