DFS | 位运算 | 位运算优化N皇后问题

借 LeetCode 的每日一题 51. N 皇后 - 力扣（LeetCode）学了一下使用位运算优化 N 皇后问题的方法，不由得感叹位运算真是个神奇的东西，整理一下：

题目

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例1

text

1
2
3

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

提示：1 <= n <= 9

DFS + 位运算优化

首先基本的 DFS 解法就不多赘述了，容易发现：随着已经摆放的皇后数量增加，棋盘上剩余能摆放的位置会快速减少，这时如果不进行优化，普通 DFS 就会进行大量无意义的试探，浪费时间。

一个优化的出发点是，不去每个位置进行试探，而是在摆放了某个皇后之后就更新之后可以继续摆放皇后的位置（列，左右对角线），对这些位置继续试探，并动态更新，这样使得试探的次数大大减少，从而节约了时间

在这种优化思路之下，如何快速的进行动态更新，如何从当前状态中快速取得可以继续放置皇后的位置都是关键。考虑到题目的数据规模，用状压 DP 的思路，采用位运算正好可以完美满足这些需求。

DFS 优化

首先可以发现，合法状态的每行有且仅有一个皇后，因此 DFS 的对象可以简化为某行.

设二进制数第 $i$ ($i$ 从 0 开始) 位为 1 表示可以放置，为 0 表示不能放置，设置三个状态数：

$vis_C$：$n$ 位二进制，表示可以放置皇后的列编号
$vis_L$：$2n-1$ 位二进制，表示可以放置皇后的，左下至右上的斜线编号（简称为 $L$ 斜线）
$vis_R$：$2n-1$ 位二进制，表示可以放置皇后的，左上至右下的斜线编号（简称为 $R$ 斜线）

以 $vis_L$ 为例，起始位置在整个棋盘左上角，在 $4\times 4$ 的棋盘中，每个格子对应的斜线编号如下表

0	1	2	3
1	2	3	4
2	3	4	5
3	4	5	6

$vis_R$ 的起始位置在整个棋盘左下角

位运算优化

首先是几个常用的位运算操作：（$i$ 都从 0 开始编号）

a |= (1 << i) // 设置第 i 位为 1
a &= ~(1 << i) // 设置第 i 位为 0
a ^= (1 << i) // 取反第 i 位
(a >> i) & 1 // 取第 i 位的值
a = a & -a // lowbit 操作，除了最右边的 1 之外其余全部置为 0

由于按位运算的特性，对状态数进行位运算就是对整个状态集合进行位运算，与使用数组比起来是非常高效的

根据刚才的编号规则容易发现，第 $row$ 行第 $i$ 列格子所在的 $L$ 斜线编号为 $i+row$，所在的 $R$ 斜线编号为 $i+(n-row-1)$， $i$ 每增加 $1$，两种对角线的编号也增加 $1$

所以把状态数 $vis_L$，$vis_R$ 向右位移一些单位就可以对应上当前行的各个列，把列编号向左位移也可以对应斜线的编号，且由于按位与运算的性质，多出来的 1 和 0 不会影响运算结果

具体做法：

设 $row$ 为当前行编号，$bin(i)$ 为当前列编号 $i$ 表示的二进制数 $1\ll i$，都从 0 开始编号
设置第 $i$ 列不能放置皇后：$vis_C\; \&=\; rev(bin(i))$
设置第 $i$ 列所在的 $L$ 对角线不能放置皇后：$vis_L\; \&=\;rev(bin(i)\ll row)$
设置第 $i$ 列所在的 $R$ 对角线不能放置皇后：$vis_R\; \&=\;rev(bin(i)\ll (n-row-1))$
获取当前状态：$state = vis_C\; \&\; (vis_L\gg row) \;\&\; (vis_R\gg(n-row-1))$

此时对于 $state$，其第 $i$ 位为 1 就表示第 $i$ 列可以放置，否则就不能放置，使用 $lowbit$ 操作从低位往高位逐一读取 $state$，读取的结果就是每一个可以放置皇后的列编号 $x$ 对应的二进制数 $1\ll x$

位运算获取数 $x$ 二进制表示下最低位 1 的位置（从 0 开始）

经过上述运算，我们得到的 $x$ 是一个只有第 $i$ 位为 1，其他位均为 0 的数，表示第 $i$ 列可以放置皇后。要输出具体的解法，我们还需要从根据 $x$ 计算出 $i$

除了 $i=log_2{x}$，获取 $i$ 也可以用位运算实现。通过 $lowbit$ 运算我们获得了 $x’=2^i$，只需找到一种映射关系 $f$ 是 ${ x\;|\;x=2^i }$ 到 ${y\;|\;y=i}$ 的一个双射即可

这段代码来自 erl_mseg.c：

static const int debruijn[32] = {
	0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
	31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

#define LOW1BIT(X) (debruijn[((unsigned int)(((X) & -(X)) * 0x077CB531U)) >> 27])

代码中的 $0x077CB531U$ 不是唯一的，但是当它改变时数组内容也要随之改变

效果

位运算优化后的提升是非常显著的：

算法	时间	空间
普通DFS	136 ms	10.3 MB
普通DFS + 状态压缩	120 ms	10.5 MB
位移运算优化DFS	0 ms	7.7 MB

代码

char board[10][10];
int debruijn[32] = {0,  1,  28, 2,  29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4,  8,
                    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6,  11, 5,  10, 9};

#define low1bit(X) (debruijn[((unsigned int)(((X) & -(X)) * 0x077CB531U)) >> 27])

void dfs(int x, int vis_col, int vis_l, int vis_r, int n, vector<vector<string>>& res) {
#define lowbit(x) (x & -x)
    int pos = vis_col & (vis_l >> x) & (vis_r >> (n - x - 1));
    for (int i = lowbit(pos); i; pos ^= i, i = lowbit(pos)) {
        board[x][low1bit(i)] = 'Q';
        if (x == n - 1) {
            vector<string> v{};
            for (int i = 0; i < n; ++i) {
                v.push_back(string(board[i]));
            }
            res.push_back(v);
        } else {
            dfs(x + 1, vis_col & (~i), vis_l & (~(i << x)), vis_r & (~(i << (n - x - 1))), n, res);
        }
        board[x][low1bit(i)] = '.';
    }
}

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result{};
            for (int i = 0; i < n; ++i) {
                board[i][n] = '\0';
                for (int j = 0; j < n; ++j) {
                    board[i][j] = '.';
                }
            }
            dfs(0, (1 << n) - 1, (1 << ((n << 1) - 1)) - 1, (1 << ((n << 1) - 1)) - 1, n, result);
            return result;
        }
};