Today I am going to post the NQueen problem in C with Backtracking.

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

--------------------------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------------------------------

__: 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.__**What is 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 :__**How to solve the problem**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

#include<math.h>

int x[50],soln=0;

int place(int k,int i){

**//checking with previously placed queens**

int j;

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

int j;

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

**//if successfully placed at ith location**

if((x[j]==i) || (abs(x[j]-i)==abs(j-k)))

return 0;

return 1;

if((x[j]==i) || (abs(x[j]-i)==abs(j-k)))

return 0;

return 1;

**//if not successful then backtrack**

}

void nqueens(int k,int n){

int i;

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

if(place(k,i)==1){

}

void nqueens(int k,int n){

int i;

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

if(place(k,i)==1){

**//if successful then save column number**

x[k]=i;

x[k]=i;

**//if all queens olaced then show solution**

if(k==n)

if(k==n)

**//place all other queens**

display(n);

else

nqueens(k+1,n);

display(n);

else

nqueens(k+1,n);

}

}

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

}

}

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.

return 0;

}

-------------------------------------------------------------------------------------------------------------------------

**OUTPUT**

**-------------------------------------------------------------------------------------------------------------------------**
Enter no.of queens : 4

SOLUTION #1

* Q * *

* * * Q

Q * * *

* * Q *

SOLUTION #2

* * Q *

Q * * *

* * * Q

* Q * *

SOLUTION #1

* Q * *

* * * Q

Q * * *

* * Q *

SOLUTION #2

* * Q *

Q * * *

* * * Q

* Q * *

TOTAL SOLN. : 2

**DOWNLOAD LINKS****-------------------------------------------------------------------------------------------------------------------------**

Very useful information..

ReplyDelete