N皇后问题
发表时间：2010-04-25 21:11:46 浏览(3634) 评论(2)
N皇后问题是一个十分著名的问题。其递归思想和精益求精的优化方法值得我们学习。下面我们对这个问题做一些探讨。
【题目大意】
给定一个N*N的棋盘，要向其中放入N个皇后。要求她们任意两个不能同行，不能同列，不能同主或副对角线。给定棋盘大小N，问共有多少种不同的放置方法。
【第一想法】
我们可以以行作为搜索的依据，然后设置列数组、主对角线数组、右对角线数组三个布尔数组记录每列、每条主对角线、每条副对角线是否被占用。在循环当前行的某个格子，发现其列、主辅对角线均未被占用，则该格子可以放一个皇后。我们就可以尝试放在该点一个皇后并进入下一行的搜索。我们可以用某个格子的横纵坐标的和差分别表示其所在主辅对角线。
Pascal代码：
var i,j,k,l,m,n,ans:longint;
h,z,f:array[-24..24] of boolean;
procedure dfs(x:longint);
var t:longint;
begin
if (x>n) then
begin
inc(ans);
exit;
end;
for t:=1 to n do
if (not h[t])and(not z[x+t])and(not f[x-t]) then
begin
h[t]:=true;z[x+t]:=true;f[x-t]:=true;
dfs(x+1);
h[t]:=false;z[x+t]:=false;f[x-t]:=false;
end;
end;
begin
read(n);
ans:=0;
dfs(1);
writeln(ans);
end.
这种最朴素的算法当n<=12时能在1s内出解。
【对称性优化】
考虑到图形具有对称性。当n为偶数时，在第一行将皇后放置在前n/2个格子中和将她放在后n/2个格子中的方案数是一样的。所以，我们可以在搜第一行的时候只做前一半，然后将答案*2。
当n为奇数时，我们先将一个皇后放在中间列的前n div 2个位置，将第二个皇后放在中间行前n div 2-1个位置，且其列标号不要超过第一个皇后的行标号。这样每一个方案都对应于8个不同的方案。特殊的当皇后放到正中心的时候要另搜一次。（本段参考Nocow上的题解）
这种优化能在1s之内解决n<=13的情况。
【双向链表优化】
为了加快寻找每一行哪些地方可以放皇后，我们可以用一个双向链表来维护。
一种比较方便的方式是用数组模拟双向链表。我们用数组pre和next分别表示每个链表中元素的前驱和后继。当一个点被删除时，改变其前驱的后继为其后继，后继的前驱为其前驱。这样下次访问时就不会访问到该点。恢复的方法是将其前驱的后继和后继的前驱改回其自身。当某一列被占用时，我们将链表做相应修改，这样越到后面的行所扫描的元素数量越少。
这种优化能在1s之内解决n<=15的情况。
【位运算优化】
（本段参考Matrix67的题解）
我们可以用n位2进制数表示已经被占用的列状况。某一列已被占用，则该位表示为1，否则表示为0。这样，所有的0位就是我们可以占用的位。类似的，我们也可以表示出主、副对角线当前状态的2进制表示。在递归每一层的时候，我们先通过上面的3个数字的or值求反得出当前行的可用情况。1为可用，0为不可用。通过lowbit操作取出最右边的1的位置，然后尝试在该位置放一个皇后，将3个状态的改变带入下一层搜索。最终得出答案。
lowbit(x)=x and (x xor (x-1))=x and -x,表示2的x最低位1从右往左数的位置次方。
每次迭代到下一层，对角线的影响的位会发生相应的错位。
Pascal代码：
var n,final,ans:longint;
procedure work(h,z,f:longint);
var t,now:longint;
begin
if (h=final) then
begin
inc(ans);
exit;
end;
now:=final and not (h or z or f);
while (now>0) do
begin
t:=now and -now;
work(h+t,(z+t) shl 1,(f+t) shr 1);
dec(now,t);
end;
end;
begin
read(n);
ans:=0;
final:=1 shl n -1;
work(0,0,0);
writeln(ans);
end.
【题目大意】
给定一个N*N的棋盘，要向其中放入N个皇后。要求她们任意两个不能同行，不能同列，不能同主或副对角线。给定棋盘大小N，问共有多少种不同的放置方法。
【第一想法】
我们可以以行作为搜索的依据，然后设置列数组、主对角线数组、右对角线数组三个布尔数组记录每列、每条主对角线、每条副对角线是否被占用。在循环当前行的某个格子，发现其列、主辅对角线均未被占用，则该格子可以放一个皇后。我们就可以尝试放在该点一个皇后并进入下一行的搜索。我们可以用某个格子的横纵坐标的和差分别表示其所在主辅对角线。
Pascal代码：
var i,j,k,l,m,n,ans:longint;
h,z,f:array[-24..24] of boolean;
procedure dfs(x:longint);
var t:longint;
begin
if (x>n) then
begin
inc(ans);
exit;
end;
for t:=1 to n do
if (not h[t])and(not z[x+t])and(not f[x-t]) then
begin
h[t]:=true;z[x+t]:=true;f[x-t]:=true;
dfs(x+1);
h[t]:=false;z[x+t]:=false;f[x-t]:=false;
end;
end;
begin
read(n);
ans:=0;
dfs(1);
writeln(ans);
end.
这种最朴素的算法当n<=12时能在1s内出解。
【对称性优化】
考虑到图形具有对称性。当n为偶数时，在第一行将皇后放置在前n/2个格子中和将她放在后n/2个格子中的方案数是一样的。所以，我们可以在搜第一行的时候只做前一半，然后将答案*2。
当n为奇数时，我们先将一个皇后放在中间列的前n div 2个位置，将第二个皇后放在中间行前n div 2-1个位置，且其列标号不要超过第一个皇后的行标号。这样每一个方案都对应于8个不同的方案。特殊的当皇后放到正中心的时候要另搜一次。（本段参考Nocow上的题解）
这种优化能在1s之内解决n<=13的情况。
【双向链表优化】
为了加快寻找每一行哪些地方可以放皇后，我们可以用一个双向链表来维护。
一种比较方便的方式是用数组模拟双向链表。我们用数组pre和next分别表示每个链表中元素的前驱和后继。当一个点被删除时，改变其前驱的后继为其后继，后继的前驱为其前驱。这样下次访问时就不会访问到该点。恢复的方法是将其前驱的后继和后继的前驱改回其自身。当某一列被占用时，我们将链表做相应修改，这样越到后面的行所扫描的元素数量越少。
这种优化能在1s之内解决n<=15的情况。
【位运算优化】
（本段参考Matrix67的题解）
我们可以用n位2进制数表示已经被占用的列状况。某一列已被占用，则该位表示为1，否则表示为0。这样，所有的0位就是我们可以占用的位。类似的，我们也可以表示出主、副对角线当前状态的2进制表示。在递归每一层的时候，我们先通过上面的3个数字的or值求反得出当前行的可用情况。1为可用，0为不可用。通过lowbit操作取出最右边的1的位置，然后尝试在该位置放一个皇后，将3个状态的改变带入下一层搜索。最终得出答案。
lowbit(x)=x and (x xor (x-1))=x and -x,表示2的x最低位1从右往左数的位置次方。
每次迭代到下一层，对角线的影响的位会发生相应的错位。
Pascal代码：
var n,final,ans:longint;
procedure work(h,z,f:longint);
var t,now:longint;
begin
if (h=final) then
begin
inc(ans);
exit;
end;
now:=final and not (h or z or f);
while (now>0) do
begin
t:=now and -now;
work(h+t,(z+t) shl 1,(f+t) shr 1);
dec(now,t);
end;
end;
begin
read(n);
ans:=0;
final:=1 shl n -1;
work(0,0,0);
writeln(ans);
end.
网友评论：
 | 1 lonelycorn 于 2010-05-14 23:31:57 说： | 回复 |
|---|---|---|
最后一列不用枚举，用n*(n-1)/2-前面每列的坐标和，略有优化效果，不用位运算能过usaco 13皇后。
| ||
 | 2 Admin 于 2010-05-15 19:03:05 说： | 回复 |
回复lonelycorn：是的。那个优化效果挺明显，貌似能减少n*ans那么多的搜索量？
|