queen.c

C PROGRAM FOR 8 QUEENS PROBLEM USING BACKTRACKING

//8 QUEEN PROBLEM ALGORITHM BY PRIANCEU PANDEY
#include <stdio.h>
#include <conio.h>
#define BOOL int;
#define TRUE 1;
#define FALSE 0;
int check(void);
int  queen(int i);
int a[8][8];
main()
{
int i,j,k;
clrscr();
for(i=0;i<8;i++)
	{
		for(j=0;j<8;j++)
		a[i][j]=0;
	}
queen(0);


for(i=0;i<8;i++)
	{
		for(j=0;j<8;j++)
		{
		printf("%d",a[i][j]);
		}
		printf("\n");
	}
getche();
return 0;
}

int check(void)
{
int i,j,k;
for(i=0;i<8;i++)
{
	for(j=0;j<8;j++)
	{
	if(a[i][j]==1)
	{
		for(k=0;k<8;k++)
		{
		if((k!=i)&&(a[k][j]==1))
		return 0;
		}
		for(k=0;k<8;k++)
		{
		if((k!=j)&&(a[i][k]==1))
		return 0;
		}
		for(k=1;((i+k)<8)&&((j+k)<8);k++)
		{
		if(a[i+k][j+k]==1)
		return 0;
		}
		for(k=1;((i-k)>=0)&&((j-k)>=0);k++)
		{
		if(a[i-k][j-k]==1)
		return 0;
		}
		for(k=1;((i-k)>=0)&&((j+k)<8);k++)
		{
		if(a[i-k][j+k]==1)
		return 0;
		}
		for(k=1;((i+k)<8)&&((j-k)>0);k++)
		{
		if(a[i+k][j-k]==1)
		return 0;
		}

	}
	}
}
return 1;
}

int queen(int i)
{
int j;
if(i>7)
	return 1;


for(j=0;j<=7;j++)
{
	int x=0,y=0;
	a[i][j]=1;
	x=check();
	if(x==0)
	{
	a[i][j]=0;
	continue;
	}
	else{
	y=queen(i+1);
	if (y==0)
	{
	a[i][j]=0;
	continue;
	}
	else if (y==1)
	break;
	}
}
if(j>=8)
	return 0;
else
	return 1;
}