问题是8皇后问题有多少种解法(只需要一个总数, 不需要每一个具体的解决方案)

据说是目前效率最高的代码, 使用位运算操作.

#include<stdio.h>

int succ, ans;

void sol(int cp, int lp, int rp) {
    if (cp == succ) {
        ++ans;
        return;
    }
    int p = succ & (~(cp | lp | rp));
    while (p) {
        int bit = p & (-p);
        sol(cp | bit, (lp | bit) << 1, (rp | bit) >> 1);
        p &= (p - 1);
    }
}

int totalNQueens(int n){
    ans = 0;
    succ = (1 << n) - 1;
    sol(0, 0 ,0);
    return ans;
}

int main(){
    int ans;
    ans = totalNQueens(4);
    printf("%d\n", ans);
}

自己看了很久没看明白, 网上搜索了一下资料后才理解, 其实挺简单的. 不记得资料 URL 了, 也不去再找了, 默默致谢一下.

一步步来, 先不管上面的代码, 不管是不是使用位来操作, 先按一个简单的思路写下伪代码.

sol(depth, pos) { // depth 是当前要处理第几行, pos 是前面已经安放好的位置, 也就是上面 depth-1 行的数据

	 // 如果 N 排数据都已经安置好了, ans 加1
	if depth == N+1 {
		ans++
	}

	p = 根据 pos 计算当前行可以放的所有位置

	while ( p 中还有位置可以尝试 ) {
		next = 取当前行的下一个位置
		sol(depth+1, pos.update(next))
		update(p)
	}
}

我们如果想使用 BIT 记录数据(包括已经安放的位置, 以及当前行可以尝试的位置等等), 以及使用位运算加速, 需要考虑几个问题:

  1. 如何表示已经安放的位置
  2. 如何根据问题 1 计算出当前行可以安放的位置

直接看一下上面的代码是如何解决这些问题的.

它并没有直接使用一个变量记录”已经安放的位置”, 而是使用了三个变量间接实现的, 理解了这三个变量就理解这个代码了.

cp 用来记录”只考虑直上直下的冲突, 前面所有行安放的棋子会导致 depth 这一行哪些位置不能放”, 就是说, 第一行放左数第一个位置, 那么第二行就不能再放左数第一个位置了. 拿”八”皇后举例说明, 第一行棋子放在左数第三个位子, 那在计算第二行的位置时, cp = 0b00100000 . 继续在第二行的左数第一个位置放棋子, 计算第三行的位置时, cp = 0b00100000 0b10000000 = 0b10100000 . 很自然的, cp 的初始值应该是 0b00000000
lp 用来记录”右上-左下这条对角线上的冲突, 前面所有行安放的棋子会导致 depth 这一行哪些位置不能放”, 就是说, 第一行放左数第二个位置, 那么第二行就不能再放左数第一个位置了. 拿”八”皇后举例说明, 第一行棋子放在左数第三个位子, 那在计算第二行的位置时, lp = 0b00100000 0b01000000 = 0b01100000 .

rp 和 lp 类似, 只是记录 “左上-右下” 这条对角线.

搞清楚这三个变量, 再回头看一下问题1和2 . 问题1并不是一定要解决的, 因为”记录已经安放的位置”也只是为了解决问题2, 我们使用这三个变量有两个好处, 一是可以快速算出问题2, 二是可以使用位运算快速更新三个变量本身

然后, depth 这个变量并不是必需的, 可以使用 cp 取得一样的效果. cp 里面有多少个1, 就代表处理了几行了.