51. N 皇后

51. N 皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

思路

老早就接触这个问题了，看了好几次的位运算求解，思路理解了，老没认真实现过代码，今天碰见了，当是复习了。可以用三个整数来表示限制条件，分别是column，diag1，diag2，假定整数的二进制位为1的话，说明该位置可以放皇后。

column表示列限制，diag1表示左对角线，diag2表示右对角线，可以通过availablePosition = （2^n - 1) & (~(column | diag1 | diag2))来求解当前可以放皇后位置，然后通过不断将availablePosition的1置零来模拟放皇后操作，再递归到下一行，此时限制条件column容易求解，diag1需要左移一位，diag2需要右移一位，只要明白这个操作，题目就容易解了。

代码

class Solution { public: vector<vector<string>> solveNQueens(int n) { vector<vector<string>> solution; vector<int> queens(n, -1); dfs(solution, queens, n, 0, 0, 0, 0); return solution; } void dfs(vector<vector<string>>& solution, vector<int>& queens, int n, int row, int column, int diag1, int diag2) { if(row == n) { vector<string> tmp = toString(queens, n); solution.push_back(tmp); return; } else { //求解当前可放位置 int availablePositions = ((1 << n) - 1) & (~(column | diag1 | diag2)); //遍历可放位置 while(availablePositions != 0) { //取的最低位的1 int Position = availablePositions & (-availablePositions); //放上皇后置0 availablePositions = availablePositions & (availablePositions - 1); //求解Position的后面0的个数 int col = __builtin_ctz(Position); //设置皇后的位置i queens[row] = col; //递归下一行 dfs(solution, queens, n, row + 1, column | Position, (diag1 | Position) << 1, (diag2 | Position) >> 1); //回溯，取消放置皇后 queens[row] = -1; } } } vector<string> toString(vector<int>& queens, int n) { vector<string> ans; for(int i = 0; i < n; i++) { string tmp(n, '.'); tmp[queens[i]] = 'Q'; ans.push_back(tmp); } return ans; } };