八皇后问题

1、介绍

先上张图来说明用回溯法解八皇后问题的每一步：

2、程序

对着严蔚敏的书写的，写好后运行竟然一次性成功了，没有任何bug，我鸡冻了。

上代码：

//	N皇后问题

#include <iostream>
using namespace std;

#define N 8

bool matrix[N + 1][N + 1] = {0};

bool IsLegal(bool matrix[N + 1][N + 1], const int &i, const int &j)
{
	//	判断前面的i-1个棋子与matrix[i][j]是否冲突，i为1时合法

	for (int m = 1; m <= i - 1; ++m) {
		for (int n = 1; n <= N; ++n) {	//	实际每一行只有一个棋子
			if (matrix[m][n] == 1) {
				if ( n == j || abs(i - m) == abs(j - n) )	//	key, not bad
					return false;
			}
		}
	}
	return true;
}

void Print(bool matrix[N + 1][N + 1])
{
	static int count = 1;
	printf("Case %d:\n", count++);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			matrix[i][j] == 1 ? printf("%c ", 2) : printf(". ");
		}
		cout << endl;
	}
	cout << endl;
}

void Trial(const int i)
{
	//	进入本函数时，在N*N的棋盘前i-1行已放置了互不攻击的i-1个棋子
	//	现从第i行起继续为后续棋子选择合适位置

	if (i > N)	//	输出当前的合法布局
		Print(matrix);
	else
		for (int j = 1; j <= N; ++j) {
			matrix[i][j] = 1;
			if ( IsLegal(matrix, i, j) )
				Trial(i + 1);
			matrix[i][j] = 0;
		}
}

int main(void)
{
	Trial(1);

	return 0;
}

运行结果：

3、数学问题

关于n皇后的解的个数（8皇后是92个解）：

n		a(n)
1		1
2		0
3		0
4		2
5		10
6		4
7		40
8		92
9		352
10		724
11		2680
12		14200
13		73712
14		365596
15		2279184
16		14772512
17		95815104
18		666090624
19		4968057848
20		39029188884
21		314666222712
22		2691008701644
23		24233937684440
24		227514171973736
25		2207893435808352
26		22317699616364044

独立解的问题我就不多提了。目前这个数列还没找到通项公式。有意思的是，高斯算八皇后的解的个数时，他算错了，他的答案是76种，不知道他漏了哪种，呵呵。（不过也是4的倍数）

4、想法

那个Trial递归函数我还没弄明白，对着书抄的，要是自己想，难。还有待研究推广。

2012/5/8 更新

把判断是否合法的IsLegal函数优化了，原来的程序是O(N^3)，现在是 O(N^2)：

//	N皇后问题

#include <iostream>
using namespace std;

#define N 8

int matrix[N + 1][N + 1] = {0};
//	matrix[0][j]为空，matrix[i][0]中放第i行的皇后的列坐标（从1开始记）

bool IsLegal(const int &i, const int &j)
{
	//	判断前面的i-1个棋子（坐标是matrix[m][n]）与matrix[i][j]是否冲突，i为1时合法
	for (int m = 1; m <= i - 1; ++m) {
		int n = matrix[m][0];
		if (  n == j || abs(i - m) == abs(j - n) )
			return false;
	}
	return true;
}

void Print(void)
{
	static int count = 1;
	printf("Case %d:\n", count++);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			matrix[i][j] == 1 ? printf("%c ", 2) : printf(". ");
		}
		cout << endl;
	}
	cout << endl;
}

void Trial(const int &i)
{
	//	进入本函数时，在N*N的棋盘前i-1行已放置了互不攻击的i-1个棋子
	//	现从第i行起继续为后续棋子选择合适位置

	if (i > N)	//	输出当前的合法布局
		Print();
	else
		for (int j = 1; j <= N; ++j) {
			matrix[i][j] = 1;
			if ( IsLegal(i, j) ) {
				matrix[i][0] = j;
				Trial(i + 1);
			}
			matrix[i][j] = 0;
		}
}

int main(void)
{
	Trial(1);

	return 0;
}

2012/5/12更新：

推荐：http://topic.csdn.net/t/20060424/13/4709025.html

我在自己机子上运行了下：