【算法-3】通俗理解递归回溯法，附马踏棋盘python代码+注释_python马踏棋盘回溯法

概述

递归回溯法：叫称为试探法，按选优条件向前搜索，当搜索到某一步，发现原先选择并不优或达不到目标时，就退回一步重新选择。

• 比较经典的问题包括骑士巡逻、八皇后和迷宫寻路等。

python示例代码

个人认为算法关键点有2点:
1.理解board[row][col]==0代表改块棋盘没有走过
2.在patrol函数的最后（第35行），board[row][col]=0消除走过的痕迹（因为试探之后发现原先选择无法达成目标，所以这里归0代表退回一步）

"""
递归回溯法：叫称为试探法，按选优条件向前搜索，当搜索到某一步，发现原先选择并不优或达不到目标时，就退回一步重新选择，
比较经典的问题包括骑士巡逻、八皇后和迷宫寻路等。
"""
# 这种退回操作一般就使用嵌套

SIZE = 5
total = 0


# 这个函数在patrol中调用，所以row，col直接引用patrol中的
def print_board(board):
    for row in board:
        for col in row:
            print(str(col).center(4), end
1
2
3
4
5
6
7
8
9
10
11
12
13
14