递归算法举例3.ppt

为了判断安全条件，在程序中要用到三个数组： （1）C[ j ] 为整型的，j = 1,2,…,8，初始化时全部 置为 1； （2）L[ k ] 为整型的，k = i - j +9, k = 2,3,…,16, 初始化时全部置为 1； （3）R[ m ] 为整型的, m = i + j, m = 2,3,…,16，初始化时全部置为 1； * 3、从思路上，在放第 i 个皇后时（当然在第 i行），选第 j 列，当 nq 为 1 时，就可将皇后放在 ( i, j ) 位置，这时做如下 3 件事 （1）放皇后q[ i ] = j，同时让第 j 列和过 ( i, j ) 位置的两条对角线变为不安全。即让 C[ j ] = 0; L[ i-j+9] = 0; R[ i+j ] = 0; 在放第 i 个皇后时（当然在第 i行），选第 j 列，当 nq 为 1 时，就可将皇后放在 ( i, j ) 位置，这时做如下 3 件事： （1）放皇后q[ i ] = j，同时让第 j 列和过 ( i, j )位置的两条对角线变为不安全。即让C[ j ] = 0; L[ i-j+9] = 0; R[ i+j ] = 0; （2）之后查一下 i 是否为 8，如果为8，则表明已经放完8个皇后，这时让方案数 Num 加 1，输出该方案下 8个皇后在棋盘上的位置。否则，未到 8个，还要让皇后数 i 加 1 再试着放，这时还要递归调用 Try( i+1 )。 （3）是为了寻找不同方案用的。当着一个方案输出之后，要回溯，将先前放的皇后从棋盘上拿起来，看看还有没有可能换一处放置。这时要将被拿起来的皇后的所在位置的第 j列，和两条对角线恢复为安全的。 * （2）之后查一下 i 是否为 8，如果为8，则表明已经放完8个皇后，这时让方案数 Num 加 1，输出该方案下 8个皇后在棋盘上的位置。否则，未到 8个，还要让皇后数 i 加 1 再试着放，这时还要递归调用 Try( i+1 )。 （3）是为了寻找不同方案用的。当着一个方案输出之后，要回溯，将先前放的皇后从棋盘上拿起来，看看还有没有可能换一处放置。这时要将被拿起来的皇后的所在位置的第 j列，和两条对角线恢复为安全的。我们用与或图来描述 8皇后问题的解题思路。 * A Try( i ) j = 1 2 . . . 8 Lp Lp 不安全 安全 什麽也不做 q[i]=j; c[j]=1; C[j]=0; R[i+j]=1; L[i-j+9]=0; i8 i==8 L[i-j+9]=1; R[i+j]=0; Try(i+1); Num++;输出 * // ******************************************* // * 程 序：6_9.cpp * // * 作 者：wuwh * // * 编制时间：2002年11月06日 * // * 主要功能：八皇后问题 * // ******************************************* #include stdio.h // 预编译命令 const int Normalize = 9; // 定义常量，用来统一数组下标 int Num; // 整型变量，记录方案数 int q[9]; // 记录8个皇