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

数据结构课程设计 选题： 八皇后问题 姓 名： 学 号： 指导老师： 目?? 录一.选题概述---------------------------------------3 设计要求与分析--------------------------------3 数据结构与定义--------------------------------4 1.结构体定义 2.函数定义 3.函数之间的定义 程序段与分析----------------------------------5 完整程序代码及运行结果截图------------------7 心得体会--------------------------------------10 参考文献--------------------------------------10 一．选题概述： 在实际应用中，有相当一类问题需要找出它的解集合，或者要求找出某些约束条件下的最优解。求解时经常使用一种称为回溯的方法来解决。所谓回溯就是走回头路，该方法是在一定的约束条件下试探地有哪些信誉好的足球投注网站前进，若前进中受阻，则回头另择通路继续有哪些信誉好的足球投注网站。为了能够沿着原路逆序回退，需用栈来保存曾经到达的每一个状态，栈顶的状态即为回退的第一站，因此回溯法均可利用栈来实现。而解决八皇后问题就是利用回溯法和栈来实现的。 二．设计要求与分析 八皇后问题是在8x8的国际象棋棋盘上，安放8个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一条对角线。 八皇后在棋盘上分布的各种可能的格局，其数目非常大，约等于232种，但是，可以将一些明显不满足问题要求的格局排除掉。由于任意两个皇后不能同行，即每一行只能放置一个皇后，因此将第i个皇后放置在第i行上。这样在放置第i个皇后时，只要考虑它与前i一1个皇后处于不同列和不同对角线位置上即可。因此，其算法基本思想如下： 从第1行起逐行放置皇后，每放置一个皇后均需要依次对第1，2，…，8列进行试探，并尽可能取小的列数。若当前试探的列位置是安全的，即不与已放置的其他皇后冲突，则将该行的列位置保存在栈中，然后继续在下一行上寻找安全位置；若当前试探的列位置不安全，则用下一列进行试探，当8列位置试探完毕都未找到安全位置时，就退栈回溯到上一行，修改栈顶保存的皇后位置，然后继续试探。 该算法抽象描述如下： （1)置当前行当前列均为1; （2）while(当前行号《8) （3）｛检查当前行，从当前列起逐列试探，寻找安全列号； （4）if（找到安全列号） （5）放置皇后，将列号记入栈中，并将下一行置成当前行，第1列置为当前列； （6）else （7）退栈回溯到上一行，移去该行已放置的皇后，以该皇后所在列的下一列作为 当前列； （8）｝结束程序。 数据结构与定义 结构体定义 typedef struct { int col[MaxSize]; //col[i]存放第i个皇后的列号 int top; //栈顶指针 }Type; 2.函数定义 bool place(Type st,int i,int j) //测试(i,j)是否与1~i-1皇后有冲突 void queen(int n) //求解皇后问题 void main() //主函数 函数之间的调用关系 main queen place 程序块与分析 bool place(Type st,int i,int j)//测试(i,j)是否与1~i-1皇后有冲突 { int k=1; if(i==1) return true;//存放第一个皇后时没有冲突 while(k=i-1)//j=1到k-1是已经放置了皇后的列 { if((st.col[k]==j)||(abs(j-st.col[k])==abs(k-i))) return false; k++; } return true; } （k，st.col[k]） （k，st.col[k]）