004-queen_sol.cpp

包含两个文件

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
long sum, n_queen;
int **map, n, flag;
clock_t start_time,end_time;

void queen(int m, long row, long left_clash, long right_clash) {
	long fsb_pos, cur_pos, t, cnt, i, j;
	if (row != n_queen) {
		fsb_pos = n_queen & (~(row | left_clash | right_clash));
		while (fsb_pos != 0) {
			cur_pos = fsb_pos & (-fsb_pos);
			if (flag == 0) {
				t = cur_pos;
				cnt = 0;
				while (t != 0) {
					t = t / 2;
					cnt++;
				}
				map[m][n-cnt] = 1;
			}
			queen(m + 1, row + cur_pos, (left_clash + cur_pos) << 1, (right_clash + cur_pos) >> 1);
			fsb_pos = fsb_pos - cur_pos;
			if (flag == 0) {
				map[m][n-cnt] = 0;
			}
		}
	}
	else {
		sum++;
		if (flag == 0) {
			printf("其中一个解：\n");
			for (i = 0; i < n; i++) {
				for ( j = 0; j < n; j++) {
					printf("%d ", map[i][j]);
				}
				printf("\n");
			}
			flag = 1;
		}
	}
}

int main() {
	int i, j;
	char ch;
	printf("2007级唐郑熠—求n皇后问题解法数量\n");
	printf("（显示解法数量和其中一种解法）\n");
	do {
		printf("\n");
		printf("请输入n(n<33)：");
		scanf("%d", &n);
		getchar();
		if (n < 1 || n > 32) {
			printf("n要在1～32之间！\n");
			continue;
		}
		map = new int*[n];
		for (i = 0; i < n; i++) {
			map[i] = new int[n];
		}
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++) {
				map[i][j] = 0;
			}
		sum = 0;
		n_queen = 1;
		flag = 0;
		printf("正在计算%d皇后问题解法数量……\n", n);
		n_queen = (n_queen << n) - 1;
		start_time = clock();
		queen(0, 0, 0, 0);
		end_time = clock();
		printf("共有%ld种解法, 耗时%ld毫秒\n", sum, end_time - start_time);
		printf("是否继续(y/n)：");
		ch = getchar();
	} while (ch == 'y');
	return 0;
}