关于c语言编程中八皇后问题的设计报告

《关于c语言编程中八皇后问题的设计报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、关于c语言编程中八皇后问题的设计报告一、课题的来源及意义八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计

2、算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。二、面对的问题1）解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；2）使用数据结构的知识，用递归法解决问题。三、需求分析1、涉及到的知识本次设计中，用到的主要知识有：递归法的运用，for语句的灵

3、活运用，数据结构中树知识的灵活运用、栈及数组的掌握。2、软硬件的需求1)系统要求：winxp以上操作系统；2)语言平台：tc++或vc++6.0；3、功能需求当运行程序时，在屏幕上显示每一种方法八个皇后的相对位置，要用比较直观的界面显示。四、概要设计我的思想是用循环递归循环来实现的，分别一一测试了每一种摆法，并把它拥有的92种变化表现出来。在这个程序中，我的主要思路以及思想是这样的：1）解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个皇后占领

4、后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。2）数据结构的实现而对于数据结构的实现，学生则是着重于:数组a[I]：a[I]表示第I个皇后放置的列；I的范围：1..8;对角线数组：b[j](主对角线),c[j]（从对角线），

5、根据程序的运行，去决定主从对角线是否放入皇后；五、详细设计和实现1、算法描述A、数据初始化。B、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置（n，m）是否等于0（未被占领）。如果是，摆放第n个皇后，并宣布占领（记得姚横列竖列斜列一起设置），接着进行递归；如果不是，测试下一个位置（n，m+1），但是如果当n<=8，m=8时，发现此时已无法摆放时，便要进行回溯。从问题的某一种可能出发，搜索从这种情况能出发，继续搜索，这种不断“回溯”的寻找解的方法，称为“回溯法”。C、使

6、用数组实现回溯法的思想。D、当n>8时，便打印出结果。E、输出函数我使用printf输出，运行形式为：第m种方法为：********2、算法流程图六、代码编写及详细注释#include#include#include#include#include#defineQUEENS8intiCount=0;//!记录解的序号的全局变量。intSite[QUEENS];//!记录皇后在各行上的放置位置的全局数组。void

7、Queen(intn);//!递归求解的函数。voidOutput();//!输出一个解。intIsValid(intn);//!判断第n个皇后放上去之后，是否有〉冲突。voidmain()/*----------------------------Main：主函数。----------------------------*/{system("title叶青--递归算法八皇后问题");cout<<""<<"八皇后的解法："<

8、-------------"<