|
3.1 N 皇后问题
【问题描述】在国际象棋中，皇后可以攻击与她在同一条水平线、垂直线和对角线的棋子。现在有一张 N×N
的国际象棋棋盘，在上面放置 N 个皇后。有多少种使皇后不能互相攻击的方案？（N≤13）
(1) 深度优先搜索（DFS）
逐列（行）搜索。每测试一个位置，就检查它是否与其他皇后冲突，如果冲突，回溯①。
每放置一个皇后，就要记录——所在列、“/”对角线和“\”对角线都不能放皇后了。
#include <iostream>
#include <cstring>
using namespace std;
bool column[20],cross1[50],cross2[50];
int pos[20];
int n, sum=0;
void dfs(int row)
{
if (row==n)
{
sum++;
return;
}
for (int i=0;i<n;i++)
if (!(column[i] || cross1[row-i+n] || cross2[row+i])) // 判断是否可以放置皇后
{
// 对皇后已经控制的列和对角线做标记
column[i]=cross1[row-i+n]=cross2[row+i]=true;
pos[row]=i;
dfs(row+1);
// 解除标记，这样才能在新位置上放置皇后。
column[i]=cross1[row-i+n]=cross2[row+i]=false;
}
}
int main()
{
cin>>n;
memset(column,0,sizeof(column));
memset(cross1,0,sizeof(cross1));
memset(cross2,0,sizeof(cross2));
dfs(0);
cout<<sum<<endl;
return 0;
}
(2) 状态压缩*
把状态放在一个 4 字节的 int 整型变量中，并且使用位运算——这样，速度会比朴素算法的快很多。
#include <iostream>
using namespace std;
// sum用来记录皇后放置成功的不同布局数；upperlim用来标记所有列都已经放置好了皇后。
int n, sum = 0, upperlim = 1;
// 搜索算法，从最右边的列开始。
void test(long row, long ld, long rd)
{
if (row != upperlim)
{
/*
row，ld，rd进行“或”运算，求得所有可以放置皇后的列,对应位为0，
然后再取反后“与”上全1的数，来求得当前所有可以放置皇后的位置，对应列改为1。
也就是求取当前哪些列可以放置皇后。
*/
long pos = upperlim & ~(row | ld | rd);
while (pos) // 0 -- 皇后没有地方可放，回溯。
{
/*
拷贝pos最右边为1的bit，其余bit置0。
也就是取得可以放皇后的最右边的列。
*/
long p = pos & -pos;
/*
将pos最右边为1的bit清零。
也就是为获取下一次的最右可用列使用做准备，
程序将来会回溯到这个位置继续试探。
*/
pos -= p;
/*
row + p，将当前列置1，表示记录这次皇后放置的列。
(ld + p) << 1，标记当前皇后左边相邻的列不允许下一个皇后放置。
(ld + p) >> 1，标记当前皇后右边相邻的列不允许下一个皇后放置。
*/
/*
此处的移位操作实际上是记录对角线上的限制，只是因为问题都化归
到一行网格上来解决，所以表示为列的限制就可以了。显然，随着移位
在每次选择列之前进行，原来N×N网格中某个已放置的皇后针对其对角线
上产生的限制都被记录下来了。
*/
test(row + p, (ld + p) << 1, (rd + p) >> 1);
}
}
else
sum++; // row的所有位都为1，即找到了一个成功的布局，回溯。
}
int main()
{
cin>>n;
// N个皇后只需N位存储，N列中某列有皇后则对应bit置1。
upperlim = (upperlim << n) - 1;
test(0, 0, 0);
cout<<sum;
return 0;
}
|