سورس کد 8 وزیر در یک صحفه شطرنج

/* The ' N - Queens ' / Eight Queens Problem :
Here are my solutions to the N-Queens / 8 queens Problem . There are three solutions here .
1. A solution by simple Backtracking / Recursion . (The only array used in this solution is a 1-d array)
2. A solution to the N-Queens / Eight Queens Problem WITHOUT RECURSION . (Using Stacks )
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 <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 if(leastval>valueToPlace) leastval=valueToPlace ;
}

if(callCounter!=8*k-1)
{ for(counter1=0;counter1<N;counter1++)
for(counter2=0;counter2<N;counter2++)
priority_array[counter1][counter2]=secondOrderPriority[counter1][counter2]-leastval;
assignSecondOrderPriority();
}

}

void motionorder(const int N1)
{
long int counter1,counter2,temp1,val1,p;
for(counter1=0;counter1<N1;counter1++)
for(counter2=0;counter2<N1;counter2++)
motionOrder[counter1][counter2]=counter2;
for(counter1=0;counter1<N1;counter1++)
{ for(counter2=1;counter2<N1;counter2++)
{ temp1=secondOrderPriority[counter1][counter2];
val1=motionOrder[counter1][counter2];
p=counter2;
while(temp1<secondOrderPriority[counter1][motionOrder[counter1][p-1]] && p-1>=0)
{motionOrder[counter1][p]=motionOrder[counter1][p-1];p=p-1;};
motionOrder[counter1][p]=val1;
}
}

}