数据结构课程设计报告-8皇后问题

《数据结构课程设计报告-8皇后问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计选题：八皇后问题姓名：学号：指导老师：目  录一.选题概述---------------------------------------310二.设计要求与分析--------------------------------3三.数据结构与定义--------------------------------41.结构体定义2.函数定义3.函数之间的定义四.程序段与分析----------------------------------5五.完整程序代码及运行结果截图-----------------

2、-7六.心得体会--------------------------------------10七.参考文献--------------------------------------1010一．选题概述：在实际应用中，有相当一类问题需要找出它的解集合，或者要求找出某些约束条件下的最优解。求解时经常使用一种称为回溯的方法来解决。所谓回溯就是走回头路，该方法是在一定的约束条件下试探地搜索前进，若前进中受阻，则回头另择通路继续搜索。为了能够沿着原路逆序回退，需用栈来保存曾经到达的每一个状态，栈顶的状态即为回退的第一站，

3、因此回溯法均可利用栈来实现。而解决八皇后问题就是利用回溯法和栈来实现的。二．设计要求与分析八皇后问题是在8x8的国际象棋棋盘上，安放8个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一条对角线。八皇后在棋盘上分布的各种可能的格局，其数目非常大，约等于232种，但是，可以将一些明显不满足问题要求的格局排除掉。由于任意两个皇后不能同行，即每一行只能放置一个皇后，因此将第i个皇后放置在第i行上。这样在放置第i个皇后时，只要考虑它与前i一1个皇后处于不同列和不同

4、对角线位置上即可。因此，其算法基本思想如下：从第1行起逐行放置皇后，每放置一个皇后均需要依次对第1，2，…10，8列进行试探，并尽可能取小的列数。若当前试探的列位置是安全的，即不与已放置的其他皇后冲突，则将该行的列位置保存在栈中，然后继续在下一行上寻找安全位置；若当前试探的列位置不安全，则用下一列进行试探，当8列位置试探完毕都未找到安全位置时，就退栈回溯到上一行，修改栈顶保存的皇后位置，然后继续试探。该算法抽象描述如下：（1)置当前行当前列均为1;（2）while(当前行号《8)（3）｛检查当前行，从当前列起逐列试

5、探，寻找安全列号；（4）if（找到安全列号）（5）放置皇后，将列号记入栈中，并将下一行置成当前行，第1列置为当前列；（6）else（7）退栈回溯到上一行，移去该行已放置的皇后，以该皇后所在列的下一列作为当前列；（8）｝结束程序。三．数据结构与定义1.结构体定义typedefstruct{intcol[MaxSize];//col[i]存放第i个皇后的列号inttop;//栈顶指针}Type;102.函数定义boolplace(Typest,inti,intj)//测试(i,j)是否与1~i-1皇后有冲突voidqu

6、een(intn)//求解皇后问题voidmain()//主函数3.函数之间的调用关系mainqueenplace四．程序块与分析boolplace(Typest,inti,intj)//测试(i,j)是否与1~i-1皇后有冲突{intk=1;if(i==1)returntrue;//存放第一个皇后时没有冲突while(k<=i-1)//j=1到k-1是已经放置了皇后的列{if((st.col[k]==j)

7、

8、(abs(j-st.col[k])==abs(k-i)))returnfalse;k++;}returnt

9、rue;}（k，st.col[k]）（k，st.col[k]）j-st.col[k]j-st.col[k](i,j)i-ki-k(i,j)10//测试(i,j)位置是否与已经放好的第1个到第i~1皇后有冲突。已经放置好的第1个到第1~i-1个皇后已放置在st栈中。St栈用的是顺序栈，栈顶指针从1开始，st.col[k]用于存放第k（1<=i<=k-1）个皇后的列号，即皇后的位置是（k,st.col[k]）。对于（i，j）位置上的皇后与已经放置的皇后（k，st.col[k]）发生冲突的情况时，则有：st.col[k]

10、==j;对角线的冲突情况是：

11、j-st.col[k]

12、==

13、k-i

14、。voidqueen(intn)//求解n皇后问题{inti,j,k;boolfind;Typest;//定义栈stst.top=0;//初始化栈顶指针st.top++;//将(1,1)放进栈st.col[st.top]=1;while(st.top>0)//栈不空时循环{i=st.top;