constraint propagation
Using one decision to rule out other options immediately, so a single choice narrows the rest of the search.
In more detail
Placing a queen rules out its column and both diagonals for every later row; the course tracks these in three sets so each check is O(1). Sudoku solvers rely on propagation to fill in forced cells. The more each choice constrains the others, the shallower the effective search tree.
Related terms
- pruning — Abandoning a branch of a search as soon as a check shows it cannot lead to a valid or better solution.
- 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.
- 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.
- 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.
Taught in
- Space, In-Place Work And The Call Stack — Algorithms & Data Structures for Working Engineers
- Stacks And Queues: Last In Or First In — Algorithms & Data Structures for Working Engineers
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers
- Backtracking: Search With Pruning — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers