N Queen Problem - Back Tracking

Problem :-

• The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For example, following is a solution for 4 Queen problem.

Idea:- 

1. Place the queens column wise, start from the left most column
2. If all queens are placed.
   1. return true and print the solution matrix.
3. Else
   1. Try all the rows in the current column.
   2. Check if queen can be placed here safely if yes mark the current cell in solution matrix as 1 and try to solve the rest of the problem recursively.
   3. If placing the queen in above step leads to the solution return true.
   4. If placing the queen in above step does not lead to the solution , BACKTRACK, mark the current cell in solution matrix as 0 and return false.
4. If all the rows are tried and nothing worked, return false and print NO SOLUTION.

Algo :- 

NQueen(k,n)
{
    for(i=1 to n) do
    {
       if(place(k,i)) then
       {
           x[k]=i;
           if(k==n) then write (x[1:n])
           else NQueen(k+1,n);
       }
    }
}
place(k,i)
{
   for(j=1 to k-1) do
   {
       if(x[i]==i) or (Abs(x[j]-i)==Abs(j-k)) then
            return true;
   }
   return false;
}

Programme:-
Download programme

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
int n;
int solNo=0;
void print(int x[])
{
 int i;
 printf("SOLUTION %d : ",++solNo);
 for(i=0;i<n;i++)
 {
  printf("%d ",(x[i]+1));

 }
 printf("\n");
}
place(int k,int i,int x[])
{
 int j;
 for(j=0;j<=k-1;j++)
 {
  if( (x[j]==i) || ( abs(x[j]-i)==abs(j-k)) )
  {
   return false;
  }
 }
 return true;
}
Nqueen(int k,int x[])
{
 int i;
 for(i=0;i<n;i++)
 {
  if(place(k,i,x))
  {
   x[k]=i;
   if(k==n-1)
   {
    print(x);
   }
   else
   {
    Nqueen(k+1,x);
   }
  }
 }
}
main()
{
 int i;
 printf("ENTER THE PROBLEM SIZE (No Of Queen): ");
 scanf("%d",&n);
 int x[n];
 for(i=0;i<n;i++)
 {
  x[i]=0;
 }
 Nqueen(0,x);
}