n皇后问题-分支限界法.doc

一、 问题1
1、 问题描述
一、N皇后问题
在N*N的棋盘上放置彼此不受攻击的N个皇后。按照国际象棋的规则，皇后可以攻击与之处于同一行或同一列或同一斜线上的棋子。N皇后的问题等价于在N*N大小的棋盘中放置N个皇后，任何2个皇后都不放在同一行或同一列或同一斜线上。使用队列式分支限界法，求出N个皇后的一种放置方案。
2、 算法设计思想
分支限界法
解向量：因为皇后不能同行或同列，所以我们可以用这样一个解向量来表示问题的解X[x1,x2…xn] x=[1,2,3…n];表示1~n行皇后位于的列数
解空间：因为皇后不能同行同列，因此解空间为排列树，使用广度优先搜索的方式搜索整棵树
剪枝函数：判断新摆放的皇后是否在已经摆放的皇后的斜线上
3、 算法过程描述
第一行第一列放置皇后，这个节点成为拓展节点，产生n-1个活结点，加入队列，第一行第二列到第n列分别产生n-1个活结点，加入队列，从队列取出第一个活结点，即第二行第二列，不满足剪枝函数的要求，除去这个节点，队列中的节点依次取出，满足剪枝函数的节点成为拓展节点产生活结点并加入队列，当成功进行到叶子节点时，就能得到问题的一个解，队列为空时，就得到了所有解
4、 算法实现及运行结果
#include<iostream>
#include<ctime>
using namespace std;

bool isOK(int n, int pieces[])
{ //剪枝函数
//判断当前状态是否合理，即皇后会不会互相攻击
for (int i = 1; i <= n-1; i++)
{
for (int j = i + 1; j <= n; j++)
{
int left = -(j - i);//向左的斜线
int right = (j - i);//向右的斜线
if (pieces[j] == pieces[i] + left||pieces[j] == pieces[i] + right)
{//第i行皇后和第j行皇后会互相攻击
return false;
}
}
}
//所有皇后都不会互相攻击
return true;
}

void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}

void nQueen(int n, int t, int pieces[])
{
if (t > n)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < pieces[i]; j++)
cout << "- ";
cout << pieces[i]<<" ";
for (int j = pieces[i] + 1; j <= n; j++)
cout << "- ";
cout << endl;
}
cout << endl;
}
else
{
for (int i = t; i <= n; i++)
{
swap(pieces[t], pieces[i]);
if (isOK(t, pieces))
{
nQueen(n, t + 1, pieces);
}
swap(pieces[t], pieces[i]);
}
}
}

int main ()
{
int n;
cin >> n;
int *pieces = new int[n + 1];
for (int i = 1; i <= n; i++)
{
pieces[i] = i;
}
nQueen(n, 1, pieces);
cout << "OK" << endl;
system("pause");
}
5、 算法复杂度分析及算法改进
子集树O(n^n)*剪枝函数(包括判断行列和斜线)O(n)=O(n^n+1)