Recusion

Backtracing

The Eight Queens Problems

psudocode

placeQueens (in queenPtr:Queen *)
// Places queens in eight columns

    if (queen's column is greater than the last column)
        The problem is solved
        
    else
    {
        while (unconsidered squares exist in queen's column
                and the problem is unsolved)
        {
            Determine the next square in queen's column that 
                is not under atack by a queen in an earlier 
                column
            if (such a square exits)
            {
                Place a queen in the square
                // try next column
                placeQueens (create queen (firstRow, queen's 
                            column+1))
                if (no queen is possible in the next column)
                {
                    Delete the new queen
                    Remove the last queen placed on the board 
                        and cosider the next square in that 
                        column
                }   // end if
            }   // end if
        }   // end while
    }   // end if