数据结构——回溯

搜索：全面访问所有可能的情况，分为两种：不考虑给定问题的特有性质，按事先顶好的顺序，依次运用规则，即盲目搜索的方法；另一种则考虑问题给定的特有性质，选用合适的规则，提高搜索的效率，即启发式的搜索。
回溯即是较简单、较常用的搜索策略。
基本思路：若已有满足约束条件的部分解，不妨设为（x1,x2,x3,……xi），I<n,则添加x(i+1)属于s(i+2)，检查(x1,x2,……,xi,x(i+1))是否满足条件，满足了就继续添加x(i+2)、s(i+2)，若所有的x(i+1)属于s(i+1)都不能得到部分解，就去掉xi，回溯到(xi,x2,……x(i-1))，添加那些未考察过的x1属于s1，看其是否满足约束条件，为此反复进行，直至得到解或证明无解。 例子
4-1 八皇后问题。
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[i]:=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[i]:=true;
　　　　b[i]:=true;
　　　　c[i]:=true
　　　end;
　　try(1);
　end.

　

跳马问题。在5*5格的棋盘上，有一个国家象棋的马，它可以朝8个方向跳，但不允许出界或跳到已跳过的格子上，要求在跳遍整个棋盘后再条回出发点。
program jump;
　var
　　h:array[-1..7,-1..7] of integer;
　　 a,b:array[1..8] of integer;
　　 i,j,num:integer;
　 procedure print;
　　 var i,j:integer;
　　 begin
　　　 num:=num+1;
　　　 if num<=5 then
　　　 begin
　　　　　 for i:=1 to 5 do
　　　　　　 begin
　　　　　　　 for j:=1 to 5 do write(h[i,j]:4);
　　　　　　　 writeln;
　　　　　　 end;
　　　　　 writeln;
　　　　 end;
　　 end;
　 procedure try(x,y,i:integer);
　　 var　 j,u,v:integer;
　　 begin
　　　 for j:=1 to 8 do
　　　　 begin
　　　　　 u:=x+a[j];
　　　　　 v:=y+b[j];
　　　　　 if h[u,v]=0 then
　　　　　　 begin h[u,v]:=i;
　　　　　　　 if i<25 then try(u,v,i+1)
　　　　　　　 else print;
　　　　　　　 h[u,v]:=0
　　　　　　 end;
　　　　 end;
　　 end;
　 begin
　　 for i:=-1 to 7 do
　　　for j:=-1 to 7 do
　　　　 if (i>=1)and(i<=5)and(j>=1)and(j<=5)
　　　　　 then h[i,j]:=0
　　　　 else h[i,j]:=1;
　　 a[1]:=2;b[1]:=1;
　　 a[2]:=1;b[2]:=2;
　　 a[3]:=-1;b[3]:=2;
　 　a[4]:=-2;b[4]:=1;
　　 a[5]:=-2;b[5]:=-1;
　　 a[6]:=-1;b[6]:=-2;
　　 a[7]:=1;b[7]:=-2;
　　 a[8]:=2;b[8]:=-1;
　　 num:=0;
　　 h[1,1]:=1;
　　 try(1,1,2);
　　 writeln('num=',num);
　end. 思考题

4-2 试编程找出下列字母方阵中所隐含的单词 "fujian",单词中字母的走向可以是图的编号为1----8的8个方向，要求打印的格式为：
（x,y）,a1,a2,a3,a4,a5
(其中（x,y）为首字母"f"所在的行、列坐标，a1,a2,a3,a4,a5为后续每个字母相对前一个字母的代号。

f u j u a n
j i f i u n
n u i j u f
u a n j n a
i a j f i u
j n n i n f