Ｎ皇后问题

问题描述：
　　在Ｎ*Ｎ的棋盘上，放置Ｎ个皇后，要求每一横行，每一列，每一对角线上均只能放置一个皇后，求可能的方案及方案数。  
 
{
  Problem   : N Queens Problem
  Algorithm : Depth First Search
  Author    : tenshi
  Date      : 2002-07-14 @ SJTU ZZL 111
}
Program N_Queens;
const n=8;
var
  a:array[1..n] of integer;   { 皇后放在 ( i, a ) }
  mk:array[1..n] of boolean; { 如果mk为true，表示第i列可以放 }
  total:integer;             { 方案总数 }
  
  procedure output; {输出}
  var i:integer;
  begin
    inc(total);
    write('No.':4,'[',total:2,']');
    for i:=1 to n do write(a:3);
    writeln;    
  end;
  
  function can(d:integer):boolean;  {判断第d行的Queen可否放在第a[d]列}
  var i:Integer;
  begin
    can:=false;
    if mk[a[d]] then exit; {如果第d列已经被占，则返回false}
    for i:=1 to d-1 do
      if abs(a-a[d])=abs(i-d) then exit; { 如果第i行和第d行的Queen在同一对角线上，则返回false }
    can:=true;
  end;
  
  procedure dfs(d:integer);
  var i,j:integer;
  begin
    if (d>n) then  { 找到一个解并输出 }
    begin
      output;  
      exit;
    end;
    for i:=1 to N do   { 每一行均有N种放法 }
    begin
      a[d]:=i;          { 第d行的Queen放在第a[d]列 }
      if can(d) then
      begin
        mk:=true;   { 标记第i列已经被占 }
        dfs(d+1);      { 如果第d行的方法可行，就放下一行 }
        mk:=false;  { 恢复第i列被占标记 }
      end;                      
    end;
  end;
  
  begin
    fillchar(mk,sizeof(mk),0);
    dfs(1);
    writeln('Total = ',total);
  end.