（……续上篇）

3  递归回溯算法

回溯算法因解决著名的“八皇后问题”^[1]而被广泛流传，其核心思想是：如果第n步无法求解，则回溯到第n-1步，求第n-1步的下一个解，然后再对第n步重新开始求解，而对第n-1步的求解与对第n步的求解完全一致；当第1步无法求解时，则全部求解结束，显然，这是一种递归的思想．本文的问题可以看做是搜索第n位的数字（从1到9依次尝试）；然后判断与前面已经搜索就绪的n-1位数字是否冲突，如果冲突，则继续搜索第n位的下一种可能（加1），如果下一种可能不存在（大于9），则回溯到第n-1位数字继续搜索，然后再重新（从1开始）搜索第n位数字；如果与前面的n-1位数字不冲突，则继续搜索第n+1位数字，直到完成全部9位数字的搜索．

下面的函数在数组r中判断第n位数字是否与前面n-1位数字冲突．

1. function ***(n:integer; var r:TArr):boolean;  
2. var  
3.   i:integer;  
4.   flag:boolean;  
5. begin 
6.   flag:= false;  
7.   i:= 1;  
8.   while (i < n) and not flag do  
9.   begin 
10.     flag:= r[i] = r[n];  
11.     inc(i);  
12.   end;  
13.   result:= flag;  
14. end; 

如果第n位数字与前面n-1位数字中任何一位相等，则函数***返回“真”，否则返回“假”．

下面的函数使用递归回溯算法在数组r中搜索前n位数字均不相同的排列．

1. function RS(n:integer; var r:TArr): boolean;  
2. begin 
3.   if n < 1 then 
4.     result:= false 
5.   else 
6.   begin 
7.     inc(r[n]);  
8.     if r[n] > 9 then 
9.     begin 
10.       r[n]:= 0;  
11.       if RS(n-1, r) then 
12.         result:= RS(n, r)  
13.       else 
14.         result:= false;  
15.     end 
16.     else 
17.       if ***(n, r) then 
18.         result:= RS(n, r)  
19.       else 
20.         result:= true;  
21.   end;  
22. end; 

如果前n位数字可以找到符合条件的排列，则函数RS返回“真”，否则返回“假”．

下面的过程初始化数据并调用递归回溯算法穷举集合{1, 2, 3,…,9}的所有排列．

1. procedure Equation(var r:TArr);  
2. var  
3.   i: integer;  
4. begin 
5.   for i:= 1 to 9 do  
6.     r[i]:= 0;  
7.   for i:= 1 to 8 do  
8.     RS(i, r);  
9.   repeat  
10.     TestArr(r);  
11.   until not RS(9, r);  
12. end; 

过程Equation首先搜索第1位到第8位数字的排列，然后在此基础上不断搜索第9位数字，每搜索成功一组，将其送入函数TestArr进行判定并输出，直到搜索结束，即穷举了所有排列．

（未完待续……）

本文转自 BlackAlpha 51CTO博客，原文链接：http://blog.51cto.com/mengliao/465335，如需转载请自行联系原作者