第5 章
回 溯 法
5.1 回溯法的算法框架
回溯法有通用的解题法之称,是程序设计中常用的一种算法设计技术。它不是按照
某种公式或确定的法则来求问题的解,而是通过试探和纠正错误的策略,找到问题的解。
这种方法一般是从一个原始状态出发,通过若干步试探,最后达到目标状态并终止。
从理论上来说,回溯法就是在一棵搜索树中从根结点出发,找到一条达到满足某条件
的子结点的路径。在搜索过程中,对于每一个中间结点,它的位置以及向下搜索过程是相
似的,因此完全可以用递归来处理。典型的例子有著名的8皇后问题等。
5.1.1 明确定义问题的解空间
通常将问题的解空间组织成树或图的形式,用回溯法求解时常遇到的两类典型的解
空间树为子集树和排列树。
例5-1 n=3时的0-1背包问题的解空间树(子集树)。
0-1背包的解空间可以用完全二叉树表示,如图5-1所示,其中有8个叶结点,对应的
解分别为{0,0,0}、{0,0,1}、{0,1,0}、{0,1,1}、{1,0,0}、{1,0,1}、{1,1,0}、{1,1,1}。
图5-1 0-1背包问题的解空间树
设w=[16,15,15],p=[45,25,25],c=30,以深度优先的方式系统地搜索问题的解: 
从根结点出发,A→ B→D→ H→…… 
子集树通常有2n 个叶结点,其结点总个数为2n+1-1。遍历子集树的任何算法均需
Ω(2n)。
例5-2 旅行商问题的解空间树(排列树)。

1 08 算法分析与设计 
给定一个有n个顶点的带权图G,如图5-2所示,要在G中找出一条有最小费用(权) 
的周游路线。
图5-3树中结点的编号按深度优先搜索的顺序给出,树中有6个叶结点,表示周游路
线有6条。
图5-2 4个顶点的带权图G 
图5-3 旅行商问题的解空间树
排列树通常有n!个叶结点,遍历子集树的任何算法均需Ω(n!)。
5.1.2 运用回溯法解题的步骤
运用回溯法解题的步骤如下: 
(1)针对所给问题,定义问题的空间解; 
(2)确定易于搜索的解空间结构; 
(3)以深度优先的方式搜索解空间,并在搜索过程中用剪枝函数(约束函数constrain(t) 
或限界函数bound(t))避免无效搜索。
5.1.3 回溯法的算法框架
1.递归回溯的算法框架 
递归回溯的算法框架如下: 
void backtrack(int t) 
{ 
if (t>n) 
output(x); /*搜索到叶结点,输出*/ 
else

第5 章　回溯法1 09 
for (i=f(n,t); i<=g(n,t); i++) 
{ 
x[t]=h(i); 
if (constrain(t) && bound(t)) 
backtrack(t+1); 
} 
} 
注意:调用一次backtrack(1)可完成整个回溯搜索过程。其中, 
.t表示递归深度,即当前扩展结点的深度; 
. n表示解空间树的高度; 
.f(n,t)表示当前扩展结点处未搜索过的子树的起始编号; 
. g(n,t)表示当前扩展结点处未搜索过的子树的终止编号; 
. h(i)表示在当前扩展结点处x[t]的第i个可选值; 
.constrain(t)表示在当前扩展结点处的约束函数; 
. bound(t)表示在当前扩展结点处的限界函数; 
. backtrack(t+1)表示对其相应子树作进一步搜索。
2.迭代回溯的算法框架
如果采用树的非递归深度优先遍历,可将回溯法表示为一个非递归的迭代过程如下: 
void iterativebacktrack(int t) 
{ 
int t=1; 
while(t>0) 
{ 
if (f(n,t)<=g(n,t)) 
for (i=f(n,t);i<=g(n,t);i++) 
{ 
x[t]=h(i); 
if (constrain(t) && bound(t)) 
{ 
if (solution(t)) 
output(x); /*搜索到叶结点,输出*/ 
else t++; 
} 
} 
else 
t--; 
} 
}

