Python回溯算法

回溯算法

回溯算法是一种系统的搜索算法，用于解决诸如排列组合、子集生成、图的路径、棋盘问题等问题。其核心思想是通过递归尝试各种可能的解决方案，遇到不满足条件的解时则回退（回溯），继续尝试其他可能性，直到找到所有的解决方案或确认无解。

主要步骤:

1. 选择路径：在当前步骤选择一个可能的路径或选项。
2. 约束检查：检查当前选择是否满足问题的约束条件。如果不满足，则回溯。
3. 递归探索：对当前选择的路径进行递归探索，继续尝试后续步骤。
4. 回溯：如果当前路径或选择无法导致有效解，则回退到上一步，尝试其他可能的路径或选择。

1.生成所有子集

给定一个集合 [1, 2, 3]，我们需要生成这个集合的所有可能的子集。

def backtrack(start, path, result, nums):
    # 将当前路径加入结果中
    result.append(path[:])
    
    # 从start位置开始，尝试添加更多的元素到路径中
    for i in range(start, len(nums)):
        path.append(nums[i])  # 做选择
        backtrack(i + 1, path, result, nums)  # 递归调用
        path.pop()  # 撤销选择（回溯）

def subsets(nums):
    result = []
    backtrack(0, [], result, nums)
    return result

# 示例
nums = [1, 2, 3]
all_subsets = subsets(nums)
for subset in all_subsets:
    print(subset)

2.数独问题

根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。

def is_valid(board, row, col, num):
    # 检查行
    for i in range(9):
        if board[row][i] == num:
            return False

    # 检查列
    for i in range(9):
        if board[i][col] == num:
            return False

    # 检查3x3子网格
    start_row, start_col = 3 * (row // 3), 3 * (col // 3)
    for i in range(start_row, start_row + 3):
        for j in range(start_col, start_col + 3):
            if board[i][j] == num:
                return False

    return True


def solve_sudoku(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1, 10):  # 尝试放置数字1-9
                    if is_valid(board, row, col, num):
                        board[row][col] = num
                        if solve_sudoku(board):
                            return True
                        board[row][col] = 0  # 回溯
                return False
    return True


# 示例数独问题（0表示空位）
board = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

solve_sudoku(board)
for row in board:
    print(row)

3.八皇后问题

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

def is_safe(board, row, col):
    # 检查列是否有皇后
    for i in range(row):
        if board[i][col] == 1:
            return False

    # 检查左上对角线是否有皇后
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    # 检查右上对角线是否有皇后
    for i, j in zip(range(row, -1, -1), range(col, len(board), 1)):
        if board[i][j] == 1:
            return False

    return True


def solve_nqueens(board, row):
    # 如果所有行都放置了皇后，表示找到一个解决方案
    if row >= len(board):
        return 1

    count = 0
    # 尝试在当前行的每一列放置皇后
    for col in range(len(board)):
        if is_safe(board, row, col):
            board[row][col] = 1  # 放置皇后
            count += solve_nqueens(board, row + 1)  # 递归尝试放置下一行的皇后
            board[row][col] = 0  # 回溯，移除皇后

    return count


def main():
    n = 8
    board = [[0] * n for _ in range(n)]  # 初始化8x8棋盘
    total_solutions = solve_nqueens(board, 0)  # 计算所有解决方案的数量
    print(f"Total solutions: {total_solutions}")


if __name__ == "__main__":
    main()