100个python算法超详细讲解：马踏棋盘

棋盘"/>

100个python算法超详细讲解：马踏棋盘

【100个python算法超详细讲解】@谷哥技术

1．问题描述
国际象棋的棋盘为8×8的方格棋盘。现将“马”放在任意指定的方格中，按
照“马”走棋的规则将“马”进行移动。要求每个方格只能进入一次，最终使
得“马”走遍棋盘的64个方格。编写一个Python程序，实现马踏棋盘操作，要求
用1～64这64个数字标注“马”移动的路径，也就是按照求出的行走路线，将数字
1～64依次填入棋盘的方格中，并输出。
2．问题分析
国际象棋中，“马”的移动规则如图8.17所示。

图中实心的圆圈代表“马”的位置，它下一步可移动到图中空心圆圈所标注
的8个位置上，该规则叫作“马走日”。但是如果“马”位于棋盘的边界附近，那么
它下一步可移动到的位置就不一定有8个了，因为要保证“马”每一步都走在棋盘
中。
马踏棋盘的问题其实就是要将1～64填入到一个8×8的矩阵中，要求相邻的
两个数按照“马”的移动规则放置在矩阵中。例如数字a放置在矩阵的(i,j)位置
上，则数字a+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)、(i-1,j-2)、(i-2,j-1)之中的一个位置上。这样在矩阵中从1遍历
到64，就得到了马踏棋盘的行走路线。因此本题的最终目的是输出一个8×8的矩
阵，在该矩阵中填写1～64这64个数字，相邻数字之间遵照“马走日”的规则。

3．算法设计
解决马踏棋盘问题的一种比较容易理解的方法是应用递归的深度优先搜索
的思想。因为“马”每走一步都是盲目的，它并不能判断当前的走步一定正确，
而只能保证当前这步是可走的。“马”走的每一步棋都是从它当前位置出发，向
下一步的8个位置中的1个行走（在它下一步有8个位置可走的情况下）。因
此“马”当前所走的路径并不一定正确，因为它可能还有剩下的可选路径没有尝
试，如图8.18所示。

在图8.18中，假设最开始“马”位于棋盘的(0,0)位置，接下来“马”有两处位置
可走，即(1,2)和(2,1)。这时“马”是无法确定走2的位置最终是正确的，还是走3
的位置最终是正确的。因此“马”只能任意先从一个路径走下去（例如从2的位
置）。如果这条路是正确的，那当然是幸运的，如果不正确，则“马”要退回到
第一步，继续从3的位置走下去。以后“马”走的每一步都遵循这个规则。这个过
程就是一种深度搜索的过程，同时也是一种具有重复性操作的递归过程。可以
用一棵“探索树”来描述该深度优先搜索的过程，如图8.19所示。

 “马”的行走过程实际上就是一个深度探索的过程。如图8.19所示，“探索
树”的根结点为“马”在棋盘中的初始位置（这里用4×4的棋盘示意）。接下
来“马”有两种行走方式，于是根结点派生出两个分支。而再往下一步行走，根
结点的两个孩子又能够分别派生出其他不同的“行走路线”分支，如此派生下
去，就得到了“马”的所有可能的走步状态。可以想见，该探索树的叶子结点只
可能有两种状态：一是该结点不能再派生出其他的“走步”分支了，也就
是“马”走不通了；二是棋盘中的每个方格都被走到，即“马”踏遍棋盘。于是从
该探索树的根结点到第二种情况的叶结点构成的路径就是马踏棋盘的行走过
程。
如何才能通过搜索这棵探索树找到这条马踏棋盘的行走路径呢？可以采用
深度优先搜索的方法以先序的方式访问树中的各个结点，直到访问到叶结点。
如果叶结点是第二种情况的叶结点，则搜索过程可以结束，因为找到了马踏棋
盘的行走路径；如果叶结点为第一种情况的叶结点，即走不通了，则需要返回
到上一层的结点，顺着该结点的下一条分支继续进行深度优先搜索下去。
因此在设计“马踏棋盘”的算法时可以借鉴图的深度优先遍历算法和二叉树
的先序遍历（根左右）算法。但是在这里并不需要真正地构建这样一棵探索
树，我们只需要借用探索树的思想。在实际的操作过程中，所谓的探索树实际
就是深度优先搜索的探索路径，每个结点实际就是当前的棋盘状态，而所谓的
叶结点要么就是在当前棋盘状态下，“马”无法再进行下一步行走；要么就是马
踏棋盘成功。该算法可描述如下：

