论坛交流
首页办公自动化| 网页制作| 平面设计| 动画制作| 数据库开发| 程序设计| 全部视频教程
应用视频: Windows | Word2007 | Excel2007 | PowerPoint2007 | Dreamweaver 8 | Fireworks 8 | Flash 8 | Photoshop cs | CorelDraw 12
编程视频: C语言视频教程 | HTML | Div+Css布局 | Javascript | Access数据库 | Asp | Sql Server数据库Asp.net  | Flash AS
当前位置 > 文字教程 > C语言程序设计教程
Tag:新手,函数,指针,数据类型,对象,Turbo,入门,运算符,数组,结构,二级,,tc,游戏,试题,问答,编译,视频教程

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.
视频教程列表
文章教程搜索
 
C语言程序设计推荐教程
C语言程序设计热门教程
看全部视频教程
购买方式/价格
购买视频教程: 咨询客服
tel:15972130058