python 回溯算法（Backtracking）

回溯算法（Backtracking）是一种通过试错的方式寻找问题的解的算法设计方法。它通常用于解决组合问题，通过递归地尝试所有可能的解，并在发现当前路径不可能得到解时回退（回溯）。以下是使用Python实现回溯算法解决几个经典问题的示例：

1. 八皇后问题（N-Queens Problem）

八皇后问题要求在 ( N \times N ) 的棋盘上放置 ( N ) 个皇后，使得它们互不攻击。

python">def solve_n_queens(n):def is_safe(board, row, col):# 检查列是否有冲突for i in range(row):if board[i] == col:return False# 检查对角线是否有冲突if abs(board[i] - col) == abs(i - row):return Falsereturn Truedef backtrack(row):if row == n:solutions.append(board[:])returnfor col in range(n):if is_safe(board, row, col):board[row] = colbacktrack(row + 1)board[row] = -1  # 回溯solutions = []board = [-1] * n  # 初始化棋盘backtrack(0)return solutions# 示例
n = 4
solutions = solve_n_queens(n)
for solution in solutions:print(solution)
# 输出:
# [1, 3, 0, 2]
# [2, 0, 3, 1]

2. 数独求解（Sudoku Solver）

数独求解问题要求填充一个 ( 9 \times 9 ) 的数独网格，使得每行、每列和每个 ( 3 \times 3 ) 子网格都包含数字 1 到 9。

python">def solve_sudoku(board):def is_valid(row, col, num):# 检查行和列for i in range(9):if board[row][i] == num or board[i][col] == num:return False# 检查 3x3 子网格start_row, start_col = 3 * (row // 3), 3 * (col // 3)for i in range(3):for j in range(3):if board[start_row + i][start_col + j] == num:return Falsereturn Truedef backtrack():for row in range(9):for col in range(9):if board[row][col] == 0:  # 找到空白格for num in range(1, 10):if is_valid(row, col, num):board[row][col] = numif backtrack():return Trueboard[row][col] = 0  # 回溯return Falsereturn Truebacktrack()# 示例
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, 0],[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)
# 输出:
# [5, 3, 4, 6, 7, 8, 9, 1, 2]
# [6, 7, 2, 1, 9, 5, 3, 4, 8]
# [1, 9, 8, 3, 4, 2, 5, 6, 7]
# [8, 5, 9, 7, 6, 1, 4, 2, 3]
# [4, 2, 6, 8, 5, 3, 7, 9, 1]
# [7, 1, 3, 9, 2, 4, 8, 5, 6]
# [9, 6, 1, 5, 3, 7, 2, 8, 4]
# [2, 8, 7, 4, 1, 9, 6, 3, 5]
# [3, 4, 5, 2, 8, 6, 1, 7, 9]

3. 子集生成（Subset Generation）

生成一个集合的所有子集。

python">def subsets(nums):def backtrack(start, path):result.append(path[:])for i in range(start, len(nums)):path.append(nums[i])backtrack(i + 1, path)path.pop()  # 回溯result = []backtrack(0, [])return result# 示例
nums = [1, 2, 3]
print(subsets(nums))
# 输出: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

4. 排列组合（Permutations and Combinations）

生成一个集合的所有排列或组合。

排列（Permutations）

python">def permutations(nums):def backtrack(path):if len(path) == len(nums):result.append(path[:])returnfor num in nums:if num not in path:path.append(num)backtrack(path)path.pop()  # 回溯result = []backtrack([])return result# 示例
nums = [1, 2, 3]
print(permutations(nums))
# 输出: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

组合（Combinations）

python">def combinations(nums, k):def backtrack(start, path):if len(path) == k:result.append(path[:])returnfor i in range(start, len(nums)):path.append(nums[i])backtrack(i + 1, path)path.pop()  # 回溯result = []backtrack(0, [])return result# 示例
nums = [1, 2, 3, 4]
k = 2
print(combinations(nums, k))
# 输出: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]