解骑士巡游问题
一、 设计任务与目标
国际象棋中马采用 日”字走法,对棋盘上马所在的结点,一步内到达的结 点最多
有八个,即假设马所在点的坐标为(
i
,
j
),那么其它八个结点的坐标为
(
i+1,j+2
)
,
(
i+2,j+1
)
,
(
i+2,j-1
)
,
(
i+1,j-2
),(
i-1,j-2
)
,
(
i-2,j-1
)
,
(
i-2,j+1
)
,
(
i-1,j+2
)把这些点看作马所在点的邻接点,所以可以采用类似图的深度优先遍 历,以马
所在点为初始点对整个棋盘进行遍历。然后按遍历的顺序输出结点
棋盘的规格限制为
8*8
,输入数据为起始点的位置(
0-7
)。输出数据为可以 遍历成
功的若干方案(本程序设置为至多八种)。
二、 方案设计与论证
解决马的遍历问题,可以用一个二维数组
board
叩来表示棋盘,一开始用
来存放步骤号,若走过了则把它赋值为
1
。另对马的
8
种可能走法设定一个顺序, 如当前
位置在棋盘的(
i
,
j
)方格,下一个可能的位置依次为(
i+2
,
j+1
)、(
i+1
,
j+2
)、
(
i-1
,
j+2
)、(
i-2
,
j+1
)、(
i-2
,
j-1
)、(
i-1
,
j-2
)、(
i+1
,
j-2
)、(
i+2
,
j-
1
), 实际可以走的位置尽限于还未走过的和不越出边界的那些位置。为便于程序的同
意处理,可以引入两个数组
mover]]
、
movec[]
,分别存储各种可能走法对当前位 置的纵横
增量。整形变量
step
存放步骤号,
start
存放遍历次数,在
numable
函数 和
number
函数
中的语句
k=(i+start)%N;
中是用于定位,保证不会超过棋盘范围和 八次遍历都不会走同
样的路径
test
存放遍历成功次数。
在
8
X
8
方格的棋盘上,从任意指定的方格出发,为马寻找一条走遍棋盘每 一格并且
只经过一次的一条路径。
评论0
最新资源