1、一、实验名称：n 皇后问题 二、实验目的及要求8 皇后问题是一个广为人知的问题：将 8 个皇后放在 88 的棋盘上，皇后之间不能互相攻击，求各种放法。更一般的，把 8 换成 n，其解法个数是随 n 成几何级增长的，因此程序运行时间也是几何级别的。现在我们关注这样一个问题，既然不能很快的把所有解都枚举出来，那么我们能不能很快的求出一个解来呢？这就是 n 皇后问题。有人说，我就用纯搜索来搜第一个解，会不会快呢？你可以试一试，当 n 增大的时候会变的非常非常慢。除了搜索，还能有什么更好的办法呢？下面介绍一个 QS2 算法，可以在当 n 大到 500000 的时候仍能在几分钟之内得到解。三、实验环境C
2、+四、实验内容在一个 N*N 的棋盘上放置 N 个皇后，且使得每两个之间不能互相攻击，也就是使得每两个不在同一行，同一列和同一斜角线上。对于 N1，问题的解很简单，而且我们很容易看出对于 N2 和N 3 来说，这个问题是无解的。所让我们考虑 4 皇后问题并用回溯法对它求解。因为每个皇后都必须分别占据行，我们需要做的不过是为图 1 棋盘上的每个皇后分配一列。我们从空棋盘开始，然后把皇后 1 放到它所在行的第一个可能位置上，也就是第一行第列。对于皇后 2，在经过第一列和第二列的失败尝试之后，我们把它放在第一个可能的位置，就是格子2，3),位于第二行第二列的格子。这被证明是一个死胡同,因为皇后：将没
3、有位置可放。所以，该算法进行回溯，把皇后 2 放在下一个可能位置(2 ，4)上。然后皇后 3 就可以放在 (3，2)，这被证明是另一个死胡同。该算法然后就回溯到底，把皇后 1 移到(1 ，2)。接着皇后 2 到(2 ，4)，皇后3 到(3，1)，而皇后 4 到(4，3) ，这就是该问题的一个解。图 2 给出了这个查找的状态空间树。五、算法描述及实验步骤void Queen(int n); /* n 皇后问题 */void TrySolution(int i,int n,int a, int b,int c, int x); /* 回溯求解 n 皇后问题 */void OutSolution(i
4、nt n,int x);/* 输出一组解 */int main(void) /* 主函数 main(void) */int n = 4;Queen(n); /* 求解 4 皇后问题 */system(“PAUSE“); /* 调用库函数 system() */return 0; /* 返回值 0 */ /* n 皇后问题 */void Queen(int n)int aN + 1, b2 * N + 1, c2 * N + 1; /* a:某一列，b:副对角线， c:主对角线 */int i, xN + 1; /* x:皇后所放置的列 */* 赋初值 */for (i =1 ; i n) /*
5、 /in 表示第 1n 个皇后已放置好 */ OutSolution(n, x); /* 已得到解,输出解 */elsefor (j = 1; j /* 文件包含预处理命令，printf( )函数在其中声明 */#include /* 文件包含预处理命令，system( )函数在其中声明 */#define N 80 /* 皇后最多个数 */#define FALSE 0#define TRUE 1void Queen(int n); /* n 皇后问题 */void TrySolution(int i,int n,int a, int b,int c, int x); /* 回溯求解 n 皇后问题 */void OutSolution(int n,int x);/* 输出一组解 */int main(void) /* 主函数 main(void) */int n = 4;Queen(n); /* 求解 4 皇后问题 */system(“PAUSE“); /* 调用库函数 system() */return 0; /* 返回值 0 */ /* n 皇后问题 */void Queen(int n)int aN + 1, b2 * N + 1, c2 * N + 1; /* a:某一列，b:副对角线， c:主对角线 */int i, xN + 1; /* x:皇后所放置的列 */
