[codeup] 2046 八皇后

题目描述

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。

对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。

给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

输入

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1 <= b <= 92)

输出

输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。

样例输入

3

6

4

25

样例输出

25713864

17582463

36824175

思路

八皇后问题的答案有92个，首先按照字典序生成这92个答案，然后根据下标查询即可。生成八皇后直接按行的顺序生成八个全排列，这八个全排列即为八行中每行皇后的位置，也就是列号，然后检查满足限制条件即可。

简单的暴力生成版本：

int count = 0;

int n, p[maxn];

bool hash_table[maxn] = {false};

void generate_p(int index)

{

	if (index == n + 1) { // 判断全排列满足条件

		bool flag = true;

		for (int i = 1; i <= n; i++) {

			for (int j = i + 1; j <= n; j++) {

				if (abs(i - j) == abs(p[i] - p[j]))

					flag = false;

			}

		}

		if (flag)

			count++;

		return;

	}

	for (int x = 1; x <= n; x++) {

		if (hash_table[x] == false) {

			p[index] = x;

			hash_table[x] = true;

			generate_p(index + 1);

			hash_table[x] = false;

		}

	}

}

由于某些全排列序列在前几个数出来时就可以判断是错误答案了，所以可以稍微优化以下代码，加上剪枝回溯的版本：

int count = 0;

int n, p[maxn];

bool hash_table[maxn] = {false};

void generate_p(int index)

{

	if (index == n + 1) {

		count++;

		return;

	}

	for (int x = 1; x <= n; x++) {

		if (hash_table[x] == false) {

			bool flag = true; // 剪枝

			for (int pre = 1; pre < index; pre++) {

				if (abs(index - pre) == abs(x - p[pre])) {

					flag = false;

					break;

				}

			}

			if (flag == true) {

				p[index] = x;

				hash_table[x] = true;

				generate_p(index + 1);

				hash_table[x] = false;

			}

		}

	}

}

代码

#include <cstdio>

#include <algorithm>

const int maxn = 11;

int n, p[maxn];

bool hash_table[maxn] = {false};

int count = 0;

int solve[100] = {0};

void generate_p(int index)

{

	if (index == n + 1) {

		count++;

		int tmp = 0;

		for (int i = 1; i <= n; i++) {

			tmp = tmp * 10 + p[i];

		}

		solve[count] = tmp;

		return;

	}

	for (int x = 1; x <= n; x++) {

		if (hash_table[x] == false) {

			bool flag = true;

			for (int pre = 1; pre < index; pre++) {

				if (abs(index - pre) == abs(x - p[pre])) {

					flag = false;

					break;

				}

			}

			if (flag == true) {

				p[index] = x;

				hash_table[x] = true;

				generate_p(index + 1);

				hash_table[x] = false;

			}

		}

	}

}

int main()

{

	int m, t;

	n = 8;

	generate_p(1);

	scanf("%d", &m);

	while (m--) {

		scanf("%d", &t);

		printf("%d\n", solve[t]);

	}

	return 0;

}

巴特西

[codeup] 2046 八皇后

题目描述

输入

输出

样例输入

样例输出

思路

代码

最新文章

热门文章