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

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

boolisOK(intn,intpieces[])
{//剪枝函数
//判断当前状态是否合理，即皇后会不会互相攻击
for(inti=1;i<=n-1;i++)
{
for(intj=i+1;j<=n;j++)
{
intleft=-(j-i);//向左的斜线
intright=(j-i);//向右的斜线
if(pieces[j]==pieces[i]+left||pieces[j]==pieces[i]+right)
{//第i行皇后和第j行皇后会互相攻击
returnfalse;
}
}
}
//所有皇后都不会互相攻击
returntrue;
}

voidswap(int&a,int&b)
{
intt=a;
a=b;
b=t;
}

voidnQueen(intn,intt,intpieces[])
{
if(t>n)
{
for(inti=1;i<=n;i++)
{
for(intj=1;j<pieces[i];j++)
cout<<"-";
cout<<pieces[i]<<"";
for(intj=pieces[i]+1;j<=n;j++)
cout<<"-";
cout<<endl;
}
cout<<endl;
}
else
{
for(inti=t;i<=n;i++)
{
swap(pieces[t],pieces[i]);
if(isOK(t,pieces))
{
nQueen(n,t+1,pieces);
}
swap(pieces[t],pieces[i]);
}
}
}

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