马的遍历 #

1. 马的遍历问题的介绍
2. 马的遍历问题的算法分析
3. 马的遍历问题代码实现

马的遍历问题的介绍 #

中国象棋的半张棋盘如下图所示。马自左下角往右上角跳。如果规定只许往右跳，不许往左跳。那么从棋盘左下角跳到棋盘右上角的路线有哪些？比如下图所示的一种跳行路线，打印格式为:
(0,0)->(1,2)->(3,3)->(4,1)->(5,3)->(7,2)->(8,4)

马的遍历问题的算法分析 #

马的遍历问题与迷宫问题类似，也是典型的回溯问题，因为马只能向右跳，所以马每次的移动轨迹只可能又如下四步(x表示横坐标，也表示纵坐标):
(x,y)->(x+1,y+2)
(x,y)->(x+1,y-1)
(x,y)->(x+2,y+1)
(x,y)->(x+2,y-1)
第一步:马从棋盘(0,0)处选择四条路中的一个跳格。
第二步:判断马是否还在棋盘上(0=<x<=8,0=<y<=4)，如果是保存当前的选择，选择下一步跳格，如果不是继续从四条路中选择一个跳格，直到到达顶点(8,4)

马的遍历问题的代码实现 #

res=[[0,0]]#出发点设为零,res[1]代表第一次选择的结果，以此类推
d=[[1,2],[1,-2],[2,1],[2,-1]]#马的四种移动轨迹
def myprint(r):#按要求打印结果
    for i in r:
        print(i,'->',sep='',end='')
    print('\b\b')
def dfs(step):
    if res[step-1]==[8,4]:#如果上一步选择已经到达终点打印结果
        myprint(res)
    for i in d:
        if(res[step-1][0]+i[0]>=0 and res[step-1][0]+i[0]<=8\
        and res[step-1][1]+i[1]>=0 and res[step-1][1]+i[1]<=4):#判断当前步骤的选择是否还在棋盘内
            [x,y]=[res[step-1][0]+i[0],res[step-1][1]+i[1]]
            res.append([x,y])#如果在保留结果
            dfs(step+1)#寻找下一步
            res.pop()#撤销当前的选择
dfs(1)#从第一步开始寻找马的路径

小结 #

习题 #

1. 如果在上述问题中，因为一些原因马不能跳到棋盘坐标的(4,3)，试求解所有的路径
2. 如果想在6步之内跳到终点，求解所有的路径