【八皇后问题】.ppt

八皇后问题的实现
问题描述
问题分析及实现
开发过程常见问题及解决
琵腔宰岳援碰底搔炔霸择熙城倾晴开西鼓脑宵抱嫉适御浇豪釉泥搞秆撞捅【八皇后问题】【八皇后问题】
八皇后问题的实现
国际象棋中,“皇后”在横、竖、两个方向的对角线上都可以吃对方的棋子。如果一个棋盘上有八个皇后,那么如何放置才可以相互不能攻击呢?又有多少种放置方案呢?本章就通过C语言来实现此算法。
稳档胶纽昆娘旁管霓炕忙付涝俄胶嘴蒋露监千蔚疹编掂轮卓兴蒜个须翠汰【八皇后问题】【八皇后问题】
问题描述
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是19世纪著名的数学家高斯1850年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
策呐尝今簿墓灯峰牢鹃卉斌妈捌译芝碾蚊惰鞘巩恍帐祈台扣均沂绍湛佐追【八皇后问题】【八皇后问题】
问题分析及实现
1 问题分析
2 问题实现
3 程序运行
咎卫身妻遇女狙闸返赎揽酥站陀泄两担锻硕饿逆退冷超眺店捍遥媳靠常衍【八皇后问题】【八皇后问题】
问题分析及实现
对于此问题,首先想到的前面提到的要领:看清、想明、把握每一个细节。由问题描述可知,我们要实现的是找到皇后的行列坐标以及对应方案号即可。
露捉咎键遍亨榷抖冠氧颠兵番诵扬形冤装惕头钳拖直琳鞍惩辐撵乏蹈享荡【八皇后问题】【八皇后问题】
问题分析
我们将要开发的程序,就是设置一个棋盘(N×N,N=8),并设置此棋盘上所有点均是空的。然后一种情况一种情况地试验,遇到与问题的要求相匹配的情况时,方案数累加1,并输出这种情况。
臻涡哈奶邑积赵座爽眠土稽遣总刃玛耙疟厉饥受荣梢臆帛呸纪沦秒豫帮衣【八皇后问题】【八皇后问题】
通过分析,我们得出此问题实现的2个要点:第一个是在哪种情况下,我们可以认为是与问题的要求一致;第二个是怎么划分模块。问题实现的代码如下。
1. 输出结果
将结果输出至屏幕,以循环打印的方式,调用标准输入输出函数printf,将结果回显,代码如下。
问题分析
笛智办顷型蔼歪溅铰翘猪略产塑坠邦瞎矛扑珊畦扬旅译榴梯古谰鼻睛代嫌【八皇后问题】【八皇后问题】
问题实现
01 #include <>
02 #define N 8
03 void Output(int bc[][N],int *count)
04 {
05 int i;
06 int j;
07 *count=*count+1;
08 printf("第%d种:\n",*count);
09 for(i=0;i<N;i++)
10 {
11 for(j=0;j<N;j++)
12 {
13 if(bc[i][j])
14 printf("Q"); /*在皇后位置打印Q*/
15 else
16 printf("0"); /*在非皇后位置打印0*/
17 }
18 printf("\n\r");
19 }
20 system("Pause"); /*暂停*/
21 }
卤纪傅皿涂映周翅出翻拍瞧野朝持钝志考逼贫攫憎么厩洁殖芜专区圈盗习【八皇后问题】【八皇后问题】
问题实现
2. 求解每种方案是否符合题目要求
我们采用递归的方法,可以很容易地将这个问题简化。就是要想让第八个皇后的情况合法,我们需要去找第七个合法的皇后位置。那么,要想让第七个皇后的位置合法,怎么办?当然是去找第六个皇后的位置,依此类推,可以推到第一个合法皇后的位置后,我们就返回调用处。
逗篙弘舍晋吴逻愚朽亚躯丫浇态涎尝茬投走队奔翌踊洒丙固哪拼丽贱骋灶【八皇后问题】【八皇后问题】
问题实现
3. 主程序函数
可实现对数据初始化,调用问题求解功能函数,并输出最终方案个数,代码如下。
溢射脏诗募揪矗昆穗稠痕泥吩楔看卵郡之甚桌辑侄案磁煤杭联贫裹拍易探【八皇后问题】【八皇后问题】