Leetcode 51

class Solution {
    vector<vector<string>> ans;
    vector<string> tmp;
    int N;
    char Q = 'Q';
public:
    bool check(int i, int j){
        for(int k = i - 1; k >= 0; k--){
            if(tmp[k][j] == Q) return false;
            if(j + (i - k) < N && tmp[k][j+i-k] == Q) return false;
            if(j - i + k >= 0 && tmp[k][j-i+k] == Q) return false;
        }
        return true;
    }

    void search(int remain){
        if(remain == 0){
            ans.push_back(tmp);
            return;
        }

        int line = N - remain;
        for(int i = 0; i < N; i++){
            if(check(line, i)){
                tmp[line][i] = Q;
                search(remain - 1);
                tmp[line][i] = '.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        if(n == 0) return ans;
        string s = "";
        for(int i = 0; i < n; i++){
            s += ".";
        }
        tmp.resize(n, s);
        N = n;
        search(n);
        return ans;
    }
};

这么经典的回溯题还困难？不会真的有人不会做吧？不会吧不会吧？

我们遍历每一行的每一个格点，并检查它是否合格。如果合格，那么就搜索下一行。

如果我们搜完了N行，证明方案合法， 加入答案中。

关于检查，我们可以只朝上检查，并且每一行都仅需要检查三个格子。这就不必向下或者遍历待检查某行了。