马踏棋盘（关于回溯法的应用）_马踏棋盘怎么玩

作者：AllinToyou | 2024-05-15 15:22:40

踩

马踏棋盘怎么玩

问题描述：

在中国象棋中，棋子马的走法是走“日”字型；

现有一8*8的中国象棋棋盘，棋子马从任意给定一点出发，走“日”字型，要求为马

寻找一条走遍棋盘每一格并且只经过一次的一条路径。

给定一个初始的坐标，如（0,0），从该点向外走“日”字型,有两种走法，若起始点

在（4,4），棋子的每个方向都可以走，有八种走法。

所以正常计算的计算量过大，使用回溯法会优化不少

回溯算法的基本思想是：

回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续

下一条路。八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二

步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第一个皇后的位

置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。回溯算法说白了

就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达最终状态（即答案状

态）的节点，从而减少状态空间树节点的生成。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/573551