示例：

 輸入：4
 輸出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 解釋: 4 皇后問題存在如下兩個不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

分析

N皇后是經典的回溯問題，就是每一步都嘗試，每一步都看當前位置是否符合規則，下面我們直接看代碼吧。

代碼

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        used.resize(n, vector<bool>(n, false));
        backtrace(used, 0);
        return ret;
    }

    vector<vector<bool>> used;
    vector<vector<string>> ret;

    void backtrace(vector<vector<bool>> &used, int row) {
        if (row == used.size()) {
            PushString(used);
            return;
        }
        int col = used[0].size();
        for (int i = 0; i < col; ++i) {
            if (IsValid(used, row, i)) {
                used[row][i] = true;
                backtrace(used, row + 1);
                used[row][i] = false;
            }
        }
    }

    void PushString(vector<vector<bool>> &used) {
        vector<string> vec;
        for (auto &v : used) {
            string tem;
            tem.resize(v.size(), '.');
            for (int i = 0; i < v.size(); ++i) {
                if (v[i]) tem[i] = 'Q';
            }
            vec.push_back(tem);
        }
        ret.push_back(vec);
    }

    bool IsValid(vector<vector<bool>> &used, int i, int j) {
        int row = used.size();
        int col = used[0].size();
        for (int ii = 0; ii < i; ++ii) {
            if (used[ii][j]) return false;
        }
        for (int jj = 0; jj < j; ++jj) {
            if (used[i][jj]) return false;
        }
        for (int ii = i - 1, jj = j - 1; ii >= 0 && jj >= 0; ii--, jj--) {
            if (used[ii][jj]) return false;
        }
        for (int ii = i - 1, jj = j + 1; ii >= 0 && jj < col; ii--, jj++) {
            if (used[ii][jj]) return false;
        }
        return true;
    }

};

  代碼精進之路，我們一起成長！

C++數組長度可以為變量嗎？

C++中glog源碼剖析以及如何設計一個高效log模塊

想看懂stl代碼，先搞定type_traits是關鍵

C++線程池的實現