python马踏棋盘

问题描述
现在有一个国际象棋棋盘（为8×8的方格棋盘）。现将棋子“马”放在棋盘上的任意位置，按照“马”走棋的规则（L形路线）将“马”进行移动。要求每个位置只能进入一次，最后要让棋子“马”走遍棋盘上的64个位置。请编写一个程序，完成上述操作，并用1～64这64个数字标注“马”移动的路径，也就是按照求出的行走路线，将数字1～64依次填入棋盘的方格中，并打印到屏幕上。
此问题的本质就是：利用递归思维不断的去尝试下一个落子的位置，除了最后一个落子位置以外，其余的每个落子位置至少存在1个可移动位置，至多存在8个可移动位置。所以这是一个最大递归深度为64，但递归广度非常大的问题。我们在1~8中取一个中间值4，假设每次落子的位置都有4个可移动位置，那我们将需要尝试落子的次数为4的64次方。是一个很大的数字，即使用我们的电脑去尝试落子这么多次也要花很久的时间。所以这里我们不用去找出所有的落子路线，只找到一条就可以了，找多了影响我们电脑的使用寿命。（计算速率很大的电脑当我没说）
计算可移动位置
国际象棋中马走的是一个L形路线，假设第一次落子的位置在（5，5），那它会有如下图中8个白色的可移动位置。
所以我们可以得出一个结论，当落子位置在（x，y）时，可移动位置有(x - 2, y + 1)、(x - 1, y + 2)、(x + 1, y + 2)、(x + 2, y + 1)、(x + 2, y - 1)、(x + 1, y - 2)、(x - 1, y - 2)、(x - 2, y - 1) 。然而不是所有的可移动位置都在棋盘内，例如落子位置为（1，1）时，可移动位置只有（2，3）和（3，2）两个，其他的位置都在棋盘外了。所以我们在找出可移动位置后还需要判断该位置是否在棋盘内。
我们根据上述过程设计出一个计算可移动位置的函数，来帮我们计算出当前落子位置的可移动位置有哪些。根据马走L形路线的规则，我们可以设计出如下代码：
def return_location(x: int, y: int):"""返回可移动位置有那些:param x: x坐标:param y: y坐标:return: 可移动位置列表"""l_list = []# 创建一个列表来存储可移动位置if x - 2 > 0 and y + 1 < 9:# 判断此位置是否超出棋盘l_list.append((x - 2, y + 1))# 没有超出棋盘，则放入列表中if x - 1 > 0 and y + 2 < 9:l_list.append((x - 1, y + 2))if x + 1 < 9 and y + 2 < 9:l_list.append((x + 1, y + 2))if x + 2 < 9 and y + 1 < 9:l_list.append((x + 2, y + 1))if x + 2 < 9 and y - 1 > 0:l_list.append((x + 2, y - 1))if x + 1 < 9 and y - 2 > 0:l_list.append((x + 1, y - 2))if x - 1 > 0 and y - 2 > 0:l_list.append((x - 1, y - 2))if x - 2 > 0 and y - 1 > 0:l_list.append((x - 2, y - 1))return l_list# 返回可移动位置列表
递归找位置

文章插图
递归找位置的方法类似于一个二叉树，从根节点开始一个分支一个分支的去找。如下图所示：
从第一个位置A开始，有两个可移动位置B和I 。选择移动到位置B，有两个可移动位置C和F 。选择移动到位置C，有两个可移动位置D和E 。选择移动到位置D，如果位置D不满足要求，就从位置D返回C，再从位置C选择另一个位置E 。如果位置E也不满足要求，说明位置C下面的分支都不满足要求，直接从位置C返回到位置B 。再从位置B移动到位置F，尝试F下面的所有位置是否满足要求。如果F下面的位置都不满足要求，说明位置B下面的分支都不满足要求，直接返回位置A 。再从A移动到I，查看I下面的各个分支，直到满足要求为止。上面这个二叉树只有3层深度，每个位置的可移动位置只有2个，马踏棋盘的深度为64，每个位置的可移动位置最少1个最多8个，会形成非常多的分支。虽然分支数量不同，但查找方式却相似。