/* N-QUEEN PROBLEM */
#include<stdio.h>
#include<conio.h>
static int count=0;
int x[100];
int mat[100][100]={0};
void nqueen(int k, int n);
int place(int k, int i);
void init(int n);
void show(int n);
int main()
{
int n;
clrscr();
printf("Enter the value of n: ");
scanf("%d",&n);
printf("\nThe solutions are: \n");
nqueen(1,n);
printf("\nThe total number of solutions is %d",count);
getch();
return 0;
}
void nqueen(int k,int n)
{
int i,j;
for(i=1;i<=n;i++)
{
if(place(k,i))
{
x[k]=i;
if(k==n)
{
for(j=1;j<=n;j++)
{
printf("%d ",x[j]);
}
count++;
printf("\n\nIn Matrix Form:\n");
show(n);
printf("\n");
init(n);
}
else
nqueen(k+1,n);
}
}
}
//Returns 1 if a queen can be placed in kth row and ith column
//Else returns 0
int place(int k,int i)
{
int j;
for(j=1;j<k;j++)
if((x[j]==i) || (abs(x[j]-i)==abs(j-k)))
return 0;
return 1;
}
void show(int n)
{
int i, j;
for(i=1;i<=n;i++)
{
mat[i][x[i]]=1;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d ", mat[i][j]);
}
printf("\n");
}
}
void init(int n)
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
mat[i][j]=0;
}
/* OUTPUT
Enter the value of n: 4
The solutions are:
2 4 1 3
In Matrix Form:
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
3 1 4 2
In Matrix Form:
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
The total number of solutions is 2
*/
Comments
Post a Comment