回溯法实验：八皇后问题求解及 C++ 代码实现

回溯法实验：八皇后问题求解及 C++ 代码实现

实验步骤:

1. 确定问题的解空间，定义问题的解的表示方式。
2. 确定约束条件和目标函数，设计判断函数。
3. 设计回溯函数，实现回溯算法。
4. 编写主函数，调用回溯函数并输出结果。

实验代码：

#include <iostream>
#include <vector>

using namespace std;

bool isValid(vector<int>& queens, int row, int col) {
    // 判断当前位置是否与之前的皇后位置冲突
    for (int i = 0; i < row; ++i) {
        if (queens[i] == col || queens[i] - col == i - row || queens[i] - col == row - i) {
            return false;
        }
    }
    return true;
}

void backtrack(vector<vector<string>>& res, vector<int>& queens, int n, int row) {
    if (row == n) {
        // 当找到一个合法解时，将结果存入res中
        vector<string> solution;
        for (int i = 0; i < n; ++i) {
            string s(n, '.');
            s[queens[i]] = 'Q';
            solution.push_back(s);
        }
        res.push_back(solution);
        return;
    }
    for (int col = 0; col < n; ++col) {
        if (isValid(queens, row, col)) {
            queens[row] = col;
            backtrack(res, queens, n, row + 1);
        }
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<int> queens(n);
    backtrack(res, queens, n, 0);
    return res;
}

int main() {
    int n = 8; // 八皇后问题
    vector<vector<string>> res = solveNQueens(n);
    for (int i = 0; i < res.size(); ++i) {
        cout << "Solution " << i + 1 << ":\n";
        for (int j = 0; j < n; ++j) {
            cout << res[i][j] << "\n";
        }
        cout << endl;
    }
    return 0;
}

实验总结：

通过本次实验，我们使用回溯法解决了八皇后问题。回溯法是一种递归的搜索算法，通过不断地尝试不同的解，当发现当前解不满足约束条件时，回溯到上一步重新选择其他解。通过递归的方式，我们可以穷举出所有可能的解，并找到满足条件的解。回溯法的关键是设计好判断函数，以及合理地剪枝，避免不必要的重复计算。在本次实验中，我们使用 isValid 函数判断当前皇后的位置是否与之前的皇后位置冲突，从而避免了重复计算。通过实验，我们成功地找到了八皇后问题的所有解。