实验报告 ——八皇后问题求解（递归和非递归） 学号： 专业年级： 姓名： 一 、 需 求 分 析 （ 要 实 现 的 功 能 描 述 ） 1．问题描述 八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n 皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1 或n ≥ 4 时问题有解。八皇后问题最早是由国际囯际象棋棋手马克斯·贝瑟尔于1848 年提出。诺克也是首先将问题推广到更一般的n 皇后摆放问题的人之一。 2．实现功能 八皇后问题实现了在棋盘上摆放八个皇后的功能，这八个皇后任意两个皇后都不能处于同一条横行、纵行或斜线上。 3．测试数据 测试数据可以通过手工寻找三组满足需要的值，测试数组（M，N），其中M 代表皇后所在的行，N 代表皇后所在的列。例如，第一组测试数据： （1，4）、（2，7）、（3，3）、（4、8）、（5，2）、（6，5）、（7，1）、（8，6）；第二组测试数据（1，5）、（2，2）、（3，4）、（4，7）、（5，3）、（6，8）、（7，6）、（8，1）；第三组测试数据： （1，4）、（2，2）、（3，7）、（4，3）、（5，6）、（6，8）、（7，5）、（8，1）。最后与编程求得的结果进行比较。如果这三组数据在最后编程求得的结果中，说明程序的编写基本没有什么问题。 二 、 概 要 设 计 在进行概要设计的过程中，要清楚整个程序包含的功能模块及模块间的调用关系。 对于八皇后问题，整个程序中应该包括主函数模块，摆放皇后的函数模块，以及判断皇后的位置是否摆放正确的判断模块。对于模块间的关系，在运行主函数的过程中会调用摆放皇后的函数模块，在摆放皇后的函数模块中，又会调用判断皇后位置是否摆放正确的判断模块。 三 、 详 细 设 计 抽象数据类型中定义的各种操作算法实现（用 N-S图描述） 对于求解八皇后问题的非递归算法，N-S图如下： 运行queens 函数 定义 8 个皇后，并且开辟 9 个空间（a[0]不用）初始化为 0，初始化 k 为第一列,即 k=1； 当 k>0 时候 在a[k]的位置上摆放一个皇后，即皇后的位置用数组表示为（a[k],k） 当摆放皇后没有到列的最底部，并且摆放不冲突的时候 将皇后下移一位 皇后位置到达底部？ 是 否 回溯到 k-1 步 八列皇...