1 10 算法分析与设计
注意:算法的while循环结束后可完成整个回溯搜索过程。其中, 
.t表示递归深度,即当前扩展结点的深度; 
. n表示解空间树的高度; 
.f(n,t)表示当前扩展结点处未搜索过的子树的起始编号; 
. g(n,t)表示当前扩展结点处未搜索过的子树的终止编号; 
. h(i)表示在当前扩展结点处x[t]的第i个可选值; 
.constrain(t)表示在当前扩展结点处的约束函数; 
. bound(t)表示在当前扩展结点处的限界函数; 
.solution(t)表示在当前扩展结点处是否已得到问题的一个可行解。
5.2 n皇后问题
5.2.1 问题描述 
n皇后问题要求一个n×n格的棋盘上放置n个皇后,使得她们不能相吃。按照国际
象棋的规则,一个皇后可以吃掉与她处于同一行、同一列或同一对角线上的任何棋子,因
此每一行只能摆放一个皇后。n皇后问题等价于要求在一个n×n格的棋盘上放置n个
皇后,使得任何两个皇后不能放在同一行、同一列或同一对角线上。
5.2.2 算法设计
对于n皇后问题,皇后的位置用一个一维数组x[1..n]来存放,其中x[i]表示第i行
皇后放在第x[i]列。下面主要是判断皇后是否安全的问题。
(1)用一维数组x[1..n]来表示已经解决了不在同一行的问题; 
(2)对于列,当j!=k时,要求x[j]!=x[k]; 
(3)对于左上右下的对角线的每个元素有相同的“行-列”值;对于左下右上的对角
线有相同的“行+列”值。若两个皇后分别占有(j,x[j])和(k,x[k])两个位置,则两个皇
后在同一对角线上的条件是:j-x[j]=k-x[k]或j+x[j]=k+x[k],即j-k=x[j]- 
x[k]或j-k=x[k]-x[j]。因此,同一对角线上的条件可归纳为|j-k|=|x[k]-x[j]|。
判断是否可放置一个新皇后的算法如下: 
int place(int k) 
{ 
int i; 
for (i=1;i<k;i++) 
if (x[i]==x[k]|| abs(x[i]-x[k])==abs(i-k)) 
return(0); 
return(1); 
}

第5 章　回溯法1 11 
5.2.3 算法实现
下面给出n皇后问题的递归回溯算法的实现代码,有兴趣的读者可以自行调试完成
n皇后问题的迭代回溯算法的实现。 
void backtrack(int t) 
{ 
int i,xx; 
if (t>n) 
for (i=1;i<=n;i++) 
printf("%d",x[i]); 
else 
for (i=0;i<n;i++) 
{ 
x[t]=i; 
if (t==1 && x[t]>=n/2 ) 
break; 
if (place(t)==1) 
backtrack(t+1); 
} 
} 
5.2.4 8 皇后问题的不等效解分析与实现
1.8皇后问题的不等效解 
会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。
如何在8×8的棋盘上放置八个皇后,使它们不能相吃,这就是古老而著名的8皇后问题。
显然,每行只能摆放一个皇后,问题转换为求每行上皇后所在的列。
该问题是19世纪著名的数学家高斯于1850年提出的,当时高斯认为有76种方案。
1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法
解出92种结果,如图5-4所示,现已证明了结果的正确性。在数学游戏的书常讨论到8 
皇后问题的对称解。在计算机文献方面,PeterNaur在1972 年讲解了对称的问题, 
RodneyW.Topor在1982年用群论讨论过并有PASCAL程序。N.Wirth在其名著《算
法+数据结构=程序》中编程求得8皇后问题的92个解之后说:“实际上只有12个真正
不同的解;我们的程序不能识别对称的解。”随后列出这12 个真正不同的解(即不等效
解)。下面以图示的方式总结规律并设计一个有效的求解算法,并用C程序加以识别,N. 
Wirth那句“我们的程序不能识别对称的解”已成过去式。
2.8皇后问题的不等效解分析
对于n皇后问题,可以发现一些解是另一些解的简单反射或旋转的结果。比如,n= 
4时的两个解(1,3,0,2)和(2,0,3,1)在反射意义下是等效的。n=6时,其4个解等效情

1 12 算法分析与设计
图5-4 8皇后问题的12个不等效解(92个解中最左列)及对应的等效解(同行右侧) 
况如图5-5所示。
图5-5 6皇后的1个不等效解及其3个等效解
当n=8时,共有92个解,其中有12个不等效解,如图5-4所示。图5-6中除第10个
不等效解演变出3个等效解之外,其他11个不等效解经棋盘旋转90°、180°、270°及简单
反射后,各可演变出7个等效解,如图5-7所示。图5-5、图5-6和图5-7分别表示了8皇
后棋子的一个布局,这3个图中的多个解只不过是由于看棋盘的角度不同而导致的。
图5-6 8皇后第10个不等效解24170635及其3个等效解

第 
5 
章　回溯法

113
图5-
7 8 
皇后第1个不等效解04752613 
及其7个等效解

对于图5-5、图5-6和图5-7不等效解及其所产生的等效解之间的关系,可以发现构
成简单反射关系的解正好是一半,只要限制第一个皇后所在的列x[0]<n/2即可。而构
成旋转关系的解有两种情况,一种只需左旋90°,另一种需依次左旋90°、180°、270°。进一
步考察属第一种情况的如图5-5和图5-6所示的不等效解135024 和24170635,发现其满
足x[n1i]n1, ° 左旋270的解与左旋

