python 回溯算法（Backtracking）

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

---

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

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

1. def solve_n_queens(n):
2.     def is_safe(board, row, col):
3.         # 检查列是否有冲突
4.         for i in range(row):
5.             if board[i] == col:
6.                 return False
7.             # 检查对角线是否有冲突
8.             if abs(board[i] - col) == abs(i - row):
9.                 return False
10.         return True
12.     def backtrack(row):
13.         if row == n:
14.             solutions.append(board[:])
15.             return
16.         for col in range(n):
17.             if is_safe(board, row, col):
18.                 board[row] = col
19.                 backtrack(row + 1)
20.                 board[row] = -1  # 回溯
22.     solutions = []
23.     board = [-1] * n  # 初始化棋盘
24.     backtrack(0)
25.     return solutions
27. # 示例
28. n = 4
29. solutions = solve_n_queens(n)
30. for solution in solutions:
31.     print(solution)
32. # 输出:
33. # [1, 3, 0, 2]
34. # [2, 0, 3, 1]

复制代码

---

2. 数独求解（Sudoku Solver）

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

1. def solve_sudoku(board):
2.     def is_valid(row, col, num):
3.         # 检查行和列
4.         for i in range(9):
5.             if board[row][i] == num or board[i][col] == num:
6.                 return False
7.         # 检查 3x3 子网格
8.         start_row, start_col = 3 * (row // 3), 3 * (col // 3)
9.         for i in range(3):
10.             for j in range(3):
11.                 if board[start_row + i][start_col + j] == num:
12.                     return False
13.         return True
15.     def backtrack():
16.         for row in range(9):
17.             for col in range(9):
18.                 if board[row][col] == 0:  # 找到空白格
19.                     for num in range(1, 10):
20.                         if is_valid(row, col, num):
21.                             board[row][col] = num
22.                             if backtrack():
23.                                 return True
24.                             board[row][col] = 0  # 回溯
25.                     return False
26.         return True
28.     backtrack()
30. # 示例
31. board = [
32.     [5, 3, 0, 0, 7, 0, 0, 0, 0],
33.     [6, 0, 0, 1, 9, 5, 0, 0, 0],
34.     [0, 9, 8, 0, 0, 0, 0, 6, 0],
35.     [8, 0, 0, 0, 6, 0, 0, 0, 3],
36.     [4, 0, 0, 8, 0, 3, 0, 0, 1],
37.     [7, 0, 0, 0, 2, 0, 0, 0, 0],
38.     [0, 6, 0, 0, 0, 0, 2, 8, 0],
39.     [0, 0, 0, 4, 1, 9, 0, 0, 5],
40.     [0, 0, 0, 0, 8, 0, 0, 7, 9]
41. ]
42. solve_sudoku(board)
43. for row in board:
44.     print(row)
45. # 输出:
46. # [5, 3, 4, 6, 7, 8, 9, 1, 2]
47. # [6, 7, 2, 1, 9, 5, 3, 4, 8]
48. # [1, 9, 8, 3, 4, 2, 5, 6, 7]
49. # [8, 5, 9, 7, 6, 1, 4, 2, 3]
50. # [4, 2, 6, 8, 5, 3, 7, 9, 1]
51. # [7, 1, 3, 9, 2, 4, 8, 5, 6]
52. # [9, 6, 1, 5, 3, 7, 2, 8, 4]
53. # [2, 8, 7, 4, 1, 9, 6, 3, 5]
54. # [3, 4, 5, 2, 8, 6, 1, 7, 9]

复制代码

---

3. 子集生成（Subset Generation）

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

1. def subsets(nums):
2.     def backtrack(start, path):
3.         result.append(path[:])
4.         for i in range(start, len(nums)):
5.             path.append(nums[i])
6.             backtrack(i + 1, path)
7.             path.pop()  # 回溯
9.     result = []
10.     backtrack(0, [])
11.     return result
13. # 示例
14. nums = [1, 2, 3]
15. print(subsets(nums))
16. # 输出: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

复制代码

---

4. 分列组合（Permutations and Combinations）

生成一个聚集的所有分列或组合。
分列（Permutations）

1. def permutations(nums):
2.     def backtrack(path):
3.         if len(path) == len(nums):
4.             result.append(path[:])
5.             return
6.         for num in nums:
7.             if num not in path:
8.                 path.append(num)
9.                 backtrack(path)
10.                 path.pop()  # 回溯
12.     result = []
13.     backtrack([])
14.     return result
16. # 示例
17. nums = [1, 2, 3]
18. print(permutations(nums))
19. # 输出: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

复制代码

组合（Combinations）

1. def combinations(nums, k):
2.     def backtrack(start, path):
3.         if len(path) == k:
4.             result.append(path[:])
5.             return
6.         for i in range(start, len(nums)):
7.             path.append(nums[i])
8.             backtrack(i + 1, path)
9.             path.pop()  # 回溯
11.     result = []
12.     backtrack(0, [])
13.     return result
15. # 示例
16. nums = [1, 2, 3, 4]
17. k = 2
18. print(combinations(nums, k))
19. # 输出: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

复制代码

---

总结

回溯算法通过递归地实验所有可能的解，并在发现当前路径不可能得到解时回退。它实用于组合问题、分列问题、搜索问题等。通过公道地剪枝和回溯，可以高效地找到问题的解。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。