Algorithm 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Algorithm
标  题: 回溯法:八皇后问题
发信站: 哈工大紫丁香 (Wed Aug 13 16:04:12 2003)

,求问题的解,而是通过试探和纠正错误的策略,找到问题的街.这种方法一般是从一个原

始状态出发,通过若干步试探,最后达到目标状态终止.
    回溯法在理论上来说,就是在一棵搜索树中从根结点出发,找到一条达到满足某条件

的子结点的路径.在搜索过程中,对于每一个中间结点,他的位置以及向下搜索过程是相似

的,因此完全可以用递归来处理.典型的例子就是著名的"八皇后问题".
    "八皇后问题"是在国际象棋棋盘上放置八个皇后,使她们不能相吃.国际象棋中的皇

后可以吃掉与她处于同一行,同一列,同一对角线上的棋子.因此每一行只能摆放一个皇后

.因共有八行,所以每行有且只有一个皇后.
    在本例中皇后的位置有一个一维数组来存放A(I)=J表示第I行皇后放在第J列.下面主

要来看看怎么样判断皇后是否安全的问题.(1)首先,用一维数组来表示,已经解决了不在

同一行的问题.(2)对于列可以引进一个标志数组C[J],若J列上已放了皇后,则C[J]=FALS

E.(3)对于左上右下的对角线I-J为一常量,位于[-7,+7]之间,再此引入标志数组L[-7..7

];对于左下右上的对角线,类似的有I+J等于常量,用数组R[2..16]来表示.当在第I行,第

J列上放置了皇后,则只需设置:C[J]:=FALSE; L[I-J]:=FLASE; R[I+J]:=FALSE就可以解

决皇后的安全问题了.
源程序如下:
Program eightqueens;
   var cont,i:integer;
       a:array[1..8] of byte;
      c:array[1..8] of boolean;
       l:array[-7..7] of boolean;
        r:array[2..16] of boolean;
       q:boolean;
procedure pr;
   var i:integer;
begin
   for i:=1 to 8 do write(a[i]:4);
   inc(cont);writeln('cont=',cont);
end;
procedure try(i:integer);
 var j:integer;
  procedure erase(i:integer);
   begin
    c[j]:=true;l[i-j]:=true;r[i+j]:=true;
   end;
 begin
    for j:=1 to 8 do
  begin
     if c[j] and l[i-j] and r[i+j] then
begin
   a[i]:=j;c[j]:=false;l[i-j]:=false;
   r[i+j]:=false;
    if i<8 then try(i+1)
     else pr;
   erase(i);
   end;
  end;
end;
{***************************main*******************************}
begin
for i:=1 to 8 do c[i]:=true;
for i:=-7 to 7 do l[i]:=true;
for i:=2 to 16 do r[i]:true;
cont:=0;
i:=1;
try(i);
readln;
end.
用递归算法编制的程序具有结构清晰和移读性高的特点,但是也有执行效率不高的缺点.

但当能够找到明显的递推公式用迭代法求解时,迭代法的效率会比递归方法高很多.还请

大家根据情况来选择使用!

--
╔═══════════════════╗
║★★★★★友谊第一  比赛第二★★★★★║
╚═══════════════════╝

※ 来源:．哈工大紫丁香 bbs.hit.edu.cn [FROM: 202.118.229.162]