Goal:

Implement the algorithm PlaceQueens in the picture

Language to be used:

C++

PLACEQUEENSQ[1..n],r): if r = n+1 print Q[1..n] else for j - 1 ton legal TRUE for i1 tor-1 if (Q[i]= j) or (Q[i]=j+r-i) or (Q[i]=j-r+i) legal FALSE if legal Q[r]] PLACEQUEENS(Q[1..n],r+1) ((Recursion!) Figure 2.2. Gauss and Laquire's backtracking algorithm for the n queens problem. (with r =0). Edges in the recursion tree correspond to recursive calls. Leaves correspond to partial solutions that cannot be further extended, either because there is already a queen on every row, or because every position in the next empty row is attacked by an existing queen. The backtracking search for complete solutions is equivalent to a depth-first search of this tree. H