N-Queens I & II (Leetcode 51, 52

著名的“N皇后”问题。主要思路是：我们逐行进行DFS，而在每一行的DFS中逐列扫描，放置皇后。

N Queens I: https://leetcode.com/problems/n-queens/description/
N Queens II: https://leetcode.com/problems/n-queens-ii/description/

而判断皇后位置是否合适，则需要一个prevoius position函数。previous[i] = c, means one Queen is on row i, col c。
由于我们逐行DFS，则保证了行不一样。列，和对角线的check利用如下函数，需要遍历所有之前放置的位置。其中对角线的check非常巧妙。

 bool isValid(int row, int col, vector<int> &pos){
        for(int i=0; i<pos.size(); i++){
            if(col == pos[i] || (abs(i-row) == abs(pos[i] - col))) return false;
        }
        return true;
    }

N-Queens I:

class Solution {
public:
    
    bool isValid(int row, int col_idx, vector<int> &record){
        for(int i=0; i<record.size(); i++){
            if(record[i] == col_idx || row - i == abs(col_idx - record[i])) return false;
        }
        return true;
    }
    
    void findcombo(vector<vector<string>> &allcomb, vector<int> &record, int row, int n){
        if(row == n){
            vector<string> comb;
            for(int i=0; i<record.size(); i++){
                int idx = record[i];
                string temp = string(n, '.');
                temp[idx] = 'Q';
                comb.push_back(temp);
            }
            allcomb.push_back(comb);
            return;
        }
        for(int i=0; i<n; i++){
            if(!isValid(row, i, record)) continue;
            record.push_back(i);
            findcombo(allcomb, record, row+1, n);
            record.pop_back();
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> allcomb;
        if(n <= 0) return allcomb;
        vector<int> record;
        findcombo(allcomb, record, 0, n);
        return allcomb;
    }
};

II 和 I 的做法基本一样，也是用DFS来做。用一个cnt变量，来记录满足条件个数。

class Solution {
public:
    int totalNQueens(int n) {
        if(n <= 0) return 0;
        int cnt = 0;
        vector<int> pos;
        findcombo(cnt, pos, 0, n);
        return cnt;
    }
    
    void findcombo(int &cnt, vector<int> &pos, int cur, int n){
        if(cur == n){
            cnt++;
        }
        for(int i=0; i<n; i++){
            if(isValid(cur, i, pos)){
                pos.push_back(i);
                findcombo(cnt, pos, cur+1, n);
                pos.pop_back();
            }
        }
    }
    
    bool isValid(int row, int col, vector<int> &pos){
        for(int i=0; i<pos.size(); i++){
            if(col == pos[i] || (abs(row-i) == abs(col-pos[i]))) return false;
        }
        return true;
    }
};