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.
In more detail
It explores a decision tree depth-first: choose, recurse, then undo and try the next option. Pruning cuts off hopeless branches early, which is where all its speed comes from. It is the right tool when you need every valid solution, as in N-queens, sudoku or generating permutations.
Related terms
- pruning — Abandoning a branch of a search as soon as a check shows it cannot lead to a valid or better solution.
- decision tree — A tree in which each internal node is a question or choice and each path from the root to a leaf is one complete outcome.
- depth-first search — A graph search that follows one path as deep as it can go, then backs up to the last choice point and tries the next branch.
- 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.
- exhaustive search — Trying every possible candidate solution and checking each one.
Taught in
- Stacks And Queues: Last In Or First In — Algorithms & Data Structures for Working Engineers
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers
- Breadth-First Search And Shortest Paths By Hops — Algorithms & Data Structures for Working Engineers
- Depth-First Search, Cycles And Topological Order — 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