*** ALL THESE PROGRAMS HAVE BEEN TRIED AND TESTED IN TURBO-CPP ***
------------------------------------------------------------------------------------ */
SOLUTION #1
# include <stdio.h>
# include <stdlib.h>
# include <time.h>
int N; //For N * N ChessBoard
int flag;
void printArray(int a[]); /* Just to Print the Final Solution */
void getPositions(int a[],int n1,int n2); /* The Recursive Function */
int main()
{int *a;
int ctr=0;
printf("\nTHE N QUEENS PROBLEM ");
printf("\nNumber Of Rows(N) For NxN Chessboard.");
scanf("%d",&N);
a=(int *)(malloc(sizeof(int)*N));
printf("\nAll possible Solutions .. \n");
printf("\nIn Each of the solutions the Coordinates of the N-Queens are given (Row,Col) .");
printf("\nNote that the Rows and Colums are numbered between 1 - N :\n");
for(ctr=0;ctr<N;ctr++)
getPositions(a,0,ctr);
getchar();
getchar();
}
void printArray(int a[])
{
int i,choice;
static int counter=0;
counter++;
printf("\nSOLUTION # %d :",counter);
for(i=0;i<N;i++)
printf("(%d,%d) ",i+1,a[i]+1);
if(counter%10==0) { printf("\nEnter 0 to exit , 1 to continue .");
scanf("%d",&choice);
if(choice==0) exit(0);
};
}
void getPositions(int a1[],int colno,int val)
{ int ctr1,ctr2;
a1[colno]=val;
if(colno==N-1)
{ printArray(a1) ; return;
};
for(ctr1=0;ctr1<N;)
{ /* This Loop Finds Suitable Column Numbers , in the NEXT ROW */
for(ctr2=0;ctr2<=colno;ctr2++)
if(a1[ctr2]==ctr1 || (colno+1-ctr2)*(colno+1-ctr2)==(ctr1-a1[ctr2])*(ctr1-a1[ctr2]))
goto miss1;
getPositions(a1,colno+1,ctr1);
miss1:
ctr1++;
}
}
/* END OF FIRST PROGRAM*/
--------------------------------------------------------------------------------------
2. PROGRAM FOR N QUEENS PROBLEM WITHOUT RECURSION (Using two stacks instead)
/*EightQueens Program using two Stacks , Stacks are implemented using arrays */
# include <stdio.h>
# include <stdlib.h>
# include <time.h>
typedef struct { int x,y;
} position ;
void SolveProblem(int n);
int N=0;
void main()
{printf("\nENTER THE SIZE OF CHESSBOARD ( N ) FOR NxN CHESSBOARD :");
scanf("%d",&N);
printf("\nIn Each of the solutions the Coordinates of the N-Queens are given (Row,Col) .");
printf("\nNote that the Rows and Colums are numbered between 1 - N :\n");
SolveProblem(N);
getchar();
}
void SolveProblem(int n)
{
int counter1,counter2=-1,counter3=-1;
static int counter=0,choice;
int d[100][3]={0};
int *stack2;
position Position1,Position2,Position3;
position *head1=(position *)malloc(n*n*sizeof(position));
stack2=(int *)malloc(n*sizeof(int));
for(counter1=n-1;counter1>=0;counter1--)
{ Position1.x=0;
Position1.y=counter1;
head1[++counter2]=Position1;
};
while(counter2>=0){ Position1=head1[counter2--];
while(counter3>=0 && Position1.x<=counter3){
Position2.x=counter3;
Position2.y=stack2[counter3--];
d[Position2.y][0]=0;
d[Position2.x+Position2.y][1]=0;
d[Position2.x-Position2.y+n][2]=0;};
stack2[++counter3]=Position1.y;
d[Position1.y][0]=1;
d[Position1.x+Position1.y][1]=1;
d[Position1.x-Position1.y+n][2]=1;
if(counter3==n-1)
{
counter++;
printf("\nSOLUTION # %d:",counter);
for(counter1=0;counter1<=counter3;counter1++)
printf("(%d,%d) " ,counter1+1, stack2[counter1]+1);
if(counter%10==0){printf("\nEnter 1 to Continue , 0 to end.");
scanf("%d",&choice);
if(choice==0)
exit(0);
};
Position2.x=counter3;
Position2.y=stack2[counter3--];
d[Position2.y][0]=0;
d[Position2.x+Position2.y][1]=0;
d[Position2.x-Position2.y+n][2]=0;}
else{for(counter1=n-1;counter1>=0;counter1--)
if(d[counter1][0]==0 && d[Position1.x+1+counter1][1]==0 && d[n+Position1.x+1-counter1][2]==0)
{Position3.x=Position1.x+1;
Position3.y=counter1;
head1[++counter2]=Position3;
};
}
}
}
3. PROGRAM WITH (At Least Some !) HEURISTICS
# include <stdio.h>
# include <stdlib.h>
# include <time.h>
# include <math.h>
int N; //For N * N ChessBoard
void printArray(int a[]);
void getPositions(int ,int);
void assignPriority();
void assignSecondOrderPriority();
void motionorder(const int);
int d[500][3]={0};
int *a1;
int ctr2;
int *a2;
long int **priority_array,**secondOrderPriority;long int **motionOrder;
int main()
{
int ctr=0,ctr1,n1;
printf("\nNumber Of Rows/Cols For NxN Chessboard.");
scanf("%d",&N);
a1=(int *)(malloc(sizeof(int)*N));
a2=(int *)(malloc(sizeof(int)*N));
priority_array=(long int **)malloc(N*sizeof(long int *));
for(ctr=0;ctr<N;ctr++) priority_array[ctr]=(long int *)malloc(N*sizeof(long int));
secondOrderPriority=(long int **)malloc(N*sizeof(long int *));
for(ctr=0;ctr<N;ctr++) secondOrderPriority[ctr]=(long int *)malloc(N*sizeof(long int));
motionOrder=(long int **)malloc(N*sizeof(long int *));
for(ctr=0;ctr<N;ctr++) motionOrder[ctr]=(long int *)malloc(N*sizeof(long int));
assignPriority();
printf("\nAll possible Solutions .. (Row,Col) \n");
assignSecondOrderPriority();
printf("\n N=%d ",n1==N);
motionorder(n1);
printf("\nIn Each of the solutions the Coordinates of the N-Queens are given (Row,Col) .");
printf("\nNote that the Rows and Colums are numbered between 1 - N :\n");
N=n1;
for(ctr=n1-1;ctr>=0;ctr--)
getPositions(0,motionOrder[0][ctr]);
getchar();
getchar();
return 0;
}
void printArray(int a[])
{
int i,choice;
static int counter=0;
printf("\nSOLN %d :",++counter);
for(i=0;i<N;i++)
printf("%d ",a[i]+1);
if(counter%10==0) {printf("\nEnter 0 to exit, 1 to continue.");
scanf("%d",&choice);
if(choice==0)
exit(0);
}
}
void getPositions(int colno,int val)
{ int ctr1;
if(colno==0)
for(ctr1=0;ctr1<N;ctr1++) a1[ctr1]=0;
a1[colno]=val;
d[N+val-colno][0]=1;
d[val][1]=1;
d[val+colno][2]=1;
if(colno==N-1)
{
printArray(a1);
d[N+val-colno][0]=0;
d[val][1]=0;
d[val+colno][2]=0;
}
else
for(ctr1=N-1;ctr1>=0;ctr1--)
{ctr2=(int)motionOrder[colno+1][ctr1];
if(d[ctr2][1]!=1)
if(d[ctr2+colno+1][2]!=1)
if(d[N+ctr2-colno-1][0]!=1)
if(ctr2>=0 && ctr2<N)
getPositions(colno+1,ctr2);
}
d[N+val-colno][0]=0;
d[val][1]=0;
d[val+colno][2]=0;
}
void assignPriority()
{long int counter1,counter2,v1,v2;
for(counter1=0;counter1<=N/2;counter1++)
for(counter2=0;counter2<=N/2;counter2++)
priority_array[counter1][counter2]=0;
for(counter1=0;counter1<N;counter1++)
for(counter2=0;counter2<N;counter2++)
{if((v1=counter1+counter2+1)>N) v1=2*N-v1;
v2=N-abs(counter1-counter2) ;
priority_array[counter1][counter2]=2*N+v1+v2-1;
}
printf("\n");
}
void assignSecondOrderPriority()
{static int callCounter=0;
int leastval,k=N/2;
long int row,col,valueToPlace,counter1,counter2;
callCounter++;
for(row=0;row<N;row++)
for(col=0;col<N;col++)
{valueToPlace=0;
for(counter1=0;counter1<N;counter1++)
valueToPlace+=priority_array[counter1][col]+priority_array[row][counter1];
counter1=0;
while(row+counter1<N && col+counter1<N)
{valueToPlace+=priority_array[row+counter1][col+counter1];
counter1++;
};
counter1=0;
while(row+counter1<N && col-counter1>=0)
{valueToPlace+=priority_array[row+counter1][col-counter1];
counter1++;
};
counter1=0;
while(row-counter1>=0 && col+counter1<N)
{valueToPlace+=priority_array[row-counter1][col+counter1];
counter1++;
};
counter1=0;
while(row-counter1>=0 && col-counter1>=0)
{valueToPlace+=priority_array[row-counter1][col-counter1];
counter1++;
};
secondOrderPriority[row][col]=valueToPlace-5*priority_array[row][col];
if(row==0 && col==0) leastval = valueToPlace ;
else