# 深度优先搜索的“马踏棋盘”
def TravelChessBoard(x, y, tag):
x1, y1, flag, count = x, y, False, 0
chess[x][y] = tag
搜索成功 返回
if tag == 60: # 搜索成功，返回1
return True
flag, x1, y1 = nextxy(x1, y1, count) # 找到基于(x1,y1)的下一个可走位置
# 上一步未找到，则在其余几种可走位置中寻找下一个可走位置
while not flag and count < 7:
count = count + 1
print('(1): ', count)
flag, x1, y1 = nextxy(x1, y1, count)
while flag: # 找到下一个可走位置，则进行深度优先搜索
if TravelChessBoard(x1, y1, tag + 1): # 递归
return True
x1 = x
y1 = y
count = count + 1
flag, x1, y1 = nextxy(x1, y1, count) # 寻找下一个(x,y)
while not flag and count < 7: # 循环地寻找下一个(x,y)
count = count + 1
print('(2): ', count)
flag, x1, y1 = nextxy(x1, y1, count)
if not flag:
chess[x][y] = 0 # 搜索不成功，擦除足迹，返回0
return False

该算法中通过函数TravelChessBoard()递归地搜索“马”的每一种走法。其中
参数x、y指定“马”当前走到棋盘中的位置，tag是标记变量，每走一个棋盘方
格，tag自动增1，它标识着马踏棋盘的行走路线。
算法首先将当前“马”处在棋盘中的位置上添加标记tag，然后判断tag是否等
于64，如果等于64，说明这是马踏棋盘的最后一步，因此搜索成功，程序应当
结束，返回1。否则，找到“马”下一步可以走到的位置(x1,y1)，如果找到这个位
置坐标，flag置1，否则flag置0。
下面在flag为1的条件下（即找到坐标(x1,y1)），递归地调用函数
TravelChessBoard()。也就是从(x1,y1)指定的棋盘中的位置继续向下深度搜索。
如果从(x1,y1)向下搜索成功，即程序一直执行下去，直到tag等于64返回1，那
就说明“马”已经踏遍棋盘（马踏棋盘的过程是：先走到棋盘的(x,y）位置，再从
(x,y）的下一个坐标(x1,y1)向下深度搜索，直至走遍全棋盘），于是搜索结束，
返回1；否则继续找到“马”的下一个可以行走的坐标(x1,y1)，如果找到这个位置
坐标，flag置1，并从(x1,y1)向下重复上述的递归搜索，否则flag置0，本次递归
结束。
如果找遍当前位置(x,y)的下一个坐标(x1,y1)（一般情况是8种），但是从
(x1,y1)向下继续深度优先搜索都不能成功地“马踏棋盘”（此时flag等于0），则
表明当前所处的状态并不处于马踏棋盘的“行走路径”上，也就是说“马”本不应
该走到(x,y)的位置上，因此将chess[x][y]置0，表明棋盘中该位置未被走过（擦
掉足迹），同时返回0，程序退到上一层的探索状态。
这里应当知道，所谓当前位置(x,y)的下一个坐标(x1,y1)是指“马”下一步可
以走到的地方，用坐标(x1,y1)返回。在探索树中它处在(x,y)所在的结点的子结
点中，如图8.20所示。

当前位置(x,y)的下一个坐标(x1,y1)的可选个数由当前棋盘的局面决定。一
般情况下有8种可走的位置（如图8.17所示），但是如果“马”位于棋盘的边缘
（如图8.18所示的探索树的根结点）或者8个可选位置中有的已被“马”前面的足
迹所占据，则这两种情况下(x1,y1)的可选个数就不是8个了。
上述搜索算法相当于先序遍历探索树，只不过它不一定是将探索树完整地
遍历，而是当tag等于64时，也就是棋盘被全部“踏遍”时就停止继续搜索了。
4．完整的程序
根据以上分析，编写程序如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 马踏棋盘
# 找到基于（x,y）位置的下一个可走的位置
def nextxy(x, y, count):
if count == 0 and x + 2 <= X - 1 and y - 1 >= 0 and chess[x + 2][y - 1]
== 0: # 找到坐标(x+2,y-1)
x = x + 2
y = y - 1
flag = True
elif count == 1 and x + 2 <= X - 1 and y + 1 <= Y - 1 and chess[x + 2][y
+ 1] == 0: # 找到坐标(x+2,y+1)
x = x + 2
y = y + 1
flag = True
elif count == 2 and x + 1 <= X - 1 and y - 2 >= 0 and chess[x + 1][y -
找到坐标
2] == 0: # 找到坐标(x+1,y-2)
x = x + 1
y = y - 2
flag = True
elif count == 3 and x + 1 <= X - 1 and y+2 <= Y-1 and chess[x+1][y+2]
== 0: # 找到坐标(x+1,y+2)
x = x + 1
y = y + 2
flag = True
elif count == 4 and x - 2 >= 0 and y - 1 >= 0 and chess[x - 2][y - 1]
== 0: # 找到坐标(x-2,y-1)
x = x - 2
y = y - 1
flag = True
elif count == 5 and x - 2 >= 0 and y + 1 <= Y - 1 and chess[x - 2][y +
1] == 0: # 找到坐标(x-2,y+1)
x = x - 2
y = y + 1
flag = True
elif count == 6 and x - 1 >= 0 and y - 2 >= 0 and chess[x - 1][y - 2]
== 0: # 找到坐标(x-1,y-2)
x = x - 1
y = y - 2
flag = True
elif count == 7 and x - 1 >= 0 and y + 2 <= Y - 1 and chess[x - 1][y +
2] == 0: # 找到坐标(x-1,y+2)
x = x - 1
y = y + 2
flag = True
else:
flag = False
return flag, x, y
# 深度优先搜索的“马踏棋盘”
def TravelChessBoard(x, y, tag):
x1, y1, flag, count = x, y, False, 0
chess[x][y] = tag
if tag == 60: # 搜索成功，返回1
return True
flag, x1, y1 = nextxy(x1, y1, count) # 找到基于(x1,y1)的下一个可走位置
# 上一步未找到，则在其余几种可走位置中寻找下一个可走位置
while not flag and count < 7:
count = count + 1
# print('(1): ', count)
flag, x1, y1 = nextxy(x1, y1, count)
while flag: # 找到下一个可走位置，则进行深度优先搜索
if TravelChessBoard(x1, y1, tag + 1): # 递归
return True
x1 = x
y1 = y
count = count + 1
flag, x1, y1 = nextxy(x1, y1, count) # 寻找下一个(x,y)
while not flag and count < 7: # 循环地寻找下一个(x,y)
count = count + 1
# print('(2): ', count)
flag, x1, y1 = nextxy(x1, y1, count)
if not flag:
chess[x][y] = 0 # 搜索不成功，擦除足迹，返回0
return False
if __name__ == '__main__':
X = 8
Y = 8
chess = [[0]*X for i in range(Y)] # 初始化，棋盘的所有位置都置0
深度优先搜索
if TravelChessBoard(2, 0, 1): # 深度优先搜索
for i in range(X):
for j in range(Y):
print("%-5d" % chess[i][j],
end='')
print()
print("The horse has travelled the
chess borad")
else:
print("The horse cannot travel the
chess board")

 5．运行结果
在PyCharm下运行程序，结果如图8.21所示。