当前位置:首页 >> 学科竞赛 >>

骑士周游问题



回专题模式 回学习阶段模式 【题目名称、来源】 骑士周游问题(经典题目 knight.pas) 【问题描述】 骑士周游问题 如下图所示,国际象棋棋盘上的马一步可以跳向八个方向,问:如果给出一个 n*m 的 棋盘,马从左上角开始跳,是否能够不重复的跳遍所有的格子。 输入:棋盘大小 n m 输出:n*m 个数,分 n 行 m 列,便利棋盘格子的顺序



源程序: 【所属专题】 【适合学习阶段】 【解题思路】 问题分析: 该问题是经典搜索问题 解答树: 2,3

1,1 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.


相关文章:
高斯的确是神一般的存在
Gauss 可以在六步以内解决骑士周游问题。 Gauss 同时给 Bertrand Russell 和自己理发。 Gauss 想喝果汁时,直接对橙子使用夹挤定理。 Gauss 唱完 “Aleph-Null ...
人工智能实验报告
实验要求采用 PROLOG 编程求解 8*8 骑士周游问题以及农夫、狼、羊、菜问 题。采用熟悉的高级语言编程实现“过河问题” 、 “九宫格”等问题的求解。 二、所用...
农夫过河和骑士周游(数据结构课程设计)
农夫过河和骑士周游(数据结构课程设计)_电脑基础知识_IT/计算机_专业资料。文档内容有实验要求: 1.1实验目的 1.2实验内容问题描述 1.3:实验输出要求 2:程序设计...
人工智能实验报告
实验结果 图一 图二 八骑士周游结果一 八骑士周游结果二 图三 农夫、狼、羊、菜问题结果 图四 四皇后的一个解 图五 下棋过程截图 六、讨论与结论通过本次...
数据结构经典代码(严蔚敏)
图的关键路径问题的算法*/ /* 背包问题的贪心法算法*/ /* 用动态规划法求组和数的算法*/ /* 用回溯法解决骑士周游问题的算法*/ /* 0/1 背包问题的回溯...
更多相关标签: