八皇后问题全解.doc

计算机科学与技术专业 数据结构 课程设计报告设计题目：八皇后问题目 录 1需求分析 3 1.1功能分析 3 1.2设计平台 4 2概要设计 4 2.1算法描述 5 2.2算法思想 6 2.3数据类型的定义 6 3详细设计和实现 7 3.1算法流程图 7 3.2 主程序 7 3.3 回溯算法程序 8 4调试与操作说明 10 4.1调试情况 10 4.2操作说明 10 5设计总结 12 参 考 文 献 13 附录 13 1需求分析 1.1功能分析 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的,并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。现在我们已经知道八皇后问题有92个解答。 1、本演示程序中，利用选择进行。程序运行后，首先要求用户选择模式，然后进入模式。皇后个数设0n11。选择皇后个数后，进入子菜单，菜单中有两个模式可以选择。 2、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令：相应的输入数据和运算结果显示在其后。 3、程序执行的命令包括： 1）进入主菜单。 2）选择皇后问题，输入是几皇后。 3）进入子菜单。 4选择皇后显示模式。 5）选择结束 4、测试数据1）N的输入为4；2）共有2个解答。3）分别是 ○ ● ○ ○ ○ ○ ● ○ ○ ○ ○ ● ● ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ● ○ ○ ● ○ ○ ● ○ ○ 1.2设计平台 Windows2000以上操作系统；Microsoft Visual C++ 6.0 2概要设计问题：N后问题 问题描述： 国际象棋中皇后可以攻击所在行，列，斜线上的每一个位置，按照此规则要在一个n*n的棋盘上放n个皇后使每一个皇后都不互相攻击 问题分析： 引入1个数组模拟棋盘上皇后的位置 引入3个工作数组 行数组[k]1,表示第k行没有皇后 右高左低数组[k]1,表示第k条右高左低的斜线上没有皇后 左高右低数组[k]1,表示第k条左高右低的斜线上没有皇后 观察棋盘找到规律 同一右高左低的斜线上的方格，它们的行号和列号之和相等； 同一左高右低的斜线上的方格，它们的行号和列号只差相等； 开始时，所有行和斜线上都没有皇后，从第一列的第一行配置第一个皇后开始，在第m列的皇后位置数组[m]行放置了一个合理的皇后之后，准备考察第m+1列时，在数组行数组[]，右高左低数组[]，左高右低数组[]中为第m列，皇后位置数组[m]的位置设定有皇后标志 如果按此放置位置得不到结果，则把当前列中的有皇后标记改为无皇后标记。 依次类推 当在棋盘最后一列上也找到合适的位置后得到结果。 通过上面规律可以推导出结果。 2.1算法描述 回溯法——在约束条件下先序遍历，并在遍历过程中剪去那些不满足条件的分支。 使用回溯算法求解的问题特征，求解问题要分为若干步，且每一步都有几种可能的选择，而且往往在某个选择不成功时需要回头再试另外一种选择，如果到达求解目标则每一步的选择构成了问题的解，如果回头到第一步且没有新的选择则问题求解失败。 在回溯策略中，也可以通过引入一些与问题相关的信息来加快有哪些信誉好的足球投注网站解的速度。对于皇后问题来说，由于每一行、每一列和每一个对角线，都只能放一个皇后，当一个皇后放到棋盘上后，不管它放在棋盘的什么位置，它所影响的行和列方向上的棋盘位置是固定的，因此在行、列方面没有什么信息可以利用。但在不同的位置，在对角线方向所影响的棋盘位置数则是不同的。可以想象，如果把一个皇后放在棋盘的某个位置后，它所影响的棋盘位置数少，那么给以后放皇后留下的余地就太大，找到解的可能性也大；反之留有余地就小，找到解的可能性也小。 2.2算法思想 算法集中在如何解决棋子之间的冲突问题。 I.判断每个棋子是否满足规则的方法可以说是如出一辙。因此算法的整体思想是递规调用判断函数graph 。从i行开始安置各行元素,当iN时输出结果. II.具体的graph 函数的思想是: 先在第1行放上一个皇后，然后在第2行合适的位置放上一个皇后，依次类推，如果8行都放满了，说明找到了一个解，如果第好第i行的皇后后，第i+1行找不到合适的位置，这时就回到第i行，把第i行的皇后放到下一个位置，继续尝试下一行。如此反复，知道找到所有的解。注意，这种算法找的解