跳马程序和注解.docVIP

跳马程序及注解 by scp 跳马问题描述： 在5*5格的棋盘上，从（1,1）点出发，按日字跳马，要求不重复地跳经所有方格。求出符合要求的所有跳马方案。 输出前5个方案及总方案数。（用回溯法实现） 输出格式示例： 1 16 21 10 25 20 11 24 15 22 17 2 19 6 9 12 7 4 23 14 3 18 13 8 5 {参考程序及注解} var a:array[1..5,1..5] of integer; {记每一步走在棋盘的哪一格} b:array[1..5,1..5] of boolean; {棋盘的每一格有没有被走过} u,v:array[1..8] of integer; {8个方向上的x,y增量} i,j,num:integer; procedure print; {打印方案} var k,kk:integer; begin num:=num+1; {统计总方案} if num=5 then {打印出前5种方案} begin for k:=1 to 5 do {打印本次方案} begin for kk:=1 to 5 do write(a[k,kk]:5); writeln; end; end; end; procedure try(i,j,n:integer); {以每一格为阶段，在每一阶段中试遍8个方向} var k,x,y:integer; {这三个变量一定要定义局部变量} begin if n25 then begin print; exit;end ; {达到最大规模打印、统计方案} for k:=1 to 8 do {试遍8个方向} begin x:=i+u[k]; y:=j+v[k] ; {走此方向，得到的新坐标} if (x=5) and (x=1) and (y=5) and (y=1)and b[x,y] then {如果新坐标在棋盘上，并且这一格可以走} begin b[x,y]:=false; a[x,y]:=n; try(x,y,n+1); {从(x,y)去搜下一步该如何走} b[x,y]:=true; a[x,y]:=0; end; end; end; begin u[1]:=1; v[1]:=-2; {8个方向的x,y增量} u[2]:=2; v[2]:=-1; u[3]:=2; v[3]:=1; u[4]:=1; v[4]:=2; u[5]:=-1; v[5]:=2; u[6]:=-2; v[6]:=1; u[7]:=-2; v[7]:=-1; u[8]:=-1; v[8]:=-2; for i:=1 to 5 do {初始化} for j:=1 to 5 do begin a[i,j]:=0; b[i,j]:=true; end; a[1,1]:=1; b[1,1]:=false; {从(1,1)第一步开始走} try(1,1,2); {从(1,1)开始搜第2步该怎样走} writeln(num); {输出总方案(304)} end. 跳马问题与八皇后问题都属于典型的回溯法，回溯法有一种固定的思维与书写格式。