已發布·持續改進
回溯法 指南 · 2/6
本章目前僅提供英文版。
This chapter traces two small examples by hand to show what backtracking actually does at runtime. First we follow combination generation, which needs no pruning, and then we watch constraint checks and backtracking interact in 4-Queens. Finally we see how the same idea drives a Sudoku solver.
We choose 2 numbers out of [1, 2, 3, 4]. To avoid duplicates that differ only in order, the next choice always starts after the number just chosen, so a branch like [2, 1] is never created.
def combine(n, k):
result, path = [], []
def dfs(start):
if len(path) == k:
result.append(path[:])
return
for x in range(start, n + 1):
path.append(x) # choose
dfs(x + 1) # explore
path.pop() # unchoose
dfs(1)
return result
print(combine(4, 2))
# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]Following the calls step by step shows path growing and shrinking:
| Step | Action | path | Output |
|---|---|---|---|
| 1 | choose 1 | [1] | |
| 2 | choose 2 | [1, 2] | store [1, 2] |
| 3 | undo 2, choose 3 | [1, 3] | store [1, 3] |
| 4 | undo 3, choose 4 | [1, 4] | store [1, 4] |
| 5 | undo 4 and 1, choose 2 | [2] | |
| 6 | choose 3 | [2, 3] | store [2, 3] |
| 7 | ... | [3, 4] | last combination |
We can add one pruning rule here. If fewer numbers remain than slots left to fill, there is no point continuing, so narrowing the loop to range(start, n - (k - len(path)) + 2) stops the search from creating branches such as [4] that can never reach two elements.
Place 4 queens on a 4x4 board so that no two attack each other. If we put exactly one queen in each row, row conflicts disappear by construction, and we only need to check columns and the two diagonals. Squares on the same diagonal share the value row - col, and squares on the same anti-diagonal share row + col.
def is_safe(queens, row, col):
# queens[r] = column of the queen placed in row r
for r, c in enumerate(queens):
if c == col or r - c == row - col or r + c == row + col:
return False
return TrueHere is the search up to the first solution, written as column indices:
| State | Try | Result |
|---|---|---|
| [] | row 0, col 0 | placed |
| [0] | row 1, col 0 and 1 | column clash, diagonal clash |
| [0] | row 1, col 2 | placed |
| [0, 2] | row 2, cols 0-3 | all clash, backtrack |
| [0] | row 1, col 3 | placed |
| [0, 3] | row 2, col 1 | placed |
| [0, 3, 1] | row 3, cols 0-3 | all clash, backtrack |
| [0, 3] | row 2, col 2 and 3 | clash, back up to row 0 |
| [] | row 0, col 1 | placed |
| [1] | row 1, col 3 | placed |
| [1, 3] | row 2, col 0 | placed |
| [1, 3, 0] | row 3, col 2 | placed, solution [1, 3, 0, 2] |
It took only a handful of steps to prove that no solution starts with a queen in row 0, column 0. Instead of generating all 4^4 = 256 placements, the full search for both solutions visits just 17 nodes, root included.
def solve(n):
solutions = []
def place(queens):
row = len(queens)
if row == n:
solutions.append(queens[:])
return
for col in range(n):
if is_safe(queens, row, col):
queens.append(col)
place(queens)
queens.pop()
place([])
return solutions
print(solve(4)) # [[1, 3, 0, 2], [2, 0, 3, 1]]Sudoku follows the same pattern. Pick an empty cell, try the digits 1 through 9, and skip any digit already present in the same row, column, or 3x3 box. If no digit fits, return to the previous cell and try its next digit.
def can_place(board, r, c, d):
if any(board[r][j] == d for j in range(9)):
return False
if any(board[i][c] == d for i in range(9)):
return False
br, bc = 3 * (r // 3), 3 * (c // 3)
return all(board[i][j] != d
for i in range(br, br + 3)
for j in range(bc, bc + 3))Practical solvers add the MRV heuristic (minimum remaining values): always fill the cell with the fewest legal digits first. A cell with a single candidate is filled immediately, and dead ends are exposed much earlier.
path, pairs every choice with an undo, and descends depth first.
0 則留言
登入 · 登入後即可留言。
來留下第一則留言吧。