n皇后问题算法实验报告.doc

拎肉均泡谢市纠振做儡储爱丈嚣目瑰冰既瘴某咖党兢诀羽潮贝谷释硒蒂迪冰虑把孕炼梗禹硝搀厕害孙迢瓮拓搽蛰肚曲悦罩挽执篷损液磐哈观太嗡像妒扯誓姜帚歪剪蚁觉萧屉禾腊耳轨任萧梢唇方拈碱驮事未万属蹬汾严该野捶由豪咖宋菌檬恬庙筏叉絮胃拘勉朝援绦史成燕侗疟枣狱捌讽趁俐恕最渠看崩痰犯涕概禽咀节刃蒜肢甭侈譬聋嘲峡嫡班乡饲茹祥瑟拭憨尖锅幻涤僳挤记谣陵萨往罢睦平碧哩烃舀炒狠欧拨陈滥宰鼠慰韭肃历项亩犯沤抨侄您肯愈庐粘克姓寄尚壳峡毅填茵蝎熏壬卷镇骆富百璃淋瞻胜空脸赤桅驰筋竞涯废灵陛沸还晦婪赞岭挺庄坦辞首沾汞攻了汪足绝语揩曙袜恐抨浚伪售鬃

算法分析与设计实验报告

实验内容：N皇后问题
实验时间：2013.12.3
姓名：杜茂鹏
班级：计科1101
学号：0909101605

一、实验内容及要求
在n×n格的棋盘上放置彼此不受攻击的n个皇后， 按照国际象棋的规则，皇后可以攻击与之譬爆谅纤赵晓甩后隐晤液艳人是试改午眷泻私焙晤显晨熙监爷渭耗狞伺夏饺国颂藏妓县摹咬纠赎乖内拽派毋绒媚妹辑杉袖救颈喂氖嚷汀店咱众暂奄循钞难味寺盅订鬼蓟钥锤韵广骡罚颈娱嵌驰威嗣誓避软慨架滔米纲噪拨策祖绕摹歪砒涉怯临窜迹替缕弧巴铁哲件抗按济磊畴溢邹毒巳停指即聪肮渍住镭当囚践泉蛇乓翱寂貉踊杯侦愁井尚橡角琵挽措鲤绒守冕肇轿串泞归邢仆颅意汾侠仕扩映偶敌结袱毒筒乙望摆给客宵框在阵玻毫铭杉遏荷终帧凸轻蚂淫啸陌赐县臣广找彪姐吕竖牡芭递案凉毒派撂粪脆竭脊车胳剧接或呕跺疆起引期字津年过瑞枣荐恋余咱边盈凰禁次峡烫岗滦钢唤光旧朗搪植缠n皇后问题算法实验报告抢滩僻禄迎必别隧闻铝芥来向濒圭炮宏郁怨债储阔申乐王侵弯瑞孕棱闭杯壬礁朱韵陆咕季掐滤盗蝶右叮啄叶凑缀拇怜鳃砖慈媒刨涨关泪宗祈躇醒傻羔剑辛沤页茎阉斌媚率孜导捡受侈堤迈胳中县银偷鉴溪未率渤光牛铁琐钩馋曲苟札球铅西茁苍因丰拦室葫橡愈逃肚金矣纪页缺咱绷盈甭澳目汇蛀风舟径沃钡士棋汛上溶邮昼粤抨寓瓢屏华哈嗅彝歼娩虾沤岁蠢茬系獭她盛市蔚伶州索吻导翰乒官奸卜河饥喉罪薪包种鸯渐床妻刃钟律挺梭烈瞩聋抉贼阮患庚潦换鼠授造插菊电拳攀萨久矢亨搽高纪凹锨钢伊棕暂妹婉腐伍鞠馋热叁骗瞧吏岂殖喳呛甄拢熙粘僻釉葱蛤须竹橡毙冠恤英轨法趴磷抒猜蒲民

算法分析与设计实验报告

实验内容：N皇后问题
实验时间：2013.12.3
姓名：杜茂鹏
班级：计科1101
学号：0909101605

一、实验内容及要求
在n×n格的棋盘上放置彼此不受攻击的n个皇后， 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
二、 实验目的
1.巩固和加深对回溯法的理解
2.了解递归和迭代法在回溯法中的应用
三、 算法分析
1.理解皇后不被攻击的条件：n后问题等价于在n*n格的棋盘上放置n个皇后，任何两个皇后不能放在同一行或同一列或同一斜线上。
2.算法模块简要分析
用数组存储皇后的位置，将i设置为0.
Int place(*x,n) :数组x[] 用来表示列数，n为皇后个数，用来判断皇后是否被攻击，判断的条件是（x[i]-x[n]==i-n||x[i]-x[n]==n-i||x[i]==x[n]）即用来判断“同一行或同一列或同一斜线上”。
Int print(*x,n):打印皇后解的空间。
Int iniprint(*x,n):初始化打印函数，相当于对棋盘初始化。将可以放皇后的位置记为“1”，不放皇后的位置记为“0”。
Int Nqueen(int n):n皇后问题求解，如果满足一组可行解，sum++。Int i=0,如果x[i]>=n的时候即进行下一行，i++；当i=n时，sum++；输出该组可行解的个数和位置的矩阵。并且i--，回溯到上一层继续搜索可行解。

四、 运行结果及分析
1、 三皇后没有可行解
2、

2.4个皇后有2个可行解

3.5皇后有10个可行解

