N皇后问题实验报告(共5页).doc
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《N皇后问题实验报告(共5页).doc》由会员分享,可在线阅读,更多相关《N皇后问题实验报告(共5页).doc(5页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上一、 实验内容在nn格的棋盘上放置彼此不受攻击的n个皇后,按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子,求解可以放置的方法种数。二、 问题分析n后问题等于于在nn格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。即规定每一列放一个皇后,不会造成列上的冲突;当第i行被某个皇后占领后,则同一行上的所有空格都不能再放皇后,要把以i为下标的标记置为被占领状态。三、 算法设计1. 解决冲突问题: 这个问题包括了行,列,两条对角线; 列:规定每一列放一个皇后,不会造成列上的冲突; 行:当第i行被某个皇后占领后,则同一行上的所有空格都
2、不能再放皇后,要把以i为下标的标记置为被占领状态; 对角线:对角线有两个方向。在这我把这两条对角线称为:主对角线和从对角线。在同一对角线上的所有点(设下标为(i,j)),要么(i+j)是常数,要么(i-j)是常数。因此,当第i个皇后占领了第j列后,要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。 2. 算法设计 因为n皇后问题,从n大于11开始求解过程耗时就很长,所以定义x数组的最大值MAXNUM=30;即最大可解决30皇后问题。1) 判断当前位置是否可放置皇后皇后k在第k行第xk列时,xi=xk 时,两皇后在同一列上;abs(xi-xk)=abs(i-k)时,两皇后在同一斜线上;
3、两种情况两皇后都可相互攻击,返回false表示不符合条件。bool Place(int k)int i;i=1;while(ik)if(xi=xk|abs(xi-xk)=abs(i-k)return false;i=i+1;return true;2) 输出当前解void Print(int x,int n)num+;printf(第%dt种解法:(,num);for(int i=1;i0)xk+=1;while(xk=n&!Place(k)xk+=1;if(xk=n)if(k=n)Print(x,n);elsek=k+1;xk=0;/回溯至上一行;elsek-;3. 实验结果及分析n皇后问题
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 皇后 问题 实验 报告
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内