Backtracking

If a feasible solution to a problem can be built up from partial solutions, backtracking is an algorithm design technique that allows one to systematically search through partial solutions to determine if one branch leads to a feasiable solution.

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

• the eight queen's problem,
• the knight's tour,
• sudoku,
• peg soliaire, and
• the knapsack problem.

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.