N皇后算法

最近正在学习回溯法，遇到的第一个问题就是n皇后问题，问题如下：

专注于为中小企业提供成都网站设计、做网站服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业瑞丽免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了超过千家企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。

要求在一个n×n的棋盘上放置n个皇后，使得任意两个皇后不在同一行或同一列或同一斜线上。

直接上代码：

#include
#include
using namespace std;
void NQueen(int, int, int*);

int main()
{
	int x[4] = { -1, -1, -1, -1 }; //4 * 4的棋盘测试
	NQueen(0, 4, x);
	return 0;
}

bool Place(int k, int i, int* x) //用来判断皇后是否在同一列或者同一斜线，k表示当前行号，i记录当前的列号，x记录了当前棋盘信息
{
	for (int j = 0; j < k; j++)
	{
		if ((x[j] == i) || abs(x[j] - i) == abs(j - k))
			return false;
	}
	return true;
}

void NQueen(int k, int n, int* x)
{
	for (int i = 0; i < n; i++) //遍历当前递归到行的所有列号
	{
		if(Place(k, i, x)) //判断当前位置是否可行
		{
			x[k] = i;
			if (k == n - 1) //如果到了最后一行，说明是一个可行解，输出
			{
				for (int j = 0; j < n; j++)
				{
					cout << x[j] << " ";
				}
				cout << endl;
			}
			else //深度优先进入下一层递归
			{
				NQueen(k + 1, n, x);
			}
		}
	}
	return;
}

本文名称：N皇后算法
URL分享：http://cdiso.cn/article/dsoipjh.html