51. N Queens - cocoder39/coco39_LC GitHub Wiki

51. N-Queens

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> solution(n, string(n, '.'));
        vector<int> placer(n, -1); //placer[i] = j iff placing queue at (i, j) 
        helper(res, solution, placer, 0);
        return res;
    }
private:    
    void helper(vector<vector<string>>& res, vector<string>& solution, vector<int>& placer, int row) {
        if (row == solution.size()) {
            res.push_back(solution);
            return;
        }
        
        for (int col = 0; col < solution.size(); col++) {
            if (isValid(solution, placer, row, col)) {
                placer[row] = col;
                solution[row][col] = 'Q';
                helper(res, solution, placer, row + 1);
                solution[row][col] = '.';
                placer[row] = -1;
            }
        }
    }
    
    bool isValid(vector<string>& solution, vector<int>& placer, int row, int col) {
        //check the column, 45 diagonals: if row - 1 then col + 1, 135 diagonals: if row - 1 then col - 1
        for (int i = 0; i < row; i++) {
            if (placer[i] == col || row - i == placer[i] - col || row - i == col - placer[i]) {
                return false;
            }
        }
        return true;
    }
};

In solution 1, placer records only for each row. An optimization is recording the column, 45 diagonals and 135 diagonals simultaneously using bit mask

bit mask of n queens

As situation shown above, we are processing row[3]. maskCol = 101010 indicates col[1], col[3], col[5] are available to place queen without conflicting columns. mask135 = 000111 indicates col[0], col[1], col[2] are available without conflicting 135 diagonals. mask45 = 100100 indicates col[1], col[2], col[4] and col5] are available without conflicting 45 diagonals. All together, mask = ~(maskCol | mask45 | mask135) = 010000 indicates only col[1] is available without any conflict.

hehe

after having placed queen on cur[3][1], attention how the bit masks are modified for row[4]. the new_maskCol = maskCol | mask. before placing cur[3][1], row[3]' mask45 = 100100. After placing, new_mask45 = mask45 | mask = 110100. In other word, the 45 diagonals impacts col[0]s, col[1], col[3] of row[3]. It would impact col[-1] (ignore), col[0], col[2] of row[4], generating row[4]' mask45 = 110100 << 1= 101000

tips:

  • int full1 = (1 << n) - 1 to get full1 whose lower n bits are all '1's
  • int positions = full1 & (~(maskCol | mask45 | mask135)) indicates available positions for placing queen.
  • int pos = positions & (~positions + 1) indicates one available position from position. pos is the right most '1' in position. To get all available positions one by one, we use positions -= pos to clear current available position.
  • get the column corresponding to the available position through
            int col = 0;
            int p = pos;
            while (! (p & 1)) { //get the col corresponding to pos
                p >>= 1;
                col++;
            }
  • bit mask transfer through maskCol | pos, (mask45 | pos) << 1, (mask135 | pos) >> 1. Although << 1 would exceed n-bit restriction, full1 can cancel the bad influence.
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        //the lower n bits of full1 are all '1's
        //int can hold at most 32 bits
        int full1 = (1 << n) - 1;   
        vector<vector<string>> res;
        vector<string> cur(n, string(n, '.'));
        helper(res, cur, 0, full1, 0, 0, 0);
        return res;
    }
private:    
    void helper(vector<vector<string>>& res, vector<string>& cur, int row, int full1, int maskCol, int mask45, int mask135) {
        if (row == cur.size()) { //all columns are occupied
            res.push_back(cur);
            return;
        }
        
        //a '0' in lower n bits of positions means there is an available position
        int positions = full1 & (~(maskCol | mask45 | mask135));
        while (positions) { 
            int pos = positions & (~positions + 1); //get the right most '1'. eg. 010110->000010
            positions -= pos; //clear the position corresponding to pos
            int col = 0;
            int p = pos;
            while (! (p & 1)) { //get the col corresponding to pos
                p >>= 1;
                col++;
            }
            cur[row][col] = 'Q';
            helper(res, cur, row + 1, full1, maskCol | pos, (mask45 | pos) << 1, (mask135 | pos) >> 1);
            cur[row][col] = '.';
        }
    }
};
⚠️ **GitHub.com Fallback** ⚠️