搜索
N皇后问题主讲：xxx2016年6月22日星期三2020/2/181第四组Content排序树问题描述效果展示N叉树2020/2/182算法分析·第四组问题描述2020/2/183在nxn格的棋盘上放置彼此不手攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。N皇后问题等价于在nxn格的棋盘上放置n个皇后，任何2两个皇后不放在同一行或者同一列或者同一斜线上。设计一个解n皇后问题的队列式分支限界法，计算在nxn个放个上放置n个彼此不受攻击皇后的一个放置方案。输入文件实例Input.txt5输出文件示例Output.txt13524Content排序树问题描述效果展示N叉树2020/2/184算法分析·第四组基于n叉树的分支限界2020/2/185要解决N皇后问题，其实就是要解决好怎么放置这n个皇后，每一个皇后与前面的所有皇后不能在同一行、同一列、同一对角线，在这里我们可以以行优先，就是说皇后的行号按顺序递增，只考虑第i个皇后放置在第i行的哪一列Queen1Queen4Queen5Queen2Queen3算法分析·第四组基于n叉树的分支限界2020/2/1862122223333333333333333333333333123451234512345123451234512345算法分析·第四组实验代码2020/2/187#includeiostream#includefstream#includealgorithm#includefunctional#includequeueusingnamespacestd;ifstreamin(input.txt);ofstreamout(output.txt);classNode{public:Node(intn){t=0;this-n=n;loc=newint[n+1];for(inti=0;i=n;++i){loc[i]=0;}}Node(constNode&other){this-t=other.t;this-n=other.n;this-loc=newint[n+1];for(inti=0;i=n;++i){this-loc[i]=other.loc[i];Content排序树问题描述效果展示N叉树2020/2/188算法分析·第四组基于排序树的分支限界2020/2/18921222233331234523453333134533331245333312353333123444434544434544424544423544423455355535552555255525算法分析·第四组实验代码2020/2/1810#includeiostream.h#includestdlib.h#includequeueusingnamespacestd;classQNode{public:operatorint()const{returncd;}int*x,i,cd;};classQueen{friendvoidmain();private:voidOutput();voidfifobb();intn,*bestx;boolfound;voidInit(QNode*&E);boolAnswer(QNode*E);voidSave(QNode*&E);voidNewNode(QNode*&N,QNode*&E,inti);boolConstrain(QNode*E);boolGetnext(queueQNode*&Q,QNode*&E);Content排序树问题描述实现效果N叉树2020/2/1811算法分析·第四组2020/2/18122020/2/1813算法分析·第四组