51. N-Queens

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

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

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

class Solution {
    vector<vector<string>> res;
    int queen = 0;
    bool isPossible(vector<string>& b, int y, int x, int n) {
        int bx = x, ax = x;
        while(y--) {
            bx--, ax++;
            if(bx >= 0 && b[y][bx] == 'Q') return false;
            if(ax < n && b[y][ax] == 'Q') return false;
        }
        return true;
    }
    void dfs(int cur, int n, vector<string>& b) {
        if(cur == n) {
            res.push_back(b);
            return;
        }
        for(int i = 0; i < n; i++) {
            if((queen & (1<<i)) || !isPossible(b, cur, i, n)) continue;
            queen ^= (1<<i);
            b[cur][i] = 'Q';
            dfs(cur + 1, n, b);
            b[cur][i] = '.';
            queen ^= (1<<i);
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        dfs(0, n, board);
        return res;
    }
};