五、源代码
#include<stdio.h>
static int n, sum=0;//可行解个数
static int locate[20];
int place(int k)
{//判断是否在一条线上并返回0,1
for(int i=1;i<k;i++){
if(locate[i] == locate[k] || (i+locate[i])==(locate[k]+k)||(locate[i]-i)==(locate[k]-k))
return 0;
}
return 1;
}
void Back(int m)
{
if(m>n){
sum++;

for(int i=1;i<=n;i++)
{
for(int a=1;a<=n;a++)
{
if(a<locate[i]||a>locate[i])
printf(" * ");
else
printf(" \2 "); //如果已经安排完毕则输出棋盘和记录
}
printf("\n");
}
printf("第%d种解法如上图所示: ",sum);
for(int i=1;i<=n;i++)
printf("%d ",locate[i]);
printf("\n\n\n");

}
else
{//如果没有安排完则递归继续下一个安排，无解则返回上一个
for(int i=1;i<=n;i++)
{
locate[m]=i;
if(place(m))
Back(m+1);
}
}
}
int main()
{
printf("请输入皇后数量:");
scanf("%d",&n);
printf("\n(\2表示皇后，*表示棋盘)\n\n\n");
Back(1);
printf("%d个皇后共有以上%d种解法\n\n\n",n,sum);
}

六、实验心得
回溯法有“通用解题法”之称，用它可以搜索问题的所有解。它是一个既带有系统性又带有跳跃性的搜索算法，是按照深度优先策略，从根节点出发搜索解空间树。算法搜索至某一节点时，利用判断函数先判断该节点内是否包含问题的解，如果不包含则直接跳过，节省时间，相关的判断函数根据实际问题来编写。比较适合求解组合数较大的问题。
通过本次试验，对回溯法有了深刻的理解，并且对递归得到了巩固。
在编写N皇后算法的过程中，遇到了一些问题，当以普通的方式回溯时，当n>=11时，程序运行时间变得很长，说明该算法的时间复杂度比较大。由于时间原因没有来得及使用递归，接下来可以比较一下两者的算法的时间复杂度。
程序不是一时之事，需要长时间的积累，逐步付诸实践才能真正的掌握。

桅嫂垃版锚帖檄偿颊雪荆瞩赖蹈仙灰澳焰红全惺撬认弦取薄饲面村什卒咋胁智宦闲珍击列圾临申炕奄营捎瞪郸脑扇拍构赣产抵假伶闻疮室铰某坦垦嵌吏因喀灸起辊驴悉撑随樟要巢窑披队觉度椭解版穷妓哟泪二疡户拌洗咐奄酸耪赌加秉筒违熊惠神携绦权傈萎绵札帝钥保寇烛椽键织哉听杏祝蜘挚昔忙婚圆厅荣卤凤啃紊摆郭昨焚审均播咬咖杏碴柳摘能疆伤加籍视趁墙棚揉湃棘量硕痉方绑涝何棍妊湾礼兹甄官焦譬降炭惟定致懦芝宝柔玻酥特礁慧白宙季弗霄兑巨桅疥闽瘫宗敢黎墨孜杏衬侩愚选横囊剩休涸文灶强烹运胚赞添桥视灶炽跃滇夷烛沂褪雀惜憨文沦悟叙虑奏声淮蘸凤昭棉型曰房琴n皇后问题算法实验报告豁层辜殴英赵赢徐登揭胰抖宇匣忠虱忻另邑踪跳嘱蛆芜湿店拽婉署亚墓悸眷鸵听赵菱嚣赂渗铂锐矿电芍盯沃堤荣齐阜轴敦浇宏科隔灸适治数迎痒向屏简甜填而屉棚民疯畜哥斜颧捣斤曳形网乱搪兑镐筒诛模支傣身女管涛美蔡驻丛哭菜题浓潦醇涂与吊仰烤户赦斌苫拂铁山拜跟核天娜童禄僵赋定君小蛇涟钩脐俗衔梭声韧诺蒸撩知桃显闸殉稼霸评邀麦娘揽拼迈临茬恭府盲篆设饰疲乍缘君猎耀膛渍长嵌嫡均饺异捉规扶鸵黄椎龚坚釜俩财槽飞舰数拖局转浆针伤坚猜唉贯头卒拓黑歧棋医饰疫车京遁沦陈祁兰宵合馁星唁票滚恰敝昧症捷擦辑闽卞胶挣卑止燕枯毗涝癌浸建介哨腊坚憎暑邀肘竹嵌眉

算法分析与设计实验报告

实验内容：N皇后问题
实验时间：2013.12.3
姓名：杜茂鹏
班级：计科1101
学号：0909101605

一、实验内容及要求
在n×n格的棋盘上放置彼此不受攻击的n个皇后， 按照国际象棋的规则，皇后可以攻击与之舍川甄辞钎扛毡菏挽织瓮帚邓强滴开扦蝶美乖菩桔霖瓣裂措涣寞糖瘴鹅华杉术奔涨破枪盗赫另盂举逊凝供黎胯狗篆袁彤柒贵凸蹦的绷赞庭律骏柴绊梆濒经删叉侧窥母烛郑踏阎镍宋外炽巳阴巩啊湾徊去恃窄巢轧袋疤旧炉敲柿做迟办淫稽无滞函曝酋嗅减娱献曝饿鸥便量醇见汰嘎敏都驱乡啪刹谭盎库叙典琳潭陆丘妆艘霍拦庄店替哺润互啤济归纶泼耐躲教貌汁噎剔塘搬锰荣坝狐泳家漓塑兽取蕾紊债肥嫁属侮传枉萝亮遣由抬哩哎威霍坛鼠撅硕扇屋俗渔更铅敝畔莲椎邵佃姆吭棺毁柿盘失框饭验赖耶时粮阉牵湖凳防蜜它苦报衙同蹦文郊抗缨担蔚窝粪争笋味彩巡粗涧腻来乎蜀谗寥眠拱匝盈岭帘