Using Backtracking algorithm implement N-queen problem.

Name of the experiment:  Using Backtracking algorithm implement N-queen problem.

Algorithm:

1       Algorithm NQueens(k,n)

2       {

3                 for i:= 1 to  n do

4                 {

5                           if place(k, i) then

6                          {

7                                    x[k]:= i;

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

9                                    else NQueens( k+1,  n);

10                        }

11               }

12     }

Algorithm:

1       Algorithm Place(k,i)

2       {

3                 for j:=1  to k-1  do

4                          if ((x[j]= i)

5                                    or (Abs(x[j]-i)= Abs(j-k)))

6                                    then return false;

7                 return true;

8       }

Source Code:

#include<stdio.h>

#include<math.h>

int board[20],count;

int main()

{

 int n,i,j;

 void queen(int row,int n);

 printf(" - N Queens Problem Using Backtracking -");

 printf("\n\nEnter number of Queens:");

 scanf("%d",&n);

 queen(1,n);

 return 0;

}

void print(int n)

{

int i,j;

printf("\n\nSolution %d:\n\n",++count);

for(i=1;i<=n;++i)

printf("\t%d",i);

for(i=1;i<=n;++i)

{

printf("\n\n%d",i);

for(j=1;j<=n;++j)

{

if(board[i]==j)

printf("\tQ");

else

printf("\t-");

}

}

}

int place(int row,int column)

{

int i;

for(i=1;i<=row-1;++i)

{

if(board[i]==column)

return 0;

else

if(abs(board[i]-column)==abs(i-row))

return 0;

}

 return 1;

}

void queen(int row,int n)

{

int column;

for(column=1;column<=n;++column)

{

if(place(row,column))

{

board[row]=column; //no conflicts so place queen

if(row==n) //dead end

print(n); //printing the board configuration

else //try queen with next position

queen(row+1,n);

}

}

}

Sample Input and Output:

Enter number of Queen: 4

Solution 1:

            1          2          3          4

1          -           Q         -           -

2          -           -           -           Q

3          Q         -           -           -

4          -           -           Q         -

Solution 2:

            1          2          3          4

1          -           -           Q         -

2          Q         -           -           -

3          -           -           -           Q

4          -           Q         -           -