partial solution
An incomplete solution built so far during a search, such as queens placed on the first few rows of the board.
In more detail
Pruning checks each partial solution against the constraints and abandons it the moment it breaks one, rather than waiting for a complete candidate. Backtracking extends a partial solution by one choice at a time and shrinks it again when it undoes a choice.
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.
Taught in
- Backtracking: Search With Pruning — Algorithms & Data Structures for Working Engineers