八皇后问题 C++ 解法：深度优先搜索算法实现

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

深度优先搜索算法

深度优先搜索 (DFS) 是一种常用的图遍历算法，可以用于解决许多问题，包括八皇后问题。在八皇后问题中，我们可以使用 DFS 来枚举所有可能的皇后放置方案，并检查每个方案是否合法。

C++ 代码实现

#include <iostream>
#include <cmath>
using namespace std;

int n; // 皇后数量
int cnt; // 解的数量
int x[100]; // 存放每一行皇后所在的列数

bool check(int k) { // 检查第k行皇后是否合法
    for (int i = 1; i < k; i++) {
        if (x[i] == x[k] || abs(x[i] - x[k]) == abs(i - k)) {
            return false; // 不合法
        }
    }
    return true; // 合法
}

void dfs(int k) { // 在第k行放置皇后
    if (k == n + 1) { // 找到了一组解
        cnt++;
        return;
    }
    for (int i = 1; i <= n; i++) {
        x[k] = i; // 第k行皇后放在第i列
        if (check(k)) { // 检查是否合法
            dfs(k + 1); // 继续搜索下一行
        }
    }
}

int main() {
    cin >> n;
    dfs(1); // 从第1行开始搜索
    cout << cnt << endl; // 输出解的数量
    return 0;
}

代码解释

1. check(int k) 函数: 用于检查第 k 行皇后是否合法。它遍历前 k-1 行的皇后，判断当前皇后是否与它们在同一行、同一列或同一对角线上。
2. dfs(int k) 函数: 用于在第 k 行放置皇后。它枚举第 k 行的每个列，如果当前位置合法，则递归调用 dfs(k+1) 函数在下一行放置皇后。
3. main() 函数: 获取输入的皇后数量 n，然后调用 dfs(1) 函数从第一行开始搜索解。最后输出解的数量 cnt。

总结

本文使用 C++ 语言实现了深度优先搜索算法来解决八皇后问题。代码简洁易懂，并且包含了详细的解释。希望本文能够帮助你更好地理解八皇后问题和深度优先搜索算法。