Backtracking is a search algorithm for finding all (or some) solutions to some computational problems, notably constant satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution. The algorithm traverses the search tree recursively, from the root down, in depth-first order. At each node the algorithm checks whether the node can be completed to a valid solution. If it cannot, the whole subtree rooted at the node is skipped (pruned). Otherwise, the algorithm checks whether the node is a valid solution, and if so reports it to the user; and recursively enumerates all sub-trees of the node.
An example: Order in which the nodes are expanded