N皇后问题完全优化指南 | aheadlead的生活博客

N皇后问题完全优化指南 | aheadlead的生活博客

第二个版本 更好的描述状态
我们可以直接用一个整数型的一维数组来描述一个棋盘：chessboard[i]的含义是第i列的皇后在chessboard[i]行上。

	// 判断当前局面是否合法 int is_valid()
	{
	int queen1, queen2;
	for (queen1=0; queen1<N; ++queen1)
	{
	for (queen2=0; queen2<queen1; ++queen2)
	{
	if (chessboard[queen1] == chessboard[queen2]) // 横向冲突
	return false;
	if (ABS(chessboard[queen1]-chessboard[queen2]) == ABS(queen1-queen2)) // 斜向冲突
	return false;
	}
	}
	return true;
	}
	// 把第queen_number号皇后摆到棋盘上去
	void place_queen(int queen_number)
	{
	int row;
	if (queen_number == N)
	{
	// 如果已经摆了N个皇后
	// 就判断当前局面是否合法
	if (is_valid())
	solution_total = solution_total+1;
	return;
	}
	// 枚举新皇后的位置
	for (row=0; row<N; ++row)
	{
	// 将第queen_number号皇后摆到棋盘的row行column列
	chessboard[queen_number] = row;
	// 放置下一个皇后
	place_queen(queen_number+1);
	}
	}

第三个版本 剪枝优化

如果你摆到第k个皇后时候（k∈{1,2,3,⋯,N}），发现第k个皇后和第1个皇后到第k−1之间的某一个皇后已经发生冲突了，那么第k号皇后后面的皇后也就没必要摆了。

这里的is_vaild()函数和之前的版本的含义已经有点不太一样了。在这里每放一个皇后就判断这个皇后是否符合互不攻击规则，而之前的版本，是所有的皇后都放好之后，才判断所有的皇后对，是否都符合互不攻击规则。这里is_vaild()的时间复杂度是线性的。

	int is_vaild(int current_queen) {
	int queen;
	for (queen=0; queen<current_queen; ++queen)
	if (chessboard[queen] == chessboard[current_queen] ||
	ABS(chessboard[queen]-chessboard[current_queen]) == ABS(queen-current_queen))
	return false;
	return true;
	}
	// 把第queen_number号皇后摆到棋盘上去
	void place_queen(int queen_number)
	{
	int row;
	if (queen_number == N)
	{
	// 如果已经摆了N个皇后
	solution_total = solution_total+1;
	return;
	}
	// 枚举新皇后的位置
	for (row=0; row<N; ++row)
	{
	// 将第queen_number号皇后摆到棋盘的row行queen_number列
	chessboard[queen_number] = row;
	if (is_vaild(queen_number)) // 判断当前局面下queen_number号皇后与之前的换后是否有冲突
	{
	place_queen(queen_number+1); // 放置下一个皇后
	}
	}
	}

第四个版本 is_valid()的优化

我们有能力在放置某个皇后的时候，知道将要放置的这个皇后的行有没有其他的皇后。

我们再声明一个数组row_available[]用来记录每一行有没有被别的皇后占用，row_available[i]==1代表当前第i行存在皇后，若row_available[i]==0代表第i行不存在皇后。

这样我们可以在某次放置皇后时，直接的知道这一行有没有别的皇后。

	void place_queen(int queen_number) {
	int row;
	if (queen_number == N)
	{
	// 如果已经摆了N个皇后
	solution_total = solution_total+1;
	return;
	}
	// 枚举新皇后的位置
	for (row=0; row<N; ++row)
	{
	// 将第queen_number号皇后摆到棋盘的row行queen_number列
	if (row_available[row] == 0)
	{
	row_available[row] = 1;
	chessboard[queen_number] = row;
	if (is_vaild(queen_number)) // 判断当前局面下queen_number号皇后与之前的换后是否有冲突
	{
	place_queen(queen_number+1); // 放置下一个皇后
	}
	row_available[row] = 0;
	}
	}
	}

第五个版本 去掉is_valid()

既然我们能用一个数组描述所有的行是否已经存在皇后了，那么对于对角线我们能不能做一样的优化呢？看到这种句式，马上就能反应过来”是可以的“的答案...

没错，上两张图。

我们先看第二张图（因为第二张图离这行文字比较近，充分的体现了我人性化的关怀 ; ) ）。可以看到，格子里的数字是行号减去列号加上边长减一。

如右上角的格子，0=0−7+8−1。

可以看到，每个数字对应一条右下方向（）的对角线，我们声明一个rdiag_available[]用于记录这条对角线上有没有皇后即可。处理的方法和上一版本一样。

左下方向（，第一张图）的可以类似地声明一个数组ldiag_available[]来记录。

