回溯算法搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。
回溯是搜索算法中的一种控制策略。
它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。
如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。
按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。
递归回溯法算法框架[一]procedure Try(k:integer);beginfor i:=1 to 算符种数 Doif 满足条件 thenbegin保存结果if 到目的地 then 输出解else Try(k+1);恢复：保存结果之前的状态{回溯一步}end;end;递归回溯法算法框架[二]procedure Try(k:integer);beginif 到目的地 then 输出解elsefor i:=1 to 算符种数 Doif 满足条件 thenbegin保存结果Try(k+1);end;end;例 1：素数环：把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。
【算法分析】非常明显，这是一道回溯的题目。
从1 开始，每个空位有 20（19）种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。
第 20个数还要判断和第1个数的和是否素数。
〖算法流程〗1、数据初始化； 2、递归填数：判断第J种可能是否合法；A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；B、如果不合法：选择下一种可能；【参考程序】program z74;框架[一]var a:array[0..20]of byte;b:array[0..20]of boolean;total:integer;function pd(x,y:byte):boolean;var k,i:byte;begink:=2; i:=x+y; pd:=false;while (k<=trunc(sqrt(i)))and(i mod k<>0) do inc(k);if k>trunc(sqrt(i)) then pd:=true;end;procedure print;var j:byte;begininc(total);write('<',total,'>:');for j:=1 to 20 do write(a[j],' ');writeln;end;procedure try(t:byte);var i:byte;beginfor i:=1 to 20 doif pd(a[t-1],i)and b[i] thenbegina[t]:=i; b[i]:=false;if t=20 then begin if pd(a[20],a[1]) then print;endb[i]:=true;end;end;BEGINfillchar(b,sizeof(b),#1);total:=0;try(1);write('total:',total);END.通过观察，我们可以发现实现回溯算法的特性：在解决过程中首先必须要先为问题定义一个解的空间．这个空间必须包含问题的一个解。
在搜索路的同时也就产生了新的解空间。
在搜索期间的任何时刻．仅保留从起始点到当前点的路径。
例 2：设有 n 个整数的集合｛1,2,…,n｝，从中取出任意 r 个数进行排列（r<n），试列出所有的排列。
解法一：program it15; 框架[一]type se=set of 1..100;VAR s:se;n,r,num:integer;b:array [1..100] of integer;PROCEDURE print;var i:integer;beginnum:=num+1;for i:=1 to r dowrite(b[i]:3);writeln;end;PROCEDURE try(k:integer);VAR i:integer;beginfor i:=1 to n doif i in s thenbeginb[k]:=i;s:=s-[i];if k=r then prints:=s+[i];end;end;BEGINwrite('Input n,r:');readln(n,r); s:=[1..n];num:=0;try(1);writeln('number=',num);END.解法二：program it15; 框架[二]type se=set of 1..100;VARs:se;n,r,num,k:integer;b:array [1..100] of integer;PROCEDURE print;var i:integer;beginnum:=num+1;for i:=1 to r dowrite(b[i]:3);writeln;end;PROCEDURE try(s:se;k:integer); VAR i:integer;beginif k>r then printelsefor i:=1 to n doif i in s thenbeginb[k]:=i;end;end;BEGINwrite('Input n,r:');readln(n,r);s:=[1..n];num:=0;try(s,1);writeln('number=',num);readln;END.例3、任何一个大于1的自然数n,总可以拆分成若干个小于n 的自然数之和. 当n=7共14种拆分方法：7=1+1+1+1+1+1+17=1+1+1+1+1+27=1+1+1+1+37=1+1+1+2+27=1+1+1+47=1+1+2+37=1+1+57=1+2+2+27=1+2+47=1+3+37=1+67=2+2+37=2+57=3+4total=14{参考程序}program jjj;var a:array[0..100]of integer;n,t,total:integer;procedure print(t:integer);var i:integer;beginwrite(n,'=');for i:=1 to t-1 do write(a[i],'+');writeln(a[t]);total:=total+1;end;procedure try(s,t:integer);var i:integer;beginfor i:=1 to s doif (a[t-1]<=i)and(i<n) thenbegina[t]:=i;s:=s-a[t];if s=0 then print(t)else try(s,t+1);s:=s+a[t];end;end;beginreadln(n);try(n,1);writeln('total=',total);readln;end.例 4、八皇后问题：要在国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃。
（提示：皇后能吃同一行、同一列、同一对角线的任意棋子。
）放置第i个皇后的算法为：procedure Try(i)；beginfor 第i 个皇后的位置=1 to 8 do；if 安全 thenbegin放置第 i个皇后；对放置皇后的位置进行标记；if i=8 then 输出else Try(i+1)；{放置第 i+1个皇后}对放置皇后的位置释放标记，尝试下一个位置是否可行；end；end；【算法分析】显然问题的键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在／斜线上的行列值之和相同；如果同在＼斜线上的行列值之差相同；如果斜线不分方向，则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同。
从下图可验证：对于一组布局我们可以用一个一维数组来表示：A:ARRAY [1..8] OF INTEGER;A[I]的下标I 表示第I个皇后在棋盘的第I行，A[I]的内容表示在第 I行的第 A[I]列，例如：A[3]=5就表示第3个皇后在第3行的第5列。
在这种方式下，要表示两个皇后 I和 J不在同一列或斜线上的条件可以描述为：A[I]<>A[J] AND ABS(I-J)<>ABS(A[I]-A[J]){I和 J分别表示两个皇后的行号}考虑每行有且仅有一个皇后，设一维数组A[1..8]表示皇后的放置：第i行皇后放在第j列，用A[i]＝j来表示，即下标是行数，内容是列数。
判断皇后是否安全，即检查同一列、同一对角线是否已有皇后，建立标志数组b[1..8]控制同一列只能有一个皇后，若两皇后在同一对角线上，则其行列坐标之和或行列坐标之差相等，故亦可建立标志数组c[1..16]、d[-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 i:byte;beginfor i:=1 to 8 do write(a[i]:4);inc(sum);writeln(' sum=',sum);end;procedure try(t:byte);var j:byte;beginfor j:=1 to 8 do{每个皇后都有8种可能位置}if b[j] and c[t+j] and d[t-j] then {寻找放置皇后的位置}begin {放置皇后,建立相应标志值}a[t]:=j;{摆放皇后}b[j]:=false;{宣布占领第j列}c[t+j]:=false;{占领两个对角线}d[t-j]:=false;if t=8 then pr {8个皇后都放置好,输出}else try(t+1);{继续递归放置下一个皇后}b[j]:=true; {递归返回即为回溯一步,当前皇后退出}c[t+j]:=true;d[t-j]:=true;end;end;BEGINfillchar(b,sizeof(b),#1);fillchar(c,sizeof(c),#1);fillchar(d,sizeof(d),#1);sum:=0;try(1);{从第1个皇后开始放置}END.例 5：马的遍历中国象棋半张棋盘如图 4（a）所示。