本讲，我们来谈谈搜索与回溯。

　　搜索与回溯是计算机解题中常用的算法，有很多问题无法根据某种确定的计算法则来求解，此时可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。

　　如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进，如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。

　　例1 　在８×８的国际象棋盘上，放置八个皇后，使任何一个皇后都不能吃掉另一个。

　　分析：要使任何一个皇后都不能吃掉另一个，需满足的条件是：同一行、同一列、同一对角线上只能有一个皇后。

　　考虑每行有且仅有一个皇后，设一维数组Ａ[1..8]表示皇后的放置：第ｉ行皇后放在第ｊ列，用Ａ[i]＝j来表示，即下标是行数，内容是列数。

　　放置第ｉ个皇后的算法为：
　　procedure try(i)；
　　　begin
　　　　选择第i个皇后的位置；
　　　　　if 安全 then
　　　　　　begin
　　　　　　　放置第i个皇后；
　　　　　　　if i=8 then 输出
　　　　　　　　else try(i+1)；{放置第i+1个皇后}
　　　　　　　　放置不成功，回溯一步，当前皇后退出，尝试下一个位置是否可行
　　　　　　end；
　　　end；

　　判断皇后是否安全，即检查同一列、同一对角线是否已有皇后，建立标志数组ｂ[1..8]控制同一列只能有一个皇后，若两皇后在同一对角线上，则其行列坐标之和或行列坐标之差相等，故亦可建立标志数组ｃ[1..16]、ｄ[-7..7]控制同一对角线上只能有一个皇后。

　　从分析中，我们不难看出，搜索前进过程实际上是不断递归调用的过程，当递归返回时即为回溯的过程。

源程序如下：
program ex1;
var
　a:array[1..8] of byte;
　b:array[1..8] of boolean;
　c:array[1..16] of boolean;
　d:array[-7..7] of boolean;
　sum:byte;
procedure pr;
　var j:byte;
　begin
　　for j:=1 to 8 do write(a[j]:4);
　　inc(sum);writeln(' sum=',sum);
　end;
procedure try(t:byte);
　var i:byte;
　begin
　　for i:=1 to 8 do
　　　if b[i] and c[t+i] and d[t-i] then {寻找放置皇后的位置}
　　　　begin　{放置皇后,建立相应标志值}
　　　　　a[t]:=i;
　　　　　b[i]:=false;
　　　　　c[t+i]:=false;
　　　　　d[t-i]:=false;
　　　　　if t=8 then pr;{８个皇后都放置好,输出}
　　　　　else try(t+1);{继续递归放置下一个皇后}
　　　　　b[i]:=true; {递归返回即为回溯一步,当前皇后退出}
　　　　　c[t+i]:=true;
　　　　　d[t-i]:=true;
　　　　end;
　end;
begin
　fillchar(b,sizeof(b),#1);
　fillchar(c,sizeof(c),#1);
　fillchar(d,sizeof(d),#1);
　sum:=0;
　try(1);
end.