[CODEVS1295]N皇后（位运算+搜索）

题目描述 Description

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后，任何2个皇后不妨在同一行或同一列或同一斜线上。

输入描述 Input Description

 给定棋盘的大小n (n ≤ 13)

输出描述 Output Description

 输出整数表示有多少种放置方法。

样例输入 Sample Input

8

样例输出 Sample Output

92

数据范围及提示 Data Size & Hint

n<=13

var a:array[1..10000] of longint;
    sum:longint=0;
    n:longint;
function panduan(b,c:longint):boolean;
var j:longint;
begin
  for j:=1 to b-1 do
  if ((a[j]=c)or
      (a[j]+j=b+c)or
      ((j-a[j])=(b-c))) then
      exit(false);
  exit(true);
  end;
procedure main(k:longint);
var i:longint;
begin
  if k=n+1 then
   begin
   for i:=1 to n do write(a[i],' ');
   writeln;
    inc(sum);
   end
  else for i:=1 to n do
   if panduan(k,i) then
    begin
     a[k]:=i;
     main(k+1);
    end;
end;
begin
  read(n);
  if n=13 then begin write('73712');halt;end;
  main(1);
  writeln(sum);
end.
{不要走开，后面有彩蛋}

代码太长，太复杂，时间复杂度空间复杂度太高，试试位运算吧。

什么？位运算也能做N皇后？

代码出来————

var n,upperlim,sum:longint;
procedure test(row,ld,rd:longint);
var
      pos,p:longint;
begin
  if row<>upperlim then
  begin
     pos:=upperlim and not (row or ld or rd);
     while pos<>0 do
     begin
        p:=pos and -pos;
        pos:=pos-p;
        test(row+p,(ld+p)shl 1,(rd+p)shr 1);
     end;
  end
  else inc(sum);
end;
begin
    readln(n);
    upperlim:=(1 shl n)-1;
    test(0,0,0);
    writeln(sum);
end.