N皇后问题

文章类别：C语言程序设计 | 发表日期:2008-9-24 14:45:44

一【题目】N皇后问题(含八皇后问题的扩展，规则同八皇后)：在N*N的棋盘上，放置N个皇
后，要求每一横行每一列，每一对角线上均只能放置一个皇后，求解可能的方案及方案数。
下面是算法的实现源码，请大家讨论。
      const max=8;
      var i,j:integer;
      a:array[1..max] of 0..max; {放皇后数组}
      b:array[2..2*max] of boolean; {/对角线标志数组}
      c:array[-(max-1)..max-1] of boolean; {\对角线标志数组}
      col:array[1..max] of boolean; {列标志数组}
      total:integer; {统计总数}
      procedure output; {输出}
      var i:integer;
    begin
      write('No.':4,'[',total+1:2,']');
      for i:=1 to max do
             write(a[i]:3);write(' ');
      if (total+1) mod 2 =0
            then writeln; inc(total);
    end;
     function ok(i,dep:integer):boolean; {判定第dep行第i列可放否}
        begin
           ok:=false;
             if ( b[i+dep]=true) and ( c[dep-i]=true) {and (a[dep]=0)} and
                         (col[i]=true)  
             then ok:=true
          end;
      procedure try(dep:integer);
          var i,j:integer;
         begin
            for i:=1 to max do {每一行均有max种放法}
                if ok(i,dep) then
                 begin
                 a[dep]:=i;
                   b[i+dep]:=false; {/对角线已放标志}
                   c[dep-i]:=false; {\对角线已放标志}
                 col[i]:=false; {列已放标志}
            if dep=max then output
                 else try(dep+1); {递归下一层}
              a[dep]:=0; {取走皇后,回溯}
              b[i+dep]:=true; {恢复标志数组}
              c[dep-i]:=true;
              col[i]:=true;
       end;
      end;
    begin
        for i:=1 to max do
              begin
               a[i]:=0;col[i]:=true;
              end;
              for i:=2 to 2*max do
                 b[i]:=true;
              for i:=-(max-1) to max-1 do
                  c[i]:=true;
             total:=0;
            try(1);
           writeln('total:',total);
end.

上一篇：{应用}数据结构题集--数组(二维数组-1) 人气:7266
下一篇：{应用}链表的运算(01) 人气:6243

C语言程序设计视频教程