eightqueens.cpp

来自「这个是编译原理课程的词法分析器」· C++ 代码 · 共 61 行

#include <stdio.h >
#include <conio.h >
#include <math.h >

#define QUEENS_NUM 8

int count=0;
int site[QUEENS_NUM];

/*
 * 输出一个解，即一种没有冲突的放置方案
 */
void output(){
	int i;
	printf("No.%-5d ",++count);
	for(i=0;i<QUEENS_NUM;i++)
		printf("%d ", site[i]);
	printf("\n ");
}


/*
 * 判断第n个皇后放上去之后，是否合法，即是否无冲突
 */
int isValid(int n){
	int i;
	for(i=0;i<n;i++){
		if(site[i]==site[n])
			return 0;
		if(abs(site[i]-site[n])==(n-i))
			return 0;
	}
	return 1;
}

/*
 * 递归放置第n个皇后，程序的核心
 */
void queen(int n){
	int i;
	if(n==QUEENS_NUM){
		output();
		return;
	}
	for(i=1;i<=QUEENS_NUM;i++){
		site[n]=i;
		if(isValid(n))
			queen(n+1);
	}
}


/*
 * 主函数
 */
void main(){ 
	queen(0);
	getch();
}