Tuesday, October 23, 2012

The N- Queens Problem in C


//FEEL FREE TO DROP ANY QUESTION IN THE COMMENTS
# include<stdio.h>
# include<conio.h>
# define C 8
int check(int k[][C], int m, int n);
void backtrack(int k[][C], int f2[], int m);
void increment(int k[][C], int m, int n);
void main()
{
int a[C][C] = {0},i, j = 0, c, fj[C] = {0}, z = 0, k, count = 0;
clrscr();
for(i = 0; i < C; i++)
{
reloop:
while(j < C)
{
c = check(a, i, j);
if(c == 0)
{
increment(a, i, j);
fj[i] = j;
z = 1;
break;
}
j++;
}
if(z != 1)
{
    backtrack(a, fj, i);
    j = fj[i - 1] + 1;
    i = i - 1;
    if(i < 0)
    {
goto end;
    }
    goto reloop;
}
j = 0;
z = 0;
if(i == (C-1))
{
for(k = 0; k < C; k++)
{
printf("(%d,%d);",k,fj[k]);
}
printf("\n");
getch();
count++;
backtrack(a, fj, i + 1);
j = fj[i] + 1;
    goto reloop;
}

}
end:
printf("%d",count);
getch();
}
int check(int k[][C], int m, int n)
{
int i, j, sum = 0;
for(i = 0; i < C; i++)
{
sum = sum + k[i][n] + k[m][i];
}
if(m == n)
{
for(i = 0; i < C; i++)
{
sum = sum + k[i][i];
}
}
else if(m < n)
{
for(i = 0, j = n - m; j < C; j++, i++)
{
sum = sum + k[i][j];
}
}
else if(m > n)
{
for( i = m - n, j = 0; i < C; i++,j++)
{
sum = sum + k[i][j];
}
}
if((m + n) == C-1)
{
for(i = C - 1, j = 0; j < C; j++, i--)
{
sum = sum + k[i][j];
}
}
else if((m + n) < C - 1)
{
for(i = m + n, j = 0; j <= m + n;  i--, j++)
{
sum = sum + k[i][j];
}
}
else if((m + n) > C-1)
{
for(i = C - 1, j = m + n - C + 1; j < C; i--,j++)
{
sum = sum + k[i][j];
}
}
return sum;
}
void increment(int k[][C], int m, int n)
{
k[m][n] = 1;
}
void backtrack(int k[][C], int f2[], int m)
{
int i, j;
i = m - 1;
j = f2[m-1];
k[i][j] = 0;
}

No comments:

Post a Comment