2 docs tagged with "State Space Search"

Backtracking is an algorithmic paradigm used to solve problems in which the number of possible candidate solutions is very large, but many of those candidates can be discarded early because they violate some constraint. The central idea is simple: construct a solution step by step, and as soon as a partial solution cannot possibly lead to a valid complete solution, abandon it and return to the previous step.

When solving hard combinatorial problems, Backtracking provides an exact solution by executing a systematic Depth-First Search (DFS). However, it does so blindly, relying entirely on hitting an unfeasible boundary before turning around.