位运算与经典八皇后问题( 三 ) _位运算

文章插图

如图示,第二行放皇后的位置只能从第三个格子开始选
第二行我们选第三个格子放皇后，选完开始在第三行选，第三方可选的位置也受到了第一，二行皇后所放位置的影响

文章插图

如图示，第三行只能从第五个格子开始放置皇后
同理，第三，四，五行都从左到右选择符合条件的的格子放置皇后，选完后问题来了，第六行所在行没有可选的位置了！如图示

文章插图

怎么办呢，回溯！重新摆放第五行的皇后，将其放到第八格上

文章插图

重新摆放后发现第六行还是没有符合条件的格子，咋办，我们知道第六行可摆放皇后的格子受第五行影响，而第五行受第四行摆放皇后位置的影响的，所以回溯到第四行，将皇后位置摆放到当前行的其他位置（第七格），再接着往下放 5，6，7，8 行的皇后。。。，只要不满足条件，改变上一层的的条件重新来，上一层调整后还是不符合条件，再调整上上层的。。。，调整完后重新往下递归选择，直到找到符合条件的，找到之后再在第一层换一个位置选皇后递归往下层选择执行，直到找到所有的解，这种不满足条件就回退上层调整再试的思想就是回溯法，可以看到回溯法一般是用递归实现的。
回溯算法有不少变种，这里我们重点介绍使用位运算的回溯算法，它是所有解法中最高效的！如果在面试中能使用位运算来解回溯算法，绝对会让面试官给你个大大的赞！
接下来是重点了，怎么用位运算来求解。
在以上回溯法的分析中，我们不难发现，在八皇后问题中，问题的关键是找出行可放皇后的格子。找到之后问题就解决了 90%，所以接下来我们就来看看怎么找这些可用的格子。
假设我们要求解第三行可放皇后的格子（说明一二行的皇后已放好了）那么第三行可放皇后的位置受到哪些条件的限制呢。显然在第一二行已放皇后的格子所在的列，左斜线，右斜线对应的方格都不能放皇后，如图示:

文章插图

我们以 column 来记录所有上方行已放置的皇后导致当前行格子不可用的集合，所在列如果放了皇后，则当前行格子对应的位置为 1，否则为 0，同理,以 pie（撇，左斜线）记录所有已放置的皇后左斜方向导致当前行格子不可用的集合，na（捺，右斜线）表示所有已放置的皇后右斜方向导致当前行不可用的集合。则对于第三行来说我们有：

column = 10010000 (上图中的第一个图，第 1，4 列放了皇后，所以 1，4 位置为 1，其他位置为 0）
pie = 00100000 (上图中的第二个图，左斜线经过第三行的第三个方格，所以第三位为 1）
na = 00101000 (上图中的第三个图，右斜线经过第三行的第三, 五个方格，所以第三,五位为 1）

将这三个变量作或运算得到结果如下

10010000
| 00100000
| 00101000
-----------------------
10111000

也就是说对于第三层来说第 1，3，4，5 个格子不能放皇后。如图示

文章插图

于是可知 column | pie | na 得到的结果中值为 0 的代表当前行对应的格子可放皇后，1 代表不能放，但我们想改成 1 代表格子可放皇后，0 代表不可放皇后，毕竟这样更符合我们的思维方式，怎么办，取反不就行了，于是我们有~(column| pie | na) 。
问题来了，这样取反是有问题的，因为这三个变量都是定义的 int 型，为 32 位，取反之后高位的 0 全部变成了 1，而我们只想保留低 8 位（因为是 8 皇后），想把高位都置为 0，怎么办，这里就要用到位运算的黑科技了

~(column | pie | na) & ((1 << 8)-1)

后面的的 ((1<< 8) -1) 表示先把 1 往左移 8 位，值为 100000000,再减 1 ，则低 8 位全部为 1，高位全部为 0！（即 0011111111）再作与运算，即可保留低 8 位，去除高位。
费了这么大的劲，我们终于把当前行可放皇后的格子都找出来了（所有位值为 1 的格子可放置皇后）。接下来我们只要做个循环，遍历所有位为 1 的格子，每次取出可用格子放上皇后，再找下一层可放置皇后的格子，依此递归下去即可,直到所有行都遍历完毕（递归的终止条件）。