Wednesday 21 November 2012

NQueen problem in C

Today I am going to post the NQueen problem in C with Backtracking.
What is the problem : According to this problem, we will have to place N queens in a n*n chessboard in such a way that the quuens are non-attacking. Non-attacking means there should be no queens in the same row,column or diagonal.
How to solve the problem : Here we will use the method of backtracking. In order to solve this problem, we first place the first queen, then the second and so on. But if we fail to place a queen, then we go back to the last successful position and try a different path. Now here is the details of the method : If a queen is already placed at location (i,j) and we want to place another queen at location (k,l), then we have to check whether we can place it in that location in the following way :
1  : check j!=l (not in same column)
2  ; ((i-j)!=(k-l)) (not in same right diagonal)
3 : ((i+j)!=(k+l)) (not in same left diagonal)
The second and third condition can be combined in a single condition which is : (abs(j-l)!=abs(k-i))
--------------------------------------------------------------------------------------------------------------------------
C CODE
--------------------------------------------------------------------------------------------------------------------------
#include<stdio.h>
#include<math.h>

int x[50],soln=0;

int place(int k,int i){
//place kth queen at ith location
   int j;
   for(j=1;j<k;j++) 
//checking with previously placed queens
     if((x[j]==i) || (abs(x[j]-i)==abs(j-k)))
      return 0;
   return 1; 
//if successfully placed at ith location
}

void nqueens(int k,int n){
  int i;
  for(i=1;i<=n;i++)
    if(place(k,i)==1){ 
//if not successful then backtrack
     x[k]=i; 
//if successful then save column number
     if(k==n) 
//if all queens olaced then show solution
       display(n);
     else
       nqueens(k+1,n);
//place all other queens
    }
}

void display(int n){
   int i,j;
   soln++;
   printf("\nSOLUTION #%d\n",soln);
   for(i=1;i<=n;i++){
     for(j=1;j<=n;j++)
       if(x[i]==j)
          printf("Q\t");
       else
          printf("*\t");
     printf("\n\n");
   }
}

int main(){
   int n;
   printf("Enter no. of queens : ");
   scanf("%d",&n);
   nqueens(1,n);
   printf("TOTAL SOLN. : %d",soln);

   return 0;
}
Note : This code has been written and compiled with GCC compiler under Linux environment Ubuntu 12.04 LTS Precise Pangolin.
-------------------------------------------------------------------------------------------------------------------------
OUTPUT
------------------------------------------------------------------------------------------------------------------------- 
Enter no.of queens : 4

SOLUTION #1
*       Q       *       *

*       *       *       Q

Q       *       *       *

*       *       Q       *


SOLUTION #2
*       *       Q       *

Q       *       *       *

*       *       *       Q

*       Q       *       *
TOTAL SOLN. : 2
-------------------------------------------------------------------------------------------------------------------------
DOWNLOAD LINKS
-------------------------------------------------------------------------------------------------------------------------

2 comments:

  1. Very useful information..

    ReplyDelete
  2. display function should be placed before nqueens function,
    but quiet good code. thanks for helping

    ReplyDelete