52. N皇后 II

  • N皇后
  • 位运算
  • DFS

看的网上别人的思路自己复现出来的结果。充分运用位运算和深度优先搜索。用位运算表示当前位置能否放置棋子的情况，0表示未放置棋子，1表示不能放置棋子。

比如一个8位的棋盘，未放置任何棋子时第一行为00000000，若第四个位置放置了棋子。则变为00010000。第二行可以放置棋子的情况变成00111000。这是由于第一行的第四个位置放置了棋子，因此这个棋子的左下角第二行第三位，正下方第二行第四位和右下角第二行第五位都无法放置棋子。顺延下去，左下角的左下角：第三行第二位；正下方的正下方：第三行第四位；因此思路中使用了三个变量，left表示左斜下方的不可放置位，right表示右斜下方的不可放置位，col表示垂直列的不可放置位。

按照上文的例子第一行为00010000。则第二行left为00100000由上一行左移一位得到，col为00010000，right为00001000由上一行右移一位得到，因此第二行的可放置位情况为(left | right | col)，即00111000。left，right如同水纹散开分别进行左移右移。与此同时第二行插入新的棋子，即表示当前产生了新的“水纹”。因此newleft = (left | colbit) << 1；newright = (right | colbit) >> 1;colbit表示插入的新的棋子位置。因此之后的“水纹”是新“水纹”和旧“水纹”的融合。列的情况比较简单。

使用深度优先搜索（dfs）进行整个运算过程。深度优先搜索的过程中，判断可插入位置是否还有空余位置可以插入，如果没能执行完最后一行就已经没有位置了，说明之前的插入方法不对。程序执行完自然返回并且无任何操作。如果已经执行完成了最后一行if(row >= n)，则最终的结果+1并且直接返回。

注意：移位运算符的优先级低于加减乘除，因此需要注意在需要的地方加上括号。

class Solution {

    int ans;

    public int totalNQueens(int n) {
        currentLine(0,0,0,0,n);
        return ans;
    }

    //left表示左斜已被插入位置，right表示右斜已被插入位置，col表示垂直已被插入位置。0表示未被插入，1表示已插入
    public void currentLine(int left,int right, int row, int col, int n){
        if(row >= n) {
            ans++;
            return;
        }

        //计算当前的可插入情况。1为可插入 0为不可插入
        int current = ~(left | right | col) & ((1<<n) -1);
        while(current > 0){
            int colbit = current & - current;
            int newleft = (left | colbit) << 1;
            int newright = (right | colbit) >> 1;
            int newcol = col | colbit;
            int newrow = row + 1;
            currentLine(newleft,newright,newrow,newcol,n);
        
            current = current & (current - 1);
        }
    }
}