**The Basic Idea**
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.

Source: Computer Science 2050