我们在解决一些算法时，会遇到这样的一类题目，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。但是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯法，因为它花费的时间比较长。 
回溯算法在Pascal中的一般形式： 
procedure tryit(i:integer); 
var j:integer; 
begin 
    for j:=1 to maxj do 
      if   新结点符合条件 then 
        begin 
           记录新结点； 
           if  新结点是目标结点 then  输出  else tryit(i+1); 
           删除结点； 
        end; 
end; 

下面给出四个回溯算法在Pascal中的应用。 

1、八皇后问题 
这个实例堪称回溯算法的经典。 
【题目叙述】我们都知道，在国际象棋中，皇后的攻击范围是其所在的行，列以及两条对角线；如果在一个8×8的棋盘上要放置8个皇后，并且使得它们互不攻击，给出所有放法。 
【问题分析】1、冲突。包括行、列、两条对角线： 
　　（1）列：规定每一列放一个皇后，不会造成列上的冲突； 
　　（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态； 
　　（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。 
　　2、数据结构。 
　　（1）解数组A。A表示第I个皇后放置的列；范围：1…8 
　　（2）行冲突标记数组B。B=0表示第I行空闲；B=1表示第I行被占领；范围：1…8 
　　（3）对角线冲突标记数组C、D。 
　　C=0表示第（I-J）条对角线空闲；C=1表示第（I-J）条对角线被占领；范围：-7…7 
　　D=0表示第（I+J）条对角线空闲；D=1表示第（I+J）条对角线被占领；范围：2…16 
【参考程序】 
var a:array[1..8] of integer; 
    b,c,d:array[-7..16] of integer; 
    t,i,j,k:integer; 
procedure print; 
begin 
  t:=t+1; 
  write(t,':'); 
  for k:=1 to 8 do write(a[k]:4); 
  writeln; 
end; 
procedure tryit(i:integer); 
var j:integer; 
begin 
  for j:=1 to 8 do 
    if (b[j]=0) and (c=0) and (d=0) then 
    begin 
      a:=j; 
      b[j]:=1; 
      c:=1; 
      d:=1; 
      if i=8 then print else tryit(i+1); 
      b[j]:=0; 
      c:=0; 
      d:=0; 
    end; 
end; 
begin 
  fillchar(b,sizeof(b),0); 
  fillchar(c,sizeof(c),0); 
  fillchar(d,sizeof(d),0); 
  tryit(1); 
end. 

2、走台阶问题 
【题目叙述】你眼前一共有n级台阶（n为正整数），现在你要走完这n级台阶，已知你只能一步走一级或一步走两级，请你算算一共有多少种走法，并把这些走法都给出。 
【输入输出样例】输入：3 
                输出：1 1 1 
                      1 2 
                      2 1 
【问题分析】每走一步（可以用变量i来表示），都有两种选择，要么走一级，要么走两级，于是这里的maxj便是2；还需要一个计数器s，用来统计走过的台阶数，目标结点便是当s=n的时候。 
【参考程序】 
const n=10;m=5000; 
var a:array[1..m] of integer; 
    i,j,w,k,t,s:integer; 
procedure print; 
begin 
  t:=t+1; 
  write(t,':'); 
  for k:=1 to w do write(a[k]:4); 
  writeln; 
end; 
procedure tryit(i:integer); 
var j:integer; 
begin 
  for j:=1 to 2 do 
    if s+j<=n then 
    begin 
      s:=s+j;w:=w+1; 
      a:=j; 
      if s=n then print else tryit(i+1); 
      s:=s-j;w:=w-1; 
    end; 
end; 
begin 
  s:=0;w:=0; 
  for i:=1 to m do a:=0; 
  tryit(1); 
  writeln('There are ',t,' times.'); 
end. 

3、找数 
【题目叙述】键盘输入n个正整数（互不相等），找出其中和等于m的数的组合。 
【输入输出样例】输入：5（m的值） 1 2 3 4 5 
                输出：1 4 
                      2 3 
                      5 
