马踏棋盘问题又称Knight Tour Problem，指的是在一个n*n棋盘上，找出一条路径，可以使马不重复地踏遍整个棋盘的格子。对于每一步，最多有八个方向可以走。
深度优先（DFS）
最自然的想法基于深度优先算法，即从初始位置开始，在可走的方向中选出一个方向作为下一步，直到找不到可走的路径时，进行回溯，最终找出一条路径。如下图所示：
图中的蓝色箭头表示马的前进，红色箭头表示遇到死路时进行回溯，直到走了64步时就说明找到了一条路径
Python 实现（Python Implementation）
API
class KnightTour
BDsize = 0 ## 表示棋盘的边长
board = [[0]*BDsize for _ in range(BDsize)] ## 表示棋盘，0代表未踩过，1代表踩过
pathboard = [[0]*BDsize for _ in range(BDsize)] ## 一个用来显示路径的棋盘，每个位置上的值表示它在路径上的顺序
start_pos = [1,1] ## 表示起始点的坐标，坐标从1开始
eight_dire = [[2,1],[2,-1],[-2,1],[-2,-1], ## 定义8个方向的坐标变化
[1,2],[1,-2],[-1,2],[-1,-2]]
def __init__(self, bd_size, s_pos) ## 构造函数
def FindMoves(self, cur_pos) ## 找出当前位置的下一步可能方向
def searchNext(self, cur_pos,cnt) ## 从当前位置开始，递归地找出路径
def tour(self) ## 调用SearchNext计算出起始位置路径，并打印出来
def printBD(self, board) ## 美观地打印出棋盘
FindMoves 找出下一步的可能方向
我们先找出一个点的下一步的所有方向的坐标（8个），然后再进行筛选，去除那些在棋盘外的和已经踏过的。
def FindMoves(self, cur_pos):
## 所有八个方向
moves = [[x + y for x,y in zip(cur_pos,dire)] for dire in self.eight_dire]
## 八个方向中下一步可以走的方向
valid_moves = [move for move in moves if 0<move[0]<self.BDsize+1
and 0<move[1]<self.BDsize+1
and self.board[move[0]-1][move[1]-1] == 0]
return valid_moves
注意：python列表下标从0开始，所以我们每次对board和pathboard进行索引时，必须减1
SearchNext 递归找出路径
这个函数接收一个参数cnt，表示还要走多少步。当每走一步，我们就给cnt-1。先考虑最后一步，这时候cnt等于0，于是我们返回True表示路径存在。这样的话，就可以递归地设计查找路径的算法。
递归过程：
- 判断cnt是否为0：如果为0，返回True；否则，进入2
- 利用FindMoves找出当前点的下一步可走方向的列表，判断列表元素的数量。如果为0，则说明无路可走，返回False；如果不为0，则用for循环遍历可走方向的列表
- 对每一个方向，将board上对应位置的值置为1，相当于沿着这个方向走了一步
- 用这个方向的坐标递归地计算下一步（参数cnt设置为cnt-1），如果返回值为真（说明沿这条路走下去有一条路径可以走完棋盘），则返回真；如果返回值不为真（说明沿这条路走下去没有一条路径可以走完棋盘），将board上对应位置的值改回0，相当于回退。
代码
def searchNext(self, cur_pos, cnt):
## 在表示路径的棋盘上标上当前是第几步
self.pathboard[cur_pos[0]-1][cur_pos[1]-1] = 64-cnt
if cnt == 0:
return True
else:
moves = self.FindMoves(cur_pos)
if len(moves) == 0 :
return False
for move in moves:
self.board[move[0]-1][move[1]-1] = 1
if self.searchNext(move,cnt-1): ## 递归调用，注意参数cnt-1
return True
else :
self.board[move[0]-1][move[1]-1] = 0
Tour
Tour相当于调用了方法SearchNext，实现了路径
def tour(self):
cur_pos = self.start_pos
self.board[cur_pos[0]-1][cur_pos[1]-1] = 1
self.searchNext(cur_pos, self.BDsize*self.BDsize-1)
printBD 打印棋盘
这个方法可以打印任何传入的棋盘（二维列表）
def printBD(self, board):
print("-------------------------")
for row in board:
for column in row:
print(column, end='\t')
print("")
print("-------------------------")
printPath 打印路径棋盘
调用方法printBD打印出路径棋盘
def printPath(self):
self.printBD(self.pathboard)
运行
KT = KnightTour(8,[1,1]) ## 建立一个8*8的棋盘，出发点设置为(1,1)
KT.tour() ## 查找路径
KT.printPath() ## 打印路径棋盘
结果如下：
-------------------------
1 16 31 40 3 18 21 56
30 39 2 17 42 55 4 19
15 32 41 46 53 20 57 22
38 29 48 43 58 45 54 5
33 14 37 52 47 60 23 62
28 49 34 59 44 63 6 9
13 36 51 26 11 8 61 24
50 27 12 35 64 25 10 7
-------------------------
改进的算法（Improvement）
上述基于深度优先的朴素算法时间复杂度很高，为 O(kN)，其中 N 是棋盘的格子数，k为一个很小的常数。
上面例子的结果实际上是用下面的算法算出来的，如果用上面的算法，需要花好几小时才能算出一样的结果。
改进的思想源于此：
有时候，我们可走的方向不止一个，在上面的代码中，我们任意地选了第一个方向。换句话说，我们相当于选择了eight_dire列表中最靠前的可走方向。为改进算法的性能，我们现在更有计划地从可走方向中选择一个方向。具体来说，就是选择将来最不大可能再走到的地方。因为我们如果现在错过了这些将来不大可能走到的地方，以后可能会花很大代价去进行回溯，以便踏过这些格子。
那么，问题就变成了：如何确定哪个格子是将来最不可能走到的？可以给每个可走的方向再进行一次试走，看哪个方向上的下一步可走的步数最少。
举个例子：马现在处于(1,2)位置，可走的位置有(3,1)，(3,3)，(2,4)，为了选出一个方向，我们接着再试走一步：如果我们选了(3,1)，那么再下一步可以走(5,2)，(2,3)，(4,3)，共三个方向；同理，(3,3)的下一步方向有7个，(2,4)的下一步方向有5个。于是，(3,1)这个点就是将来不大可能被走到。（因为它只能走到3个点，就说明将来只有这三个点能走到它）所以我们现在就要先走(3,1)这个方向，以免将来很不容易走到它而产生大量回溯。
引入count和count_next两个函数来进行判断。
count_next
count_next 接收一个坐标为参数，返回这个坐标下一步可能方向的总数。
def count_next(self, cur_pos):
valid_moves = self.FindMoves(cur_pos)
return len(valid_moves)
count
count 接收一个坐标为参数，并调用count_next，计算出这个坐标的下一步所有可能方向，以及每种方向对应的再下一步的方向总数
def count(self, cur_pos):
valid_moves = self.FindMoves(cur_pos)
return [[self.count_next(move),move] for move in valid_moves]
searchNext
最后，我们修改一下我们的searchNext函数，对可能路径排序，选择排序结果中最不可能走到的那个方向，而不是选择第一个
def searchNext(self, cur_pos, cnt):
self.pathboard[cur_pos[0]-1][cur_pos[1]-1] = 64-cnt
if cnt == 0:
return True
else:
moves = self.count(cur_pos)
moves.sort()
if moves[0][0] == 0 and cnt!= 1:
return False
for move in moves:
self.board[move[1][0]-1][move[1][1]-1] = 1
if self.searchNext(move[1], cnt-1):
return True
else :
self.board[move[1][0]-1][move[1][1]-1] = 0
注：判断条件moves[0][0] == [0] and cnt != 1是为了判断是否到达一个死节点。设想如果一个节点（记为A点）的下一步方向中有一个（记为B）的再下一步可走数目为0，那么说明这个节点B只能通过A来到达，那么A必须是倒数第二步，B必须是最后一步，否则就永远不可能走到B点。
运行
这样改进之后，不论以哪一个点开始，都可以在1秒内计算出路径。
参考资料：
http://interactivepython.org/runestone/static/pythonds/Graphs/TheKnightsTourProblem.html