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.."]
]

 1 class Solution {
 2 public:
 3     vector<vector<string> > solveNQueens(int n) {
 4         vector<string> sol;
 5         vector<vector<string> > res;
 6         solveNQueensRe(n, 0, 0, 0, sol, res);
 7         return res;
 8     }
 9     // row bit: 指明前k行放在哪几列
10     // ld bit:  当前左边对角线限制（从前一行）
11     // rd bit:  当前右边对角线限制（从前一行）
12     void solveNQueensRe(int n, int row, int ld, int rd, vector<string> &sol, vector<vector<string> > &res)
13     {
14         if(row == (1 << n) - 1) {
15             res.push_back(sol);
16             return;
17         }
18         int valid = ~(row | ld | rd); //位非运算
19         for(int i = n - 1; i >= 0; i--) {
20             int pos = 1 << i;
21             if(valid & pos) {
22                 string s(n, '.');
23                 s[i] = 'Q';
24                 sol.push_back(s);
25                 solveNQueensRe(n, row | pos, (ld | pos) << 1, (rd | pos) >> 1, sol, res);
26                 sol.pop_back();
27             }
28         }
29         
30     }
31 };