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

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy This Password *

* Type Or Paste Password Here *

41,055 Spam Comments Blocked so far by Spam Free Wordpress

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>