eightqueens.cpp

本人自编的解八皇后问题的程序

// EightQueens.cpp : 定义控制台应用程序的入口点。
// 找出给定初始点后的一组可行解
// 如果初始点后无可行解
// 则自动搜索以初始点前面的点为初始点的可行解
// 并输出结果, 棋盘上的1表示皇后所占据的位置

#include "stdafx.h"
#include <malloc.h>
#include <math.h>
#define Error -1
#define N 8		//Total of queens, you can modify here
#define InitPt 0    //You can change initialized point here :-) zero means the first point on line 1

int queen(int q[],int,int);
int _tmain(int argc, _TCHAR* argv[])
{
	int i,j,q[N];
	printf("You initialized point is the %dst Point\n",(int)(InitPt+1));
	if(queen(q,N,0)==-1){
		printf("No solution of the problem Or parameter error!\n");
	}
	else{
		if(queen(q,N,InitPt)==-1){ //search before initialized point if no solution found.
			queen(q,N,0);
			printf("There is(are) only solution(s) before initialized point!\n");
		}
		for(i=0;i<N;i++){
			for(j=0;j<q[i];j++) printf("%3d",0);
				printf("%3d",1);
		for(j=q[i]+1;j<N;j++) printf("%3d",0);
			printf("\n");
		}	
	}
	return 0;
}

int queen(int q[],int n,int InitPoint)
{
	int i,j,k;
	int attack;  
	int error; 
	int level=0; 
	//number of queens which have been arranged; 
	//a flag controls the circulation
	for(i=0; i<n; i++)
		q[i]=0;        //initialize the matrix of n queens problem
	//InitPoint=(int)InitPoint;
	if(InitPoint>n-1||InitPoint<0||n<=0) return Error;
	q[0]=InitPoint;        
	k=0;
	while((++level)<n){
		error=0;//zero means there's no problem of the solution
		attack=1;
		while(attack==1&&k<n){
			attack=0;
			for(j=0;j<level;j++)
				if(k==q[j]||abs(k-q[j])==abs(level-j)) 
					attack=1;
					//check if the position of all the queens are legal
					//attack = 0 means no attacking
			if(attack==1){
				if(k==n-1) error=1; 
				k++;
			}
		}
		if(error==0){
			q[level]=k;
			k=0;
		}
		else{
			do{
				--level;
				if(level>=0) k=q[level]+1;
			}
			while(k>=n&&level>=0);  
			//go back to the upper level if no solution found
			--level;
		}
		if(level<-1) return Error;
	}
	return 1;
}