Given a chess board of size **n*n**,the task is to find all the ways to place **n** queens so that they don’t attack each other.

In chess, a queen can move as far as she pleases, horizontally, vertically, or diagonally.

**Naive Algorithm-**

[cpp]

while there are untried configurations

{

generate the next configuration

if queens don’t attack in this configuration then

{

print this configuration;

}

}

[/cpp]

**Backtracking Algorithm-**

If queens are at (i,j) and (k,l) coordinates,then they can attack each other if:

1. i=k (same row)

2. j=l (same column)

3. |i-k|=|j-l| (diagonally),| | denotes the absolute value

[cpp]

bool place(k,i)

{

//returns true if the queen can be placed at k-th row and i-th column

//x[] is a global array with first (k-1) values set already.

//x[p]=q means a queen is at location (p,q)

for(j=1 to k-1)

{

if(x[j]==i)||(ABS(x[j]-i)==ABS(j-k)) //checking if another queen in same column or diagonally

return false;

}

return true;

}

[/cpp]

To print all possible placements using backtracking:

[cpp]

void NQueens(k,n)

{

for(i=1 to n)

{

if(place(k,i)) //checking if queen can be placed at (k,i)

{

x[k]=i;

if(k==n) then write (x[1:n]);

else Nqueens(k+1,n);

}

}

}

[/cpp]