计算机竞赛的回溯算法构造

程军康
摘要
本文介绍了在青少年计算机程序设计（信息学）竞赛中常用的算法---回溯算法，并介绍了在PASCAL语言中回溯算法的一般构造
关键词：计算机竞赛，回溯算法，PASCAL语言，算法构造
1、问题的提出
在青少年计算机程序设计（信息学）竞赛中我们经常碰到这样的题目：要求计算机求解：“关于……有多少种解法?”、“列出……所有可能的情形”’等，一般我们可以考虑使用搜索回溯算法。
搜索回溯算法是一种深度优先搜索的搜索算法，搜索就是全面访问所有可能情况，搜索回溯算法实质上是一种枚举法，它可以被描述成一种组织得井井有条的穷举探索法，这种搜索算法通常适合解决必须仔细地考察具有大量的、但是数目仍是有限的一类问题的解。
搜索回溯算法最典型的例子可以说是第三届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题（高中组）的第三题“骑士游历”问题
骑士游历:
设有一个n*m的棋盘(2<=n<=50,2<=m<=50),如下图,在棋盘上任一点有一个中国象棋马,

马走的规则为:
1.马走日字 2.马只能向右走
即如下图所示:

任务:当N,M 输入之后,找出一条从左下角到右上角的路径.
例如:输入 N=4,M=4

输出:路径的格式:(1,1)->(2,3)->(4,4)
若不存在路径,则输出"no"
任务:当N,M 给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终点的所有路径的数目.
例如:(N=10,M=10),(1,5)(起点),(3,5)(终点)

输出:2(即由(1,5)到(3,5)共有2条路径)
输入格式:n,m,x1,y1,x2,y2(分别表示n,m,起点坐标,终点坐标)
输出格式:路径数目(若不存在从起点到终点的路径,输出)
以其任务为例，简化为N=9，M=5，如图：

将马能走的四个方向设为K=1、、、4，从（，）出发，要到（，）去，这里（，）是起点，（8，）是终点，马试探前行，走第一方向K=1，所以第一步后到（2，），再走第一方向K=1，第二步后到（，），第三步还是走第一方向K=1，到达（，），已经出了边界，所以试探第二个方向，K=2，到达（，），还是出了边界，试探第三个方向，K=3，到达（，），没有出界，继续向前，得到条路径（1，）--（，）--（，）--（，）--（，）--（，），从（，）出发的个方向都不能前进，所以说（9，）是错误的点，回溯到（，），因为刚才从（，）出发的是第三方向，现在K增，试探从（，）出发的第四个方向，到（8，），再到（，），最后得到（，）--（，3）--（，）--（，）--（，）--（8，）--（，）正确的路径（即正确解）。
搜索回溯算法的基本思路可以这样描述：若已有满足约束条件的部分解，不妨设为(X1,X2,……Xi)，i 回溯算法的基本思路不复杂，但在计算机程序设计（信息学）竞赛实际构造PASCAL程序，由于竞赛时间的限制，学生往往出错较多，本文通过几个实际例子，说明回溯算法在PASCAL语言中的一般构造方法。
2、问题的解决
例：骑士游历任务，简化为起点（，），终点（，）
变量说明如下：
x0,y0是二个记前进方向的数组，其中x0[1]:=1;y0[1]:=2;x0[2]:=2;y0[2]:=1;x0[3]:=2;y0[3]:=-1;x0[4]:=1;y0[4]:=-2;
S数组是每一步走的方向
N是已经走的步数
XS，YS是是试探走后的位置
X，Y是实际走后的位置
K取、、、，表示四个走的方向，开始取0
FLAG是个标志，表示是否可以结束
程序算法描述如下：
K增加，即走一个方向
K>4，即当前方向已经全部走完，仍不满足，往回退一步（即回溯，如已回溯到N=0，则表示回溯结束，FLAG=FALSE）
试探当前K的走法（XS，YS增加）
如XS，YS没有到达边界，则让X，Y记XS，YS，并K=0，N增，S（N）记方向K
如XS，YS到达边界，则输出
转（）循环
实际程序中写了二个过程其中procedure pred; 回退一步，表示回溯过程；procedure out;输出过程，用于输出一条可以走的路径。
程序如下：
program aaa(input,output);
var x0,y0:array[1..4] of integer;
s:array[1..100] of integer;
n,x,y,xs,ys,k:integer;
flag:boolean;

