回溯算法python

回溯算法是一种通过尝试所有可能的解来解决问题的算法。在Python中，可以使用递归函数来实现回溯算法。下面是一个简单的回溯算法的Python代码示例，用于解决八皇后问题：

def is_valid(board, row, col):
    # 检查当前位置是否与之前的皇后冲突
    for i in range(row):
        # 检查同一列是否有皇后
        if board[i] == col:
            return False
        # 检查对角线是否有皇后
        if abs(board[i] - col) == abs(row - i):
            return False
    return True

def solve_n_queens(n, board, row, solutions):
    if row == n:
        # 找到一个解决方案
        solutions.append(board[:])
    else:
        for col in range(n):
            if is_valid(board, row, col):
                board[row] = col
                solve_n_queens(n, board, row + 1, solutions)

def solve_nqueens(n):
    board = [-1] * n
    solutions = []
    solve_n_queens(n, board, 0, solutions)
    return solutions

n = 8
solutions = solve_nqueens(n)
print(f"共找到 {len(solutions)} 个解决方案：")
for solution in solutions:
    print(solution)

这段代码使用回溯算法来解决八皇后问题，打印出所有的解决方案。其中，`is_valid`函数用于检查当前位置是否与之前的皇后冲突，`solve_n_queens`函数用于递归地搜索解决方案，`solve_nqueens`函数是入口函数，用于初始化变量并调用`solve_n_queens`函数。