n皇后问题

n皇后是一个经典的递归回溯问题，以八皇后问题为例提供三种解法：递归、非递归、位运算。
优秀博客链接1：https://www.jianshu.com/p/d16707207de8
优秀博客链接2：https://blog.csdn.net/xiexinxinlove/article/details/38797227

问题描述
八皇后问题是在一个 88 的棋盘上放置皇后，要求其放置后满足*同一行，同一列，同一斜线上**没有重复的皇后出现。
试问有多少种摆盘方式？

递归回溯

算法思想
递归的思路很清晰：

  1. 就是对每一行的8列逐个进行判断，如果可以放置就进行下一行的尝试；
  2. 如果一行都不能放置，则退回上一行（回溯），那么就会回到上一行继续检索剩余列

**注：很容易想到需要一个88的矩阵来存放皇后，这里可以优化一下

  • 因为对于每一个可行解，同一行仅一个皇后存放
  • 所以用n元组x[1:n]表示n后问题的解，x[i]表示皇后i放在第i行的第x[i]列
  • 由于任意两个皇后不在同一列，所以解向量x[i]互不相同

————————————————————————————————————
Dfs()递归，Judge()判断可行解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int a[10];
int sum;
int n;
void Dfs(int step){ //n=8,这里开始step=1，递归到step=9结束
	if(step>n){
		sum++;
		return;
	}
	for(int i = 1; i <= n; ++i){
		a[step] = i;
		if(Judge(step))
			Dfs(step+1);
	}
}

关键是Judge()判断可行解了，若两个皇后的位置分别是(i,j)和(k,l)

  • 同行不重复：x[i]表示的就是不同行的
  • 同列不重复：x[i]&&x[k]
  • 同对角线不重复：
    • 若2个皇后处于同一斜线,则 k-i = l-j (斜率为1的斜线)或 k-i = j-l(斜率为-1的斜线)
    • 即 abs(i-k)$$abs(x[i]-x[k])
      ——————————————————————————————————————————————
      1
      2
      3
      4
      5
      6
      7
      bool Judge(int k){  //判断第k行的x[k]是否可行
      	for(int i = 1; i < k; ++i){ //遍历1~k行的皇后
      		if((abs(k-i)==abs(a[k]-a[i]) || a[k]==a[i]))
      			return false;
      	}
      	return true;
      }

迭代回溯

迭代回溯就是递归转非递归，Judge()不用改，Dfs()改成solve()；
关于转换，属于不看答案可能这辈子都想不到系列；
只能说多磨练多思考吧。
——————————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve(){
	a[1] = 0;
	int k = 1;
	while(k > 0){
		a[k] += 1;
		while((a[k] <= n) && (!Judge(k))){  //退出的标志：找到该行可以放置的皇后
			a[k] += 1;
		}
		if(a[k] <= n){
			if(k == n)  
				++sum;
			else    //还没到第n行，++k，a[k]从0开始
				a[++k] = 0;
		}else{  //else是a[k]=n+1,这一行都不能放皇后，于是--k回溯
			--k;
		}
	}
}

优雅的位运算

位运算确实优雅
关于位运算的解法，优秀博客链接1里介绍的很详细，只稍作总结
算法思想
对于寻找第k行可放置的皇后，用8位二进制数记录1~k-1行产生的冲突；

  • 1表示有冲突，那么第k行不能放置
  • 0表示无冲突，第k行可以尝试放置

如果8位二进制全为1，显然这一行不能放了，于是回溯；
参考优秀博客链接1中的例子，a、b、c分别记录同列冲突、右斜线冲突、左斜线冲突；
d = a|b|c得到1k-1行产生的冲突（如果对d取反就是第k可放置的皇后）；
`bit = (d+1) & (d)得到一个可放置的皇后的位置； 递归寻找下一行需要更新a,b,ca=a|bit, b=(b|bit)>>1, c=(c|bit)<<1； 寻找同一行的其它皇后需要只更新dd |= bit； ***注：代码中的b=limit&((b|bit)>>1), c=limit&((c|bit)<<1)limit=(1<<n)-1`为什么要n个1和b、c进行与运算呢？
这属于唯一尚未明白的地方，先放在这吧~
另外很多博客里的位运算解法与上面的稍有不同，但思路一样，可以参考优秀博客链接2
————————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int a[10];
int sum;
int n, limit;
void solve(int a, int b, int c,int step){
	if(step == n){
		++sum;
		return;
	}
	int d = a | b | c;
	while(d < limit){   //寻找同一行的可放置的皇后
		int bit = (d +1) & (~d);
		solve(a|bit, limit&((b|bit)>>1), limit&(c|bit)<<1, step+1);
		d |= bit;
	}
}
int main(){
	scanf("%d", &n);
	limit = (1 << n) -1;
	solve(0,0,0,0);
	printf("%d\n", sum);
	return 0;
}

洛谷·P1219 [USACO1.5]八皇后

题目链接：https://www.luogu.com.cn/problem/P1219

洛谷的这道就是n皇后问题，n的范围[6,13]；
亲测使用递归回溯、非递归回溯时，最后一个测试n=13会超时（凭啥别人写的递归就能过）；
但位运算肯定能AC啦。