i]+x[--=-因此左旋180的解与原不等效解一致,° 
90°的解一致,要给予剔除。另外,当n=4时,只有一个不等效解及其构成简单反射关系
的一个等效解,不必经过旋转,否则将产生重复的两个解。通过以上分析,可由一个不等
效解构造出与其等效的其他所有解。

顺便说明一下,不等效解与其构造出的等效解之间,并非仅仅通过对称(或称简单反
射)可找到,所以称它们为等效解更合适,而有的文献中称为对称解。

3.n皇后问题不等效解的算法实现思路
皇后问题是回溯算法的典型例题,许多算法教材中都给出了解n皇后问题的回溯算
法,这里进一步讨论的是如何在产生n皇后问题不等效解的基础上,通过不等效解构造出
与其等效的其他所有解。输出皇后问题不等效解的算法思路如下: 

步骤1. 生成的第一个解必是不等效解,令count=1,用于标记不等效解的数目,并存
储此解到二维数组b中,二维数组b的第一个下标为count,第二个下标为8个皇后所在
的列。另外,用求等效解的函数dx(见后面程序)生成第一个解的其他7个等效解,并用
m标记已生成8个解,同时存储此8个解到二维数组c中,二维数组c的第一个下标为
m,第二个下标为8个皇后所在的列。

步骤2. 生成第二个解开始,每一个解必须与二维数组c中已存的解进行8个分量的
比较,判别其是新的不等效解还是重复出现的等效解,用test函数实现。若是新的不等
效解,重复步骤1,否则,仅标记sum=sum+1 。

下面给出按上述算法思想所实现的求皇后问题不等效解的C程序。n=8的运行结
果如图5-4所示;当n=4、6、10 时的运行结果如图5-8所示。当n>8 时,解的数目较大, 
程序中所用数组要调大,以n=10 为例,得到的不等效解为102 个。


1 14 算法分析与设计
图5-8 皇后问题(n=4、6、10)的不等效解及对应的等效解
算法实现程序如下: 
#define N 8 
int x[100]={0}; 
int a[N][N],b[2*N][N],c[100][N],row=0; 
static int sum=0,count=0,m=1; 
void left90(int x[]) /*产生左旋90°的等效解*/ 
{ 
int i; 
for (i=0;i<N;i++) 
a[row][N-1-x[i]]=i; 
row++; 
}
void left180(int x[]) /*产生左旋180°的等效解*/ 
{ 
int i; 
for (i=0;i<N;i++) 
a[row][N-1-i]=N-1-x[i]; 
row++; 
}
void left270(int x[]) /*产生左旋90°的等效解*/ 
{ 
int i; 
for (i=0;i<N;i++) 
a[row][x[i]]=N-1-i; 
row++; 
}
void store(int x[],int count) /*实现存储不等效解*/ 
{ 
int i; 
for(i=0;i<N;i++)

第5 章　回溯法1 15 
b[count][i]=x[i]; 
}
void dx(int x[]) /*用于构造等效解的函数dx*/ 
{ 
int i,j,flag=0; 
for (i=0;i<N;i++) /*临时存储用于构造等效解的原不等效解*/ 
a[row][i]=x[i]; 
row++; 
for (i=0;i<N/2;i++) /*判断左旋次数*/ 
if (x[i]+x[N-1-i]!=N-1) 
{ 
flag=1; 
break; 
} 
if (N>4&&flag==0) 
left90(x); 
else if (flag) 
{ 
left90(x); 
left180(x); 
left270(x); 
} 
for (i=0;i<row;i++) /*产生简单反射的等效解*/ 
for (j=0;j<N;j++) 
a[row+i][N-1-j]=a[i][j]; 
printf("\n"); 
for (i=0;i<row*2;i++) /*输出该不等效解及其产生的所有等效解*/ 
{ 
printf(" "); 
for (j=0;j<N;j++) 
printf("%d",c[m][j]=a[i][j]); 
m++; 
} 
}
int test(int x[]) /*测试是否为不等效解*/ 
{ 
int i,j; 
for (i=1;i<=m;i++) 
{ 
for (j=0;j<N;j++) 
if (c[i][j]!=x[j])

1 16 算法分析与设计 
break; 
if (j>=N) 
break; 
} 
if (i>m) 
return(1); 
else 
return(0); 
}
int place(int k) /*所放位置是否有冲突*/ 
{ 
int i; 
for (i=0;i<k;i++) 
if (x[i]==x[k]||abs(x[i]-x[k])==abs(i-k)) 
return(0); 
return(1); 
}
void backtrack(int t) /*回溯求解*/ 
{ 
int i,xx; 
if (t>N-1) 
{ 
sum=sum+1; 
if (sum==1||test(x)) 
{ 
count++; 
store(x,count); 
row=0; 
dx(x); 
} 
if (sum==48) getch(); 
} 
else for (i=0;i<N;i++) 
{ 
x[t]=i; 
if (t==0&&x[t]>=N/2 ) 
break; 
if (place(t)==1) 
backtrack(t+1); 
} 
}