回溯算法的递归实现

回溯算法的递归实现

由于回溯算法用一栈数组实现的,用到栈一般可用递归实现。

上述例1的递归方法实现如下：

program hh;
const n=4;
var i,k:integer;
    x:array[1..n] of integer;
    st:string[n];
    t:string[n];
procedure input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
   if x=x[k]  then
     begin place:=false; break end ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(t[x]);
writeln;readln;
end;
procedure try(k:integer);
var i :integer;
begin
if k=n+1 then begin print;exit end;
for i:=1 to n do
  begin
   x[k]:=i;
   if place(k) then try(k+1)
  end
end;
begin
input;
try(1);
end.

例2：n皇后问题的递归算法如下：

程序1：

program hh;
const n=8;
var i,j,k:integer;
    x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
   if (x=x[k]) or (abs(x-x[k])=abs(i-k)) then
     place:=false  ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(x:4);
writeln;
end;
procedure try(k:integer);
var i:integer;
begin
if k=n+1 then begin print; exit end;
for i:= 1 to n do
  begin
  x[k]:=i;
  if place(k) then try(k+1);
  end;
end ;
begin
try(1);
end.

程序2：

说明:当n=8 时有30条对角线分别用了l和r数组控制，

用c数组控制列.当(i,j)点放好皇后后相应的对角线和列都为false.递归程序如下:

program nhh;
const n=8;
var s,i:integer;
a:array[1..n] of byte;
c:array[1..n] of boolean;
l:array[1-n..n-1] of boolean;
r:array[2..2*n] of boolean;
procedure output;
var i:integer;
begin
for i:=1 to n do write(a:4);   
inc(s);writeln('  total=',s);
end;
procedure try(i:integer);
var j:integer;
begin
for j:=1 to n do
  begin
   if c[j] and l[i-j] and r[i+j] then
    begin
     a:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false;
     if i<n then try(i+1) else output;
     c[j]:=true;l[i-j]:=true;r[i+j]:=true;
    end;
  end;
end;
begin
for i:=1 to n do c:=true;
for i:=1-n to n-1 do l:=true;
for i:=2 to 2*n do r:=true;
s:=0;try(1);
writeln;
end.