# N Queens Problem (Backtracking)

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-

```while there are untried configurations
{
generate the next configuration
if queens don't attack in this configuration then
{
print this configuration;
}
}
```

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

```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;
}
```

To print all possible placements using backtracking:

```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);
}
}
}
```

You may use these HTML tags and attributes: `<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> `