N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example, There exist two distinct solutions to the 4-queens puzzle:

[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."],

["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;

        //record[i]表示第i行皇后放置的所在列数
        vector<int> record(n, 0);
        vector<string> sol(n, string(n, '.'));

        dfs(res, sol, 0, n, record);
        return res;
    }
private:
    void dfs(vector<vector<string>> &ret, vector<string> &sol, int i, int n, vector<int> &record){
        if(i == n){
            ret.push_back(sol);
            return;
        }

        for(int j = 0; j < n; j++){
            if(isValid(i, j, record)){
                sol[i][j] = 'Q';
                record[i] = j;
                dfs(ret, sol, i + 1, n, record);
                sol[i][j] = '.';
            }
        }
    }

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