【问题分析】这个问题和上面的走台阶问题类似，不同的是，这里要用到集合类型的数组，来统计出现过的组合，比如说组合"2，3"与"3，2"是同一个组合，因此不能重复出现，之所以是集合类型的，是因为集合[2,3]与集合[3,2]是完全相同的两个集合，而数组不具备这样的特点，这也就是这道题目的难点。 
【参考程序】 
type nb=set of 0..255; 
const max=10000; 
var a,b:array[1..max] of integer; 
    sb:array[1..max] of nb; 
    jh,jh2:set of 0..255; 
    n,m,i,j,w,k,t,s,p,q,r:integer; 
procedure print; 
begin 
  for k:=1 to w do jh2:=jh2+]; 
  for p:=1 to max do 
  begin 
    q:=p; 
    if jh2=sb[p] then 
    begin 
      q:=q-1; 
      break; 
    end; 
  end; 
  if q=max then begin 
    sb[r]:=jh2;r:=r+1; 
    t:=t+1; 
    write(t,':'); 
    for k:=1 to w do write(b[k]:4); 
    writeln; 
  end; 
  jh2:=[]; 
end; 
procedure tryit(i:integer); 
var j:integer; 
begin 
  for j:=1 to n do 
    if (s+a[j]<=m) and not(a[j] in jh) then 
    begin 
      s:=s+a[j];b:=a[j];w:=w+1;jh:=jh+[a[j]]; 
      if s=m then print else tryit(i+1); 
      s:=s-a[j];w:=w-1;jh:=jh-[a[j]]; 
    end; 
end; 
begin 
  s:=0;w:=0;jh:=[];jh2:=[];r:=1; 
  for i:=1 to max do sb:=[]; 
  fillchar(b,sizeof(b),0); 
  write('How many numbers do you want to process:');read(n); 
  write('Please input the total:');read(m); 
  write('Please input the numbers:'); 
  for i:=1 to n do read(a); 
  writeln('--------------------------------------------------------------'); 
  tryit(1); 
  if t=0 then writeln('Sorry,there are no suitable numbers.'); 
  writeln('--------------------------------------------------------------'); 
  writeln('There are ',t,' suitable groups.'); 
end. 
（程序变量太多，我自己写的时候都差点晕了，所以有待优化与改进） 

4、液晶数字问题 
【题目叙述】 如下图所示：0..9这10个数字可以由下列7个发光二极管组成。0-9十个数字排成一排，每个数字只可以用一次。排列要求：相邻数字后一个是由前一个数字添上几笔或是减去几笔得到的，不允许同时加减。例如：3和8，8和3可以相邻，3和5不能相邻等。问：有多少符合要求的排列？给出所有排列方法。 
[img]http://b7.photo.store.qq.com/http_imgload.cgi?/rurl4_b=aa6c2d3c76d790585ad863ad2c819b721a91f6d06f0676a44fd5ee3c76e191092103e77c8fd1945027d037893099dad60695548e6c38564b5b9b47789e09a3f817e8850d90280720b04000b359d3d40865acde80[/img]
【问题分析】由图可以知道，每一个数字（0-9）在液晶屏上都可以表示为几个数字的编号，比如数字2可以表示为2，3，4，5，6，这样就可以定义一个集合类型的数组，其中的每一个集合代表一个数字，其内容为编号1-7。 
【参考程序】 
type jh=set of 1..7; 
const num:array[0..9] of jh=([1..3,5..7],[3,7],[2..6],[2..4,6,7],[1,3,4,7],[1,2,4,6,7],[1,2,4..7],[2,3,7],[1..7],[1..4,6,7]); 
var a:array[1..10] of integer; 
    b:array[0..10] of integer; 
    ss:set of 0..9; 
    t,k,i,j:integer; 
procedure print; 
begin 
  t:=t+1; 
  write(t,':'); 
  for k:=1 to 10 do write(a[k]:4); 
  writeln; 
end; 
procedure tryit(i:integer); 
var j:integer; 
begin 
  for j:=0 to 9 do 
    if not(j in ss) and ((num]<=num[j]) or 
    (num]>=num[j])) then 
    begin 
      ss:=ss+[j];a:=j;b:=j; 
      if i=10 then print else tryit(i+1); 
      ss:=ss-[j]; 
    end; 
end; 
begin 
  b[0]:=8; 
  t:=0; 
  tryit(1); 
end. 

总结：回溯法在算法中处于非常重要的地位，其算法有着其他算法不可替代的优点，希望大家能够通过以上四个实例加深对回溯法的印象。