Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time (by time, here, is referred to the time elapsed till reaching any level of the search tree).

For example, consider the SudoKo solving Problem, we try filling digits one by one. Whenever we find that current digit cannot lead to a solution, we remove it (backtrack) and try next digit. This is better than naive approach (generating all possible combinations of digits and then trying every combination one by one) as it drops a set of permutations whenever it backtracks.

We will look at four different problems that can be solved using backtracking:



In each case, backtracking leads to an optimal solution, although if it cannot be quickly determined that a partial solution does no lead to a feasible solution, there may be significant depth to the tree and therefore a long run time. We will look at one solution to this issue in the solution to peg solitaire.