Explore choices and undo when they lead to dead ends.
Backtracking builds candidates incrementally and abandons a branch as soon as it cannot lead to a solution (pruning). Used in N-queens, Sudoku, permutations, constraint satisfaction. Worst case is exponential; good heuristics and pruning make it practical.
A Sudoku solver tries a digit, recurses and undoes on contradiction.
Backtracking searches a space of choices and abandons paths that cannot lead to a solution, which solves puzzles and constraint problems.
Explore choices and undo when they lead to dead ends.
Backtracking searches a space of choices and abandons paths that cannot lead to a solution, which solves puzzles and constraint problems.
Stopping the search early when a partial choice cannot lead to a valid answer, which avoids exploring huge parts of the tree.
Backtracking uses constraints to cut down the search, while brute force checks every complete candidate without that pruning.
Typical applications include solving a sudoku puzzle by trying digits and undoing mistakes, generating all valid schedules for a set of staff and shifts and finding all ways to place eight queens on a chessboard without attack.
Study "Divide and conquer" first (topic 31 of 104 in Software & Computing). It covers the groundwork this topic builds on.
Decision tree search. Constraint propagation. Branch and bound.
A Sudoku solver tries a digit, recurses and undoes on contradiction.
The next topic is "NP-completeness", which builds directly on this one.
It is classed as Beginner in Software & Computing (topic 32 of 104). It is an entry-level topic. It relies only on basic school mathematics and the ideas introduced earlier in this discipline.
Want to practise? Open the interactive course for quick checks, quizzes, simulations and progress tracking.