骑士周游问题

骑士周游问题（经典题目knight.pas） 【问题描述】 骑士周游问题

如下图所示，国际象棋棋盘上的马一步可以跳向八个方向，问：如果给出一个n*m的棋盘，马从左上角开始跳，是否能够不重复的跳遍所有的格子。 输入：棋盘大小n m

输出：n*m个数，分n行m列，便利棋盘格子的顺序 马 源程序：

【所属专题】

【适合学习阶段】

【解题思路】 问题分析：

该问题是经典搜索问题 1，1 解答树：

2，3 3，2

1，5 3，5 4，4

3，4

存储结构： const

direct:array[1..8,1..2] of integer=

((-2,1),(-1,2),(2,1),(1,2),(2,-1),(1,-2),(-1,-2),(-2,-1));

{马可以跳向八个方向的相对位移，使用常量数组可以将规则统一} Var

a:array[1..10,1..10] of integer;{使用数组作为棋盘的存储，如果某一格子没有走过值为0，否则为步数}

【测试数据】

【源程序】

program qishi;{Qi shi zhou you wen ti} const

direct:array[1..8,1..2] of integer=

((-2,1),(-1,2),(2,1),(1,2),(2,-1),(1,-2),(-1,-2),(-2,-1));

{马可以跳向八个方向的相对位移，使用常量数组可以将规则统一} var n,m,x,y:integer; i,j,count:integer;

a:array[1..10,1..10] of integer;

procedure tiao(step,x,y:integer);{递归过程实现回溯}

var r,i,j,k,l:integer;{r是规则号，i,j是按照r规则跳后的新位置} begin

for r:=1 to 8 do begin

i:=x+direct[r,1];j:=y+direct[r,2];{求新位置}

if (i>=1)and(i<=n)and(j<=m)and(j>=1) then {如果新位置合法} if a[i,j]=0 then begin a[i,j]:=step;

if step=n*m then begin{如果到达终点则打印} for k:=1 to n do begin

for l:=1 to m do write(a[k,l]:3); writeln; end;

close(output); halt; end

else tiao(step+1,i,j);{如果没有到终点，跳下一步} a[i,j]:=0;{回溯} end; end; end; begin

assign(input,'qishi.in'); reset(input); readln(n,m); {init}

assign(output,'qishi.out'); rewrite(output); for i:=1 to n do

for j:=1 to m do a[i,j]:=0; {初始化数组} a[1,1]:=1; tiao(2,1,1);

writeln('Impossible'); close(output); end.