用户登录:

用户名:
密码:      

文章分类:


最新评论:

userleijiankun 说:膜拜神牛。……
usercss 说:康拓展开和逆康拓展……
usersongrenchu 说:欢迎大家踊……
userAdmin 说:……

N皇后问题

发表时间:2010-04-25 21:11:46  浏览(1972) 评论(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.

网友评论:

user1  lonelycorn 于 2010-05-14 23:31:57 说:回复
最后一列不用枚举,用n*(n-1)/2-前面每列的坐标和,略有优化效果,不用位运算能过usaco 13皇后。
user2  Admin 于 2010-05-15 19:03:05 说:回复
回复lonelycorn:是的。那个优化效果挺明显,貌似能减少n*ans那么多的搜索量?

Guest 发表评论