backtracking

Backtracking is an algorithmic technique. It us used to find solutions by trying one of several choices. If the choice proves incorrect, computation backtracks or restarts at the point of choice and tries another choice. It is often convenient to maintain choice points and alternate choices using recursion. Backtracking is often done AI algorithms. It can greatly increase the speed of a search by avoided costly unproductive sub searches.

In solving some problems, situations can arise where many choices must be made without any knowledge of which choice will lead towards a solution. To solve such problems requires a certain degree of trial and error. Thus, after finding one choice unsucessful, we can return to the point where that decision was made, and test an alternative choice. However, for this to work, we must ensure that such a return is possible and that all paths can be tried. This technique is known as backtracking, and has a multitude of applications in artificial intelligence. Additionally, backtracking can be quite useful in finding a solution to the eight queens puzzle.

A Backtracking Algorithm

This is a simple recursive algorithm that uses backtracking to solve the eight queens puzzle:

putQueen(row)
   for every position col on the same row
      if position col is available
         place the next queen in position col;
         if (row < 8)
            putQueen(row + 1);
         else sucess;
         remove the queen from position col;

The algorithm works by testing every possible solution. Eight queens must be placed on the chess board without being able to attack one another, thus, the algorithm places the first queen on the board, and then proceeds to test every position that the second queen can be placed in, while testing which spots the third queen can be placed in relation to the second and the first... etc... it's quite recursive.