Eight Queens Problem

/* The ' N - Queens ' / Eight Queens Problem :
Here are my solutions to the N-Queens / 8 queens Problem . There are three solutions here . SOLUTION #1. A solution by simple Backtracking / Recursion . (The only array used in this solution is a 1-d array)

SOLUTION #2. A solution to the N-Queens / Eight Queens Problem WITHOUT RECURSION . (Using Stacks )

SOLUTION #3. Another recursive function with better ( but vague ) heuristics . The heuristic was completely my own (as far as I know ) , but a bit arbitrary to some extent . Anyway , I was glad to see that it produced results pretty quickly uptil N = 70 or so . ( That's on a AMD K-6 Machine with 128 MB Ram. )

IMPORTANT , PLEASE READ ::::
Regarding the display of solutions :
The solutions appear in the following format ::
Example : SOLN 1 : (1,1) (2,5) (3,8) ..... This means that the queen in the first row must be placed in column 1 , the queen in the second row must be placed in column 5 , the queen in the third row must be placed in col 8... and so on ....( obviously , there can only be 1 queen for each column or row ) .

NOTE : Both solutions 2 & 3 implement the famous method of Niklaus Wirth to use 3 boolean arrays to marks squares already visited . The first solution , though quite economical on memory , is very much inefficient as far as speed is concerned . I put it up because it was the first solution which was completely thought of by me .
*** ALL THESE PROGRAMS HAVE BEEN TRIED AND TESTED IN TURBO-CPP *** ------------------------------------------------------------------------------------ */ SOLUTION #1
#include
#include
#include
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("\n THE N QUEENS PROBLEM ");
  printf("\n Number Of Rows(N) For NxN Chessboard.");
  scanf("%d",&N);
  a=(int *)(malloc(sizeof(int)*N));
  printf("\n All possible Solutions .. \n");
  printf("\n In 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    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     printf("(%d,%d) ",i+1,a[i]+1);
  if(counter%10==0)
 {
    printf("\n Enter 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 # include # include 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 # include # include # include 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=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=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 && ctr2N) 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=0) {valueToPlace+=priority_array[row+counter1][col-counter1]; counter1++; }; counter1=0; while(row-counter1>=0 && col+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 if(leastval>valueToPlace) leastval=valueToPlace ; } if(callCounter!=8*k-1) { for(counter1=0;counter1=0) {motionOrder[counter1][p]=motionOrder[counter1][p-1];p=p-1;}; motionOrder[counter1][p]=val1; } }