-
8 Queens
I did the following program. But it is giving 10356 solutions! I need the 92 distinct solutions for n = 8. Where wrong am I?
Code:
#include <stdio.h>
#include <stdlib.h>
int *x, count = 0;
/*Return true if a a queen can be placed in kth row
and ith column. Otherwise it returns false. x[] is a
global array whose first (k-1) values have been set.*/
int Place(int k, int i)
{
int j;
for(j = 0; j < k-1; j++)
if( (x[j] == i) || (abs (x[j] - i) == abs(j - k)) )
return 0;
return 1;
}
/*Using backtracking, this function prints all possible placements
of n queens on n x n chessboard so that they are non-attacking */
void NQueens(int k, int n)
{
int i,loop;
for(i = 0; i <= n; i++)
{
if( Place(k,i) )
{
x[k] = i;
if(k == n)
{
for(loop = 0; loop < n; loop++)
printf("%u ", x[loop] );
printf("\n");
count++;
return ;
}
else
NQueens(k+1,n);
}
}
}
int main()
{
int n;
printf("Enter the size of the chessboard : ");
scanf("%u",&n);
x = (int*)calloc(n,sizeof(int));
printf("\nThe solutions to the problem are :- \n\n");
NQueens(0,n-1);
printf("count : %d",count);
return 0;
}
-
Well what's the difference between a solution and a "distinct" solution.
At the moment, you simply count solutions.
What you would seem to need is some kind of "have I seen this solution before?" test.