LeetCode做题笔记————52位运算优化N皇后

求解N皇后可行解个数的回溯优化

序章

对于N皇后问题，如果我把棋盘的一行视为二进制的一位，用1表示皇后，0表示空棋盘，岂不是可以用二进制来优化N皇后问题

来自于一个躺在床上做题上瘾的本科生。他并不知道之后这一反复在他脑海中出现，却又没能被他真正实现过的想法，在不远的将来会成为又一击溃他精神的小石子。

Part 1

确实可以，不如你尝试一下

一个声音出现在他的脑海中

我试过了，并不比传统DFS快很多，只不过是把存储棋盘的方式从二维数组变换为某个具体的数。我并没能发挥出二进制表示全部优势。

他丧气的说到，大概是打算就此放弃。

获取我们可以从最传统的方式一步一步开始。也许并不是你没能发掘出二进制的优势，而是从传统方法到二进制，之间包含着很多处优化，而你却想一步优化到最佳

声音突然变的非常温柔，他听到这段话的感觉，就好像被软绵绵的云朵包裹住。

也许你说的对吧，但我现在没心情思考这些

他仍然没办法打起精神，屏幕上显示着LeetCode52题的提交页面——这是一个他曾经都不愿意看一眼的网站，但如今他不得不完成上面发布的任务，以便能在夜之城这个资本至上的城市中找到一份还算不错的工作。更讽刺的是从他那漏音却没法修的荒板耳机中传出的武侍乐队的朋克小曲。嘈杂的失真吉他仿佛在嘲笑他糟糕的生活。而他好像并不在意，手里仍在摆弄着那张他和他那迷人的女朋友的照片。

也许我无论怎么做，都无法真正让她像喜欢她前任一样喜欢我，就像无论我怎么努力，无论刷题到几点，无论打多少比赛，做多少题目，都无法改变我起步太晚，不可能在这么短时间里达到那些区域金选手的程度这一事实。最后不得不承认自己在自己热爱的事情上做的也不够好，不得不承认自己无法让爱的人爱自己一样。

说到这他的眉头微微抽动，手中把玩的照片也随之停顿了1/50秒。事实上他也是最近才开始听朋克乐的，以前的他一直无法接受朋克的粗糙，无法认同朋克所歌颂的内核。但他无法否认的是，他的命运已经变得朋克。就像反资本的朋克最终却只能屈服于资本一样。不彻底的反抗，不坚定的叛逆，最终只会让这座完全成熟的夜之城将你视为小打小闹的未成年。

这一短暂的迟疑没能逃过那个声音的追捕：

也许你的生活还没有糟到无法改变的地步，就像传统方法也没有你认为的那么不堪的地步。如果我们找不到可以优化的地方，那我们就试着找找传统方法中值得保留的地方。也许当我们做完这一件小事之后，你能有所改观。

声音逐渐变得令人讨厌。他扎实的抓住了一个绝望者的软肋，向他抛去希望的镰刀，甚至教他如何使用。在经历过那么多的希望破面，期待落空后，不彻底的反抗者总会相信下一个会有所不同不是吗。

那就来试试看吧

他放下手中的相册，双手悬浮于屏幕之上，虚拟键盘以完全贴合齐五指自然排列的方式出现在他的指尖。电脑随机扫面了他的虹膜。脑后的插头上，代表硬盘IO的指示灯重新开始闪烁。

我们从哪开始？

既然要从传统方法上提取优点，那不如让我们先写一个最普通的N皇后解法吧，相信这个对你来说根本不算问题

....我不需要没有意义的恭维

这类人都这样，口嫌体正直。

Part 2 题目描述

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

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

给你一个整数 n ，返回 n 皇后问题 的不同解法的数量。

Sample

Input

Output

上述样例中，4皇后问题有以下两种解法，其中.表示空格，Q表示这一格上放着一枚皇后

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

Part 3 传统解法

传统解法直接使用DFS就好，由于皇后可以横向攻击的特性，那么每一行只能放置一个皇后，因此我们只需要决定每一行的那一个皇后在哪就好了。那DFS的每一层递归就用来表示一行好了。

那么对于这一行的皇后，我怎么知道这个皇后应该放在哪呢？显然我们需要根据之前放好的行的皇后来判断，即对于第$i$层的皇后，如果我们把他放在位置$j$，那么他需要满足以下条件：

$$
\begin{cases}
map[x][y] \neq Q & ( x < i, y = j) \\
map[x][y] \neq Q & (x < i, abs(x - y) = abs(i - j)) \notin R
\end{cases}
$$
对于每一层，我们通过试探的方法看该层的这一位置能否防止，可以放置则进入下一层；无法放置则试探下一个位置。如果该层所有位置均无法放置，则返回上一层，修改上一层放置的位置。

最终代码如下：

点击解锁

