backtracking (thing)

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.