diag代表diagonal，对角的意思。

	void place_queen(int queen_number) {
	int row;
	if (queen_number == N)
	{
	// 如果已经摆了N个皇后
	solution_total = solution_total+1;
	return;
	}
	// 枚举新皇后的位置
	for (row=0; row<N; ++row)
	{
	if (row_available[row] == 0 &&
	rdiag_available[row-queen_number+N-1] == 0 && // 右下对角线方向
	ldiag_available[row+queen_number] == 0) // 左下对角线方向
	{
	row_available[row] = 1;
	rdiag_available[row-queen_number+N-1] = 1;
	ldiag_available[row+queen_number] = 1;
	chessboard[queen_number] = row; // 将第queen_number号皇后摆到棋盘的row行queen_number列
	place_queen(queen_number+1); // 放置下一个皇后
	row_available[row] = 0;
	rdiag_available[row-queen_number+N-1] = 0;
	ldiag_available[row+queen_number] = 0;
	}
	}
	}

第六个版本 镜像优化

不难观察到，对于某个局面，我们对它进行上下翻转之后，得到的新局面，仍然是一个符合互不攻击规则的局面。根据这一点，我们可以将列举局面的范围缩小一半（对于偶数边长的棋盘来说是一半，对于奇数边长的棋盘却不是）

第一个皇后（最左边的皇后）我们可以考虑放置在第0行到第7行，但现在只需要考虑放置在第0行到第3行了，因为当第一个皇后在第3行到第7行的时候的局面，总是可以通过上下翻转，由第一个皇后在第0行到第3行的某个局面得来。

也就是说第一个皇后在第0行到第3行时找到了一个答案，我们直接上下翻转就能得到另外一个答案。（易证符合互不攻击规则的局面进行上下翻转前后，不可能是同一个局面。）

所以说，我们第一个皇后只需要枚举一半的范围。

对于偶数边长，我们只用列举一半，每种符合规则的情形计数两次即可。但对于奇数边长，我们要特殊处理一下中间的那一行，中间的那一行不存在上下对称之说，所以中间这一行只要计数一次。

	// 皇后从start_row行开始放，直到end_row行（前闭后开） void place_queen(int queen_number, int start_row, int end_row)
	{
	int row;
	if (queen_number == N)
	{
	// 如果已经摆了N个皇后
	solution_total = solution_total+1;
	return;
	}
	// 枚举新皇后的位置
	for (row=start_row; row<end_row; ++row)
	{
	if (row_available[row] == 0 &&
	rdiag_available[row-queen_number+N-1] == 0 && // 右下对角线方向
	ldiag_available[row+queen_number] == 0) // 左下对角线方向
	{
	row_available[row] = 1;
	rdiag_available[row-queen_number+N-1] = 1;
	ldiag_available[row+queen_number] = 1;
	chessboard[queen_number] = row; // 将第queen_number号皇后摆到棋盘的row行queen_number列
	place_queen(queen_number+1, 0, N); // 放置下一个皇后
	row_available[row] = 0;
	rdiag_available[row-queen_number+N-1] = 0;
	ldiag_available[row+queen_number] = 0;
	}
	}
	}
	// 开始放置皇后
	place_queen(0, 0, N/2);
	// 由于上下镜像导致对称的关系，解的数量能直接乘以二
	solution_total = solution_total*2;
	// 当棋盘边长为奇数的时候要特别考虑一下第一个皇后放N/2行的情况（不要忘了是从第0行开始数）
	if (N % 2 == 1)
	place_queen(0, N/2, N/2+1);
	printf("%d\n", solution_total);

第七个版本 位运算 http://www.matrix67.com/blog/archives/266

	int upperlim = (1<<N)-1; void test(int row, int ld, int rd)
	{
	int pos, p;
	if (row != upperlim)
	{
	pos = upperlim & (~(row | ld | rd));
	while (pos)
	{
	p = pos & (~pos + 1);
	pos -= p;
	test(row | p, (ld | p) << 1, (rd | p) >> 1);
	}
	}
	else
	solution_total++;
	}

第八个版本 位运算上的镜像优化

	for (i=0; i<N/2; ++i) test(1<<i, 1<<(i+1), 1<<(i-1));
	solution_total = solution_total*2;
	if (N & 1)
	test(1<<(N/2), 1<<(N/2+1), 1<<(N/2-1));

第九个版本 递归改非递归

第十个版本 发挥多核优势

如果你只要得到N皇后（N要很大）问题的一个解，可以试试通过matrix67大牛介绍的神奇环中环构造法（传送门）。也可以试试一种所谓人工智能里面的“乱搞”算法，大题思路就是先随机生成一个局面，然后不断的选择一个最佳的皇后并调整她的位置，使得整体朝着没有冲突的方向发展。出于自身蒟蒻的能力，我没法严谨的描述这个算法，感兴趣的同学可以去看看（传送门）。

如果你只想得到N皇后下，解的数量有多少的话，其实存在一种方法能在常数时间内算出来...（众人：那你写这篇文章有P用啊...）

最后推荐一篇文章，题目叫《N皇后问题解的构造及等价性分析》，囊括了我对N皇后问题的认知。

Related: 八皇后问题算什么，来看看无穷皇后问题吧
皇后也疯狂：如何在1分钟内摆放300万个皇后
Read full article from N皇后问题完全优化指南 | aheadlead的生活博客