bool judge(int layer, int pos, vector<string> board, int n)
{
    for (int i = 0; i < board.size(); i++)
    {
        if (board[i][pos] == 'Q')
            return false;
    }
    for (int i = 1; i <= board.size(); i++)
    {
        int searchLayer = layer - i;
        int searchPos = pos + i;
        int searchPos2 = pos - i;
        // cout << "search: " << searchLayer << " " << searchPos << " " << searchPos2 << endl;
        if (searchLayer >= 0 && searchPos < n && board[searchLayer][searchPos] == 'Q')
            return false;
        if (searchLayer >= 0 && searchPos2 >= 0 && board[searchLayer][searchPos2] == 'Q')
            return false;
    }
    return true;
}

void dfs(vector<vector<string>> &ans, vector<string> boardNow, int layer, int n)
{
    if (layer == n)
    {
        ans.push_back(boardNow);
        return;
    }
    for (int i = 0; i < n; i++)
    {
        string layerNow(n, '.');
        if (judge(layer, i, boardNow, n))
        {
            layerNow[i] = 'Q';
            boardNow.push_back(layerNow);
            dfs(ans, boardNow, layer + 1, n);
            boardNow.pop_back();
        }
    }
}

int solveNQueens(int n)
{
    vector<vector<string>> result;
    vector<string> boardNow;
    dfs(result, boardNow, 0, n);
    return result.size();
}

Part 4 标记

可以肯定的是，传统方法中利用每一层只能放一个棋子的特点，避免了没必要的同层试探，并且递归的过程也写的很精简。但如果我说你这个算法很慢，你能告诉我大量的开销都花费到哪里去了吗

那个声音说到，似乎故意想把你的注意力吸引到dfs本身之外的地方。

嗯，当然可以，算法的时间开销很明显。由于试探冲突需要遍历所有已经放置的层，而冲突又大多发生在最底层，所以冲突的试探时间复杂度会达到O(n)，底层能放置的位置变少很可能需要遍历底层的每个位置，那么复杂度将会达到O(n^2)

他不甘挑衅，立马答到。

那如果使用试探每个位置的过程无法优化，我们能不能把判断是否冲突的时间复杂度降到O(1)呢

这样的话我需要记录那一条列、对角线、逆对角线上已经被放了皇后了。列好说，用一个数组标记列号即可，但主对角线和副对角线需要使用某种方式将其编号....

嘴上念叨着，他又开始上下移动手指，让计算机显示出一行行霓虹代码。

对于对角线来说，根据正方形的对称性，一个包含n行n列的矩阵一共有：
$$
2 \times n - 1
$$
这么多条对角线

那么对于主对角线，直接使用行和列的和就可以得到该位置所在的对角线的编号了。

而对于副对角线，使用同样的编码方式，但是我们认为编码应该是从左下角开始的，因此应取当前行号对于n的补数再与列号相加，即：
$$
n - 1 - row + col
$$
现在就可以很轻松的完成这一工作了：

点击解锁

bool visitCol[20]; // 记录已经使用过的列
bool visitPie[20]; // 记录已经使用过的主对角线
bool visitNa[20];  // 记录已经使用过的副对角线
void dfs(vector<vector<string>> &ans, vector<string> boardNow, int layer, int n)
{
    if (layer == n)
    {
        ans.push_back(boardNow);
        return;
    }
    for (int i = 0; i < n; i++)
    {
        int col = i;
        int mainCorner = layer * i;
        int subCorner = n - layer - 1 * i;
        if (visitCol[col] || visitPie[mainCorner] || visitPie[subCorner])
            continue;
        visitCol[col] = true;
        visitPie[mainCorner] = true;
        visitNa[subCorner] = true;
        string layerNow(n, '.');
        layerNow[i] = 'Q';
        boardNow.push_back(layerNow);
        dfs(ans, boardNow, layer + 1, n);
        boardNow.pop_back();
        visitCol[col] = false;
        visitPie[mainCorner] = false;
        visitNa[subCorner] = false;
    }
}

vector<vector<string>> solveNQueens(int n)
{
    vector<vector<string>> result;
    vector<string> boardNow;
    memset(visitCol, 0, sizeof(visitCol));
    memset(visitPie, 0, sizeof(visitPie));
    memset(visitNa, 0, sizeof(visitNa));
    dfs(result, boardNow, 0, n);
    return result;
}

Part 5 空间

很好，时间上这个算法已经可以用优秀来形容了，但真的足够完美吗？

声音仿佛带着一丝戏虐，仿佛他早已知道答案。

不用你提醒我。开三个bool数组太浪费空间了。

他仿佛被激怒了，已经很久没有这种渴望战胜某个人的感觉了。

对于每一个bool数组，变成语言会为其中的每一个数据分配至少1Byte的信息。但你我都知道，保存两个状态只需要一位就好了，也就是1bit。

因此完全可以使用一个整数来代替一个bool数组，标记时使用位运算即可。并且使用位运算进行查找比改变数组中的元素值快多了，这样一来就能接近完美了：

点击解锁

