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]
