N-queens
The puzzle of placing N chess queens on an N-by-N board so that no two share a row, column or diagonal.
In more detail
Backtracking places one queen per row and prunes any column or diagonal already attacked. The standard 8-by-8 board has 92 solutions, and the count grows quickly with N. It is the classic demonstration of how much pruning saves over exhaustive search.
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.
- pruning — Abandoning a branch of a search as soon as a check shows it cannot lead to a valid or better 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