大榕树——让我们共成长!
大榕树 myDrs.org
您的位置:大榕树 \ 编程       |  Logo语言   |  Pascal语言   |  信息学奥赛   |  高考保送    |  HTML版本
|  Pascal语言>>Pascal入门>>八皇后问题程序及注解         本站全文搜索: 友情提示:

八皇后问题程序及注解
http://www.mydrs.org  12/3/2003  大榕树


大家一定见过这种办法吧 ,但是做为初学者理解起来特别困难 ,我就把我当时对它的理解简单说一下,不对的地方大家给个 建议! 
program eightqueens;
 var
  x:array[1..8] of integer;
  a,b,c:array[-7..16] of boolean;
  i:integer;
 procedure print;
  var k:integer;
  begin
   for k:=1 to 8 do write(x[k]:4);
   writeln;
  end;
 procedure try(i:integer);
  var j:integer;
  begin
   for j:=1 to 8 do
    if a[j] and b[i+j] and c[i-j]
     then begin
   x:=j;
   a[j]:=false;
   b[i+j]:=false;
   c[i-j]:=false;
   if i<8 then try(i+1)
    else print;
   a[j]:=true;
   b[i+j]:=true;
   c[i-j]:=true
  end
 end;
 begin
  for i:=-7 to 16 do
   begin
    a:=true;
    b:=true;
    c:=true
   end;
  try(1);
 end.     现在循环从 i=1 ,j:=1 to 8 do 开始 此时 计算机检测到 i=1 j=1 简化为(1,1)为空,占用该位置并令该位置对应的斜线和水平方向的位置为 false ,然后程序就开始去执行try(2),注意此时计算机在i=1 这层仅仅走拉一个循环(j=1)就跳到拉i=2 这层里此时计算机从j:=1 to 8 do 又开始循环,排除 j=1,j=2 得到 (2,3)注意计算机在层里也只是走拉3(j=3)个循环然后又跳到拉i=3 这层依次类推得到(3,5),(4,2)(5,4)而在i=6 这层里计算机从j:= 1 to 8 do 都没有找到合适的位置,此时注意在i=6 这层里计算机计算机将返回到i=5 这层里,(因为用拉递归)并且释放(5,4)该位置,为什么要释放呢?因为原因很简单如果不释放的话 该位置对应的斜线和水平方向会对以后的几层造成影响,让计算机误认为为false。此时的在i=5这层里 j=4才是结束,然后计算机又会从j=5到 8 开始去找合适的位置 ,如果找不到又会返回到上一层依次类推直到计算机找到一组解 输出,假设在(8,3)这个位置是计算机找到的一组解,此时计算机又会从j=4到8 开始循环,如果找不到 计算机就会返回上一层的即i=7这层接着上一次的跳出位置走完以后的循环,依次类推不断的返回,跳出, 求解,(即令前几个位置不变,从第8个位置变换,没有空位置的。接会返回上一层)最后返回到i=1这层里,注意此时在这层里也只是走拉j=1个循环然后计算机就又开始从j= 2 去试着找....大家有没有算过求出所有的解要走过多少个循环?我想估计也不下1000个吧。其实整个过程就是一个重复的过程(即递归)倒着想在i=7 这层里的j=1 位置即(7,1) 计算机会去试从(8,1)到(8,8)这8 个位置,而在(7,2)也同样会去试这8 个位置 等等在(6,1)会试(7,1)到(7,8) 等。 这是正着考虑(1,1)这里计算机会试着从(2,1)到(2,8)这8个位置而在这8 个位置里并没有试完就有空位置 (2,3)此时计算机会在这个位置对下一层里开始试(3,1)..(3,8)依次类推,试不通的返回,接着走完上一层直到试完所有的位置!

作 者:陕西科技大学 王成林
来 源:投稿
共有24240位读者阅读过此文

  • 上篇文章第九届分区复赛提高组数据
  • 下篇文章Pascal的多种退出语句用法

  • 发送邮件
    保存页面 打印文章 HTML版本 发表评论

    □- 近期热门文章 □- 相关文章
    1. NOIP2006竞赛大纲 [8307]
    2. 七类高中生具有保送资格 [5911]
    3. NOI2006获奖选手名单 [4956]
    4. 关于举办NOIP2006模拟赛的通告 [4107]
    5. Turbo Pascal各语句运行速... [3595]
    6. Turbo王者归来新Delphi免费... [3182]
    7. IOI2006我国4名选手全部获得金... [2946]
    8. 关于APIO2007与IOI2007... [2764]
    9. noip倒计时 by 枯叶蝴蝶 [2684]
    10. 朱泽园:思想上的金牌更重要 [2169]
    八皇后问题程序及注解
    高斯八皇后
     

    关于本站 | 合作伙伴 | 联系方式
    大榕树 版权所有 ©1999-2006 www.myDrs.org 闽ICP备05000721号