leetcode51：N皇后

题目链接

leetcode

题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

C++ 代码

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

/*
    回溯法

    由于每行只能有一个皇后，依次枚举每一行的皇后放到哪个位置，
    放置的过程中验证每一个位置是否合法。

    时间复杂度：O(n!)
        对于每个皇后，都有 n 种选择，总共有 n^n 种可能的排列。
        由于 n 个皇后不能在同行同列，所以每行恰有一个皇后。
        在不考虑对角线的情况下，计算方案数的上限。
        第一行有 n 个位置可选，第二行有 n−1 个位置可选，
        以此类推，方案数最多是 n!。
    空间复杂度：O(n)
        递归需要使用栈空间。
        在最坏的情况下，递归的深度可以达到 n，空间复杂度为 O(n)。
*/
class Solution_0 {
public:
    vector<vector<string>> solveNQueens(int n) {
        res.clear();
        n = _n;
        col = vector<bool>(n);
        dg = udg = vector<bool>(n*2);
        path = vector<string>(n, string(n, '.'));
        
        backtrack(0);

        return res;
    }

    void backtrack(int row) {
        // 结束条件
        if (row == path.size()) {
            res.push_back(path);
            return;
        }

        for (int col = 0; col < path.size(); col++) {
            // 剪枝条件：检查该位置是否可以放
            if (isValid(path, row, col)) {
                path[row][col] = 'Q'; // 做选择：放置皇后
                backtrack(row + 1);   // 下一行决策
                path[row][col] = '.'; // 撤销选择：回溯
            }
        }
    }

    bool isValid(vector<string> path, int row, int col) {
        // 检查列
        for (int i = 0; i < row; i++) {
            if (path[i][col] == 'Q') {
                return false;
            }
        }
        // 检查主对角线
        for (int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--) {
            if (path[i][j] == 'Q') {
                return false;
            }
        }
        // 检查副对角线
        for (int i = row-1, j = col+1; i >= 0 && j < path.size(); i--, j++) {
            if (path[i][j] == 'Q') {
                return false; 
            }
        }

        return true;
    }

private:
    vector<vector<string>> res;
    vector<string> path;
};

// 辅助函数：打印二维数组
void printArray(const vector<vector<string>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << "\"" << nums[i][j] << "\"";
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<int> n_cases = {
        4, 1
    };

    for (size_t i = 0; i < n_cases.size(); i++) {
        int n = n_cases[i];
        cout << "Input: n = " << n << endl;

        vector<vector<string>> result = solution.solveNQueens(n);
        cout << "Output: ";
        printArray(result);
    }

    return 0;
}