网站建设目的,河北网络推广公司,衡水网站建设地方,linux wordpress nginx一、问题描述
问题描述#xff1a;在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n皇后问题等价于在n*n的棋盘上放置n个皇后#xff0c;任何2个皇后不放在同一行或同一列或同一斜线上。 …一、问题描述
问题描述在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n皇后问题等价于在n*n的棋盘上放置n个皇后任何2个皇后不放在同一行或同一列或同一斜线上。
算法设计设计一个解n皇后问题的队列式分支限界法计算在nn个方格上放置彼此不受攻击的n个皇后的一个放置方案。
*数据输入由文件input.txt给出输入数据。第一行有1个正整数n。
*结果输出将计算的彼此不受攻击的n个皇后的一个放置方案输出到文件output.txt。文件的第一行是n个皇后的放置方案。
输入文件
input.txt
5
output.txt
1 3 5 2 4
二、问题分析 1.题目分析
对于每一个放置点而言它需要考虑四个方向上是否已经存在皇后。分别是行列45度斜线和135度斜线。
行每一行只放一个皇后直到我们把最后一个皇后放到最后一行的合适位置则算法结束。
列列相同的约束条件只需判断j是否相等即可。
45度斜线和135度斜线约束条件——当前棋子和已放置好的棋子不能存在行数差的绝对值等于列数差的绝对值的情况若存在则说明两个棋子在同一条斜线上
2.算法选择
用分支限界法来解决n皇后问题。对于该问题它满足两种树结构。这里由于每一个合适的放置点出现最优解的概率是相等的因此不需要使用优先队列。编译器提供了一个已经封装好的队列queue。
A.子集树。我们把行约束条件和其它约束条件放在一起即认为每一行棋子都有n个位置可以放置。于是它的空间结构如下 假设n3这个图只画出了两层
B.排列树。我们把行约束条件单独拿出来也就是我们认为总共有八个皇后这八个皇后必须都要放上去但是放的位置不同显然这是一个排列树。于是它的空间结构如下 这里由于我们还存在着其他的约束条件并且行约束条件和这些条件完全可以放在一起于是我就选择了相对容易理解的子集树作为解空间结构。
#includeiostream
#includequeue
#includecmath
#includevector
#includefstream
#includesstream
using namespace std;//定义一个节点类
struct Node{int number;vectorintx;//保存当前解
}; //定义一个Queen的类
class Queen{friend int nQueen(int);public:bool Place(Node q,int n);void Research();int n;//皇后个数int *bestx;//最优解
}; //判断是否能够放置的函数
bool Queen::Place(Node q,int n)
{for(int j1;jn;j)if((abs(n-j)abs(q.x[j]-q.x[n]))||(q.x[j]q.x[n])) return false;return true;
}void Queen::Research()
{queueNodeQ;//活节点队列Node sign;sign.number-1;Q.push(sign);//同层节点尾部标志int t1;//当前节点所处的层Node Ew;//当前扩展节点 Ew.number0; //搜索子集空间树while(1){ //检查所有的孩子节点 for(int k1;kn;k){//把当前扩展节点的值赋给下一个节点 Node q;q.numbert; q.x.push_back(0);//第一个位置为0 for(int i1;it;i) q.x.push_back(Ew.x[i]);q.x.push_back(k);if(Place(q,t))Q.push(q);} //取下一扩展节点,取出赋值给Ew EwQ.front();Q.pop();if(Ew.number-1){//同层节点尾部标记t;//进入下一层 Q.push(sign);//增加标记//继续往下去下一个节点 EwQ.front();Q.pop();} if(Ew.numbern){//找到最后一层的节点 for(int i0;in;i) bestx[i]Ew.x[i];break;} }
}int nQueen(int n)
{Queen X;X.nn; X.bestxnew int[n1];for(int i0;in;i) X.bestx[i]0;X.Research();for(int i1;in;i){coutX.bestx[i] ;}
}int main(){int N;cout输入方格的行数; cinN; cout输出计算的彼此不受攻击的n个皇后的一个方案; nQueen(N);return 0;
}