int col = 0; // 记录已经使用过的列
int pie = 0; // 记录已经使用过的主对角线
int na = 0;  // 记录已经使用过的副对角线
void dfs(vector<vector<string>> &ans, vector<string> boardNow, int layer, int n)
{
    if (layer == n)
    {
        ans.push_back(boardNow);
        return;
    }
    for (int i = 0; i < n; i++)
    {
        int mainCorner = layer * i;
        int subCorner = n - layer - 1 * i;
        if (((col >> i) | (pie >> mainCorner) | (na >> subCorner)) & 1)
            continue;
        string layerNow(n, '.');
        layerNow[i] = 'Q';
        boardNow.push_back(layerNow);
        col ^= (1 << i);
        pie ^= (1 << mainCorner);
        na ^= (1 << subCorner);
        dfs(ans, boardNow, layer + 1, n);
        boardNow.pop_back();
        col ^= (1 << i);
        pie ^= (1 << mainCorner);
        na ^= (1 << subCorner);
    }
}

vector<vector<string>> solveNQueens(int n)
{
    vector<vector<string>> result;
    vector<string> boardNow;
    dfs(result, boardNow, 0, n);
    return result;
}

这样就结束了吗？这么多移位操作，我看时间是应该是负优化

声音不再遮掩，直截了当的嘲讽起来。

.......

他没有说话，而是接着动起了手中的键盘，对这份代码继续进行着修改。

上面提到的三份代码实际上都没有解决一个根本性的问题：深层试探失败的次数很多这一问题。

既然我们可以通过位运算直接判断出当前位置是不是已经不可以放了。那能否直接获得可以放的位置呢？

位运算中有一种叫lowbit的操作，用于获取最低位1，并把其他位置0.

那么我将不可用位置取反，然后取lowbit即可得到一个可以使用的位置。

lowbit操作如下：

     a = 00110100
    ~a = 11001011
    -a = 11001100
a & -a = 00000100

那么代码就可以修改为如下形式：

对于col中，所有为1的位置表示不能放皇后。

对于pie中，对于当前行layer，经过该行的所有对角线的编号为[layer, n - 1 + layer]，为了和col的低n位对齐，我们将pie又移layer位，只有pie的低n位就也能表示能否放置了

对于na中，对于当前行layer，经过该行的所有对角线编号位$[n - 1 - layer, 2n - 2 - layer]$，因此我们对na进行类似的操作进行对其。

对pie和na进行对其时需要注意低n位左边的数据可能包含一些1，因此我们需要将其清0，只留下低n位的数据，因此需要与((1 << n) - 1)进行与操作。

点击解锁

int col = 0; // 记录已经使用过的列
int pie = 0; // 记录已经使用过的主对角线
int na = 0;  // 记录已经使用过的副对角线
void dfs(int &res, int layer, int n)
{
    if (layer == n)
    {
        res++;
        return;
    }
    int available = ((1 << n) - 1) & ~(col | (pie >> layer) | (na >> (n - 1 - layer)));
    while (available > 0)
    {
        int p = available & -available;
        available ^= p; // 选择这一位放置后续把这一位置0
        col ^= p;
        pie ^= (p << layer);
        na ^= (p << (n - 1 - layer));
        dfs(res, layer + 1, n);
        col ^= p;
        pie ^= (p << layer);
        na ^= (p << (n - 1 - layer));
    }
}
vector<vector<string>> solveNQueens(int n)
{
	int ans = 0;
    dfs(ans,0, n);
    return ans;
}

Part 6 完美

现在怎么样.....

他长舒了一口气，停下手指，看着眼前的一切。

太好了，已经接近完美了！过去的错误......我穿越那么多个时空，一次又一次的回到宇宙的各个时间点，终于完成了一项错误的纠正，事实证明，过去的错误时可以纠正的哈哈哈哈哈.....

.......你...到底是谁....

我是终将成为完美的人....

说罢，声音向他的脑机中发送了一段代码，变无迹可寻…

原来还可以在形式上达到完美.....

这段代码正如下面描述的，将col、pie、na作为参数放在函数中。

那么没进行一层，对这三个参数进行一次左移操作即可，并且这样免去了每次对这三个参数复原的操作。

神秘代码

void dfs(int &res, int layer, int n, int col, int ld, int rd)
{
    // cout << "Layer: " << layer << endl;
    if (layer == n)
    {
        res++;
        return;
    }
    // 左右移导致符号位发生改变，因此需要与全1进行与操作，保证有效位为低n位。
    int bits = ~(col | ld | rd) & ((1 << n) - 1);
    while (bits > 0)
    {
        int pick = bits & -bits; // 取最后一位1
        dfs(res, layer + 1, n, col | pick, (ld | pick) << 1, (rd | pick) >> 1);
        bits &= bits - 1; // 将最后一位1置0
    }
}
int totalNQueens(int n)
{
    int ans = 0;
    dfs(ans, 0, n, 0, 0, 0);
    return ans;
}