位运算解决N皇后 详细图解

解决N皇后常用的方式是使用三个set来进行判重，分别存储列方向，撇方向和捺方向。每到新的一行，在准备放皇后的时候，就分别在三个集合中进行查找，若列的集合种没有出现当前列，则说明当前列是可以进行放置的，然后再分别看看，撇方向和捺方向的集合，若仍然没有出现与之对应的记录，则说明该位置可以放置皇后。然后继续进行DFS。而解决N皇后问题的最高级的做法便是使用位运算。

题目链接：

LeetCode-52. N皇后 II

位运算代码

class Solution1 {private int size;private int count;public int totalNQueens(int n) {count = 0;size = (1 << n) - 1;solve(0, 0, 0);//【1】return count;}private void solve(int row, int na, int pie) {if (row == size) {//【2】count++;return;}int pos = size & (~(row | na | pie));//【3】while (pos != 0) {//【4】int p = pos & (-pos);//【5】pos -= p; //【6】solve(row | p, (na | p) << 1, (pie | p) >> 1);//【7】}}}

逐句解释代码

以N=4为例：
【1】这句代码的作用是生成了n个二级制位1。对应于N皇后，表示当前列有n个空位可以放置皇后。row ，na ，pie中为1的二进制位具体对应棋盘中的位置，表示当前行对应的位置是不能放入皇后的。

size = (1 << n) - 1;//【1】

【2】递归中止条件，当row == size的时候，说明已经在每一行都顺利放入皇后了，结束递归，并进行记录。

if (row == size) {...}

【3】判断当前行能在哪个位置能插入皇后。pos对应的二级制位为1的地方则说明是可以放入皇后的，一旦该位置放入了皇后，则将其置为0。

int pos = size & (~(row | pie | na));

【4】判断当前层能否放入皇后，若pos=0，则说明pos的所有二进制位都为0，则说明当前层是无法放入皇后的。只有当pos不为0，才能进入while循环，从而递归到下一层。

 while (pos != 0){...}

【5】取出最最低位的1

int p = pos & (-pos)

pos & (-pos)：取最低位的1
-pos相当于是~pos + 1
【6】将当前层的对应位置0，表示在该位置已经放上了皇后

pos -= p; 

【7】准备进入下一层

solve(row | p, (na | p) << 1, (pie | p) >> 1)

图解运行过程

第一次执行到pos -= p的结果如下：

准备进入下一层：solve(row | p, (na | p) << 1, (pie | p) >> 1)

总结

N皇后这个问题很经典，对应了很多个解法，这个位运算的代码我也是看了好久才理解，这种时候，就能深刻体会自己是有多菜。

LeetCode上有的题目大神给出的代码只能用惊为天人来形容，而距离自己写出这样的代码，还差得很远。有时一个问题要想好久，即便是看别人的代码都要理解很久才明白。明白自己的不足，加油，拿下它便可。算法学习很枯燥，但是掌握了以后的确是一把利器，加油加油！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！