八皇后问题 C++ 解法：枚举与递归

八皇后问题是经典的计算机科学问题，要求在 8x8 棋盘上放置 8 个皇后，使得她们不能互相攻击。按照国际象棋的规则，一个皇后可以吃掉与她处于同一行、同一列、同一对角线上的任何棋子，因此每一行只能摆放一个皇后。八皇后等价于要求在一个 8x8 格的棋盘上放置 8 个皇后，使得任何 2 个皇后不能放在同一行或同一列或同一对角线上。

例如，以下是一个八皇后问题的解：

(8,5,3,1,2,1)=769

图 1 解空间树中一条随机路径所对应的棋盘状态

输入数据

输出数据

算法分析

对于 n 后问题，皇后的位置用一个一维数组 x[1…n] 来存放，其中 x[i] 表示第 i 行皇后放在第 x[i] 列。下面主要来看看怎么样判断皇后是否安全的问题。

首先，用一维数组 x[1…n] 来表示，已经解决了不在同一行的问题；
对于列，当 j != k 时，要求 x[j] != x[k]；
对于左上右下的对角线的每个元素有相同的 '行 - 列' 值；对于左下右上的对角线有相同的 '行 + 列' 值。若两个皇后分别占有 (j，x[j]) 和 (k，x[k]) 两个位置，则她们在同一对角线上的条件是：

j - x[j] = k - x[k] 或 j + x[j] = k + x[k]

即

j - k = x[j] - x[k] 或 j - k = x[k] - x[j]

因此，同一对角线上的条件可归纳为 |j - k| = |x[k] - x[j]|。

C++ 代码实现

#include <iostream>
#include <cmath> // 用到绝对值函数

using namespace std;

bool check(int* x, int k) { // 判断第 k 个皇后是否安全
    for (int i = 1; i < k; i++) {
        if (x[i] == x[k] || abs(i - k) == abs(x[i] - x[k])) { // 同一列或同一对角线
            return false;
        }
    }
    return true;
}

void queen(int* x, int n, int& count) { // n 为皇后数量，count 为方案数的引用
    if (n == 0) { // 递归边界，找到了一组方案
        count++;
        return;
    }
    for (int i = 1; i <= 8; i++) { // 枚举第 n 个皇后的位置
        x[n] = i;
        if (check(x, n)) { // 若安全，则继续递归下一个皇后
            queen(x, n - 1, count);
        }
    }
}

int main() {
    int x[9] = {0}; // 用一维数组存放皇后位置，x[1]~x[8] 分别表示第 1~8 行的皇后位置
    int count = 0; // 方案数
    queen(x, 8, count);
    cout << count << endl;
    return 0;
}

代码解释

check(int* x, int k) 函数用于判断第 k 个皇后是否安全。它遍历之前放置的皇后，检查是否与当前皇后在同一行、同一列或同一对角线上。
queen(int* x, int n, int& count) 函数是递归函数，用于放置皇后。它从第 n 行开始，枚举当前行所有可能的皇后位置，并调用自身递归地放置下一个皇后。
main 函数调用 queen 函数，并将皇后数量和方案数传递给它。最后输出方案数。

总结

八皇后问题是典型的回溯算法问题，可以利用递归和枚举来解决。代码实现较为简单，但需要仔细理解算法思路。

参考资料