Backtracking

Backtracking is a search method that builds candidate solutions incrementally and abandons a partial candidate as soon as it cannot lead to a complete solution.

Depth-first search: A graph-search strategy that explores one branch as far as possible before returning to alternatives. Backtracking commonly uses this traversal pattern to explore one partial solution at a time.
N-queens problem: The problem of placing N queens on an N×N chessboard so that no two attack each other. A placement-by-placement search can reject a row as soon as a queen conflicts with an earlier one.
Dynamic programming: An algorithmic approach that solves overlapping subproblems once and reuses their results. Unlike ordinary backtracking, it stores solved subproblems to avoid repeating equivalent work.
Constraint satisfaction problem: A problem defined by variables, possible values for each variable, and constraints on their combinations. Many backtracking tasks are constraint satisfaction problems solved by assigning variables incrementally.
Search tree: A tree whose nodes represent states explored by a search procedure and whose edges represent choices. Each branch represents a sequence of choices that backtracking may extend or abandon.
Sudoku: A number-placement puzzle whose rows, columns, and boxes must each contain every digit once. Solvers can test candidate digits and retreat when later placements violate the puzzle's constraints.
Greedy algorithm: An algorithm that repeatedly makes a locally preferred choice without reconsidering earlier choices. Greedy methods commit to choices, while backtracking can retract them after discovering a dead end.
Partial assignment: An assignment that gives values to only some variables in a problem. It is the intermediate state that backtracking extends, tests, and sometimes discards.
Constraint propagation: The reduction of possible variable values by repeatedly applying constraints among variables. Propagation can expose an impossible partial assignment before deeper choices are explored.
Knight's tour: A sequence of knight moves that visits every square of a chessboard exactly once. A move sequence can be extended until it becomes impossible, then shortened to try another route.

Linked from 16 pages