004-queen_array.cpp

来自「包含两个文件」· C++ 代码 · 共 83 行

#include <stdio.h>
#include <time.h>
int n, *p, flag;
long cnt;
clock_t start_time,end_time;

int judge(int i, int j) {
	int k;
	if (j > n) {
		return 0;
	}
	for (k = i - 1; k >= 1; k--) {
		if (j == p[k]) {
			return 0;
		}
		if (i - k == p[k] - j) {
			return 0;
		}
		if (i - k == j - p[k]) {
			return 0;
		}
	}
	return 1;
}

void print() {
	int i, j;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			if (p[i] == j) {
				printf("1 ");
			}
			else {
				printf("0 ");
			}
		}
		printf("\n");
	}
}

void n_queen(int m) {
	int i;
	if (m > n) {
		cnt++;
		if (flag == 0) {
			print();
			flag = 1;
		}
		return;
	}
	else {
		for (i = 1; i <= n; i++) {
			if (judge(m, i) == 1) {
				p[m] = i;
				n_queen(m+1);
			}
		}
	}
}

int main() {
	char ch;
	printf("2007级唐郑熠—n皇后问题求解\n");
	printf("（用数组处理，速度慢，但可求解任意n值）\n");
	do {
		printf("\n");
		printf("请输入n值：");
		scanf("%d", &n);
		getchar();
		p = new int[n+1];
		cnt=0;
		flag = 0;
		start_time = clock();
		n_queen(1);
		end_time = clock();
		printf("共有%ld种解！\n", cnt);
		printf("共用时%ld毫秒\n", end_time - start_time);
		printf("是否继续(y/n)：");
		ch = getchar();
	} while (ch == 'y');
	return 0;
}