procedure pred;
begin
x:=x-x0[s[n]];y:=y-y0[s[n]];
k:=s[n];
n:=n-1;
if n<0 then flag:=false;
k:=k+1;
end;

procedure out;
var n0,xl,yl,p:integer;
begin
{for n0:=1 to n do writeln(a[n0]);}
n0:=n;xl:=0;yl:=0;p:=1;
while p<=n+1 do
begin
write('(',xl:3,yl:3,')');xl:=xl+x0[s[p]];yl:=yl+y0[s[p]];
p:=p+1;
end;
writeln;
pred;
end;

begin
n:=0;x:=0;y:=0;flag:=true;
x0[1]:=1;y0[1]:=2;x0[2]:=2;y0[2]:=1; x0[3]:=2;y0[3]:=-1;x0[4]:=1;y0[4]:=-2;
k:=0;
while flag do
begin
repeat
k:=k+1;
if k>4 then pred;
until k<=4;
xs:=x+x0[k];ys:=y+y0[k];
if (xs>=0) and (xs<=8) and (ys>=0) and (ys<=4) then
begin x:=xs;y:=ys;n:=n+1;s[n]:=k;k:=0;end;
if (x=8) and (y=4) then out;
end;
readln;
end.

例打印到N的自然数中任何M个自然数的所有组合（M 分析：当M比较小时，可以直接利用多重循环来解决，但M较大时，这种方法就显得无能为力了．为了打印出所有组合，先对每一组合的排列作一个限制，规定每一组合中前面位置上的表示总是小于后续位置上的数，这样，对于从左至右的第i个数，可推算出该位置上的最大数为N-M+l。
算法说明：
1、A（M）存放某种组合各位上的数字，把123……M作为第一个组合
2、把最末位(第m位)数字A(M)逐次加，如果达到N，就退回至第m-1位，如果第m-1位上的数也已达到其最大值n-1，再退至第m-2位。
3、将当前处理的第T位( 4．返回，重复执行，直至每位已达到其最大值
程序如下：
program aaa;
var n,m,i,j,t:integer;
a:array [1..100] of integer;
flag:boolean;

procedure out;
begin
for i:=1 to m do write(a:3);
writeln;
end;

procedure pred;
begin
t:=t-1;
if t=0 then flag:=false;
end;

begin
writeln('input n,m:');readln(n,m);
flag:=true;
for i:=1 to m do a:=i;
t:=m;
while flag do
begin
if t=m then out;
if a[t] begin a[t]:=a[t]+1;
for i:=t+1 to m do a:=a[t]+i-t;
t:=m;
end else pred;
end;
end.

例 在N*M的棋盘中放置K只“皇后”（1<=K<=N，M）,使这K只间不能相互攻击，找出所有可能的放法。
程序如下：
program aaa(input,output);
var a:array[1..100,1..100] of integer;
b:array[1..100] of integer;
x,y:array[1..100] of integer;
i,j,k,n,m,n0,x0,y0:integer;
flag:boolean;

procedure pred;
begin
for i:=1 to n do a[x[k],i]:=0;
for i:=1 to m do a[i,y[k]]:=0;
for i:=1 to m do for j:=1 to n do
if (y0-j=x0-i) or (y0+x0=j+i) then a[i,j]:=0;
k:=k-1; if k=0 then flag:=false;
end;

procedure out;
begin
for i:=1 to n0 do writeln(x,y);
pred;
end;

procedure out1;
begin
for i:=1 to m do begin for j:=1 to n do write(a[i,j]);writeln;end;
writeln;readln;
end;

begin
writeln('input n,m,n0:');readln(n,m,n0);
for i:=1 to m do for j:=1 to n do a[i,j]:=0;