(回溯算法) 详解回溯算法原理与使用方法
回溯算法是一种利用试探，如果没有达到问题的解，则取消上一步或者几步的计算，然后通过其他可能的分解步骤再次尝试查找问题的答案的算法。
在解决一些复杂的问题时，可能会有多个步骤涉及到决策，我们可以尝试每一种可能的决策，如果已经确定这个决策不能导向问题的解，我们就回退到上一个步骤，尝试别的可能的决策。
这里给出一个典型的回溯算法应用，即求解N皇后问题的Python代码示例：
# 初始化棋盘
def initBoard(size):
board = []
for _ in range(size):
board.append(["Q"]*size)
return board
# 检查当前位置是否可以放置皇后
def check(board, row, col, size):
# 检查列是否有皇后互相冲突
for i in range(row):
if board[i][col] == "Q":
return False
# 检查右上方是否有皇后互相冲突
i = row - 1
j = col + 1
while i>=0 and j<size:
if board[i][j] == "Q":
return False
i -= 1
j += 1
# 检查左上方是否有皇后互相冲突
i = row - 1
j= col - 1
while i>=0 and j>=0:
if board[i][j] == "Q":
return False
i -= 1
j -= 1
return True
# 采用回溯算法解决N皇后问题
def solveNQueens(board, row, size):
if row == size:
for line in board:
print(" ".join(line))
print("\n")
return
for col in range(size):
if check(board, row, col, size):
board[row][col] = "Q"
solveNQueens(board, row+1, size)
board[row][col] = "."
# 主函数
if __name__ == "__main__":
size = 4
board = initBoard(size)
solveNQueens(board, 0, size)代码解析：
首先，我们声明一个空棋盘。然后，我们使用递归并回溯到每一行，将皇后放到该行的每一列。如果当前选择的位置下方没有互相冲突的皇后，则继续下一行。如果当前位置不适合放置皇后，我们就回溯到当前行的一下列并尝试新的位置。一旦所有的皇后都放置好，我们就打印出来棋盘。
(python查看已安装的库) python查看自己安装的所有库并导出的命令 查看 Python 库：pip list 和 pip freeze 全网首发(图文详解1)
(repeat) Python 用repeat()重复单个值 使用 Numpy 的 repeat 函数 全网首发(图文详解1)
