[我正在学习回溯和递归，但我不理解（或无法在脑海中看到）为什么我的初始算法将电路板打印回其原始状态，而不是打印解决方案。
这是我第一次解决问题：
grid = [
[7,8,0,4,0,0,1,2,0],
[6,0,0,0,7,5,0,0,9],
[0,0,0,6,0,1,0,7,8],
[0,0,7,0,4,0,2,6,0],
[0,0,1,0,5,0,9,3,0],
[9,0,4,0,6,0,0,0,5],
[0,7,0,3,0,0,0,1,2],
[1,2,0,0,0,7,4,0,0],
[0,4,9,2,0,6,0,0,7]
]
def print_grid(grid):
rows = len(grid)
cols = len(grid[0])
for y in range(rows):
if y % 3 == 0 and y != 0:
print("- " * (cols + 3))
for x in range(cols):
if x % 3 == 0 and x != 0:
print(" | ", end="")
if x == 8:
print(grid[y][x])
else:
print(str(grid[y][x]) + " ", end="")
def find_empty(grid):
for y in range(9):
for x in range(9):
if grid[y][x] == 0:
return (y, x)
def possible(grid, y, x, n):
# check rows
for i in range(9):
if grid[i][x] == n:
return False
# check cols
for i in range(9):
if grid[y][i] == n:
return False
# check subgrid
y0 = (y // 3) * 3
x0 = (x // 3) * 3
for i in range(3):
for j in range(3):
if grid[y0+i][x0+j] == n:
return False
return True
def solve(grid):
empty = find_empty(grid)
if not empty:
return True
y, x = empty
for n in range(1, 10):
if possible(grid, y, x, n):
grid[y][x] = n
solve(grid)
grid[y][x] = 0
solve(grid)
print_grid(grid)
将solve函数更改为下面的代码后，我得到了预期的结果。
def solve(grid):
empty = find_empty(grid)
if not empty:
return True
y, x = empty
for n in range(1, 10):
if possible(grid, y, x, n):
grid[y][x] = n
# changed this part
if solve(grid):
return True
grid[y][x] = 0
函数“如果不为空”的第一个出口点不够吗？
grid[y][x] = 0
因为这实际上会在解决后覆盖正确的板（尝试在条件print_grid(grid)内添加if not empty:）。我认为，了解正确的代码比了解原始代码为什么不起作用要快。我添加了一些印刷线，以便于理解。
def solve(grid): empty = find_empty(grid) if not empty: print("board completed") return True y, x = empty for n in range(1, 10): if possible(grid, y, x, n): grid[y][x] = n if solve(grid): print("board is completed! do not reset anymore") return True print((y,x), " is not", n, " !!! reset this!!!") grid[y][x] = 0
打印：
(0, 4) is not 9 !!! reset this!!! (0, 2) is not 3 !!! reset this!!! (2, 1) is not 9 !!! reset this!!! (2, 0) is not 3 !!! reset this!!! (2, 1) is not 3 !!! reset this!!! (3, 5) is not 8 !!! reset this!!! (3, 3) is not 1 !!! reset this!!! (4, 3) is not 7 !!! reset this!!! (4, 1) is not 6 !!! reset this!!! (4, 0) is not 2 !!! reset this!!! (4, 8) is not 4 !!! reset this!!! (4, 5) is not 2 !!! reset this!!! (4, 3) is not 7 !!! reset this!!! (4, 1) is not 6 !!! reset this!!! (4, 0) is not 8 !!! reset this!!! (3, 8) is not 1 !!! reset this!!! (3, 5) is not 8 !!! reset this!!! (3, 3) is not 9 !!! reset this!!! (3, 1) is not 5 !!! reset this!!! (3, 0) is not 3 !!! reset this!!! (3, 5) is not 8 !!! reset this!!! (3, 3) is not 1 !!! reset this!!! (4, 3) is not 7 !!! reset this!!! (4, 1) is not 6 !!! reset this!!! (4, 0) is not 2 !!! reset this!!! (4, 8) is not 4 !!! reset this!!! (4, 5) is not 2 !!! reset this!!! (4, 3) is not 7 !!! reset this!!! (4, 1) is not 6 !!! reset this!!! (4, 0) is not 8 !!! reset this!!! (3, 8) is not 1 !!! reset this!!! (3, 5) is not 8 !!! reset this!!! (3, 3) is not 9 !!! reset this!!! (3, 1) is not 3 !!! reset this!!! (3, 0) is not 5 !!! reset this!!! (3, 3) is not 1 !!! reset this!!! (3, 3) is not 9 !!! reset this!!! (3, 1) is not 3 !!! reset this!!! (3, 5) is not 3 !!! reset this!!! (3, 3) is not 1 !!! reset this!!! (6, 5) is not 4 !!! reset this!!! (6, 4) is not 8 !!! reset this!!! (7, 3) is not 5 !!! reset this!!! (7, 2) is not 8 !!! reset this!!! (6, 6) is not 8 !!! reset this!!! (6, 5) is not 4 !!! reset this!!! (6, 4) is not 9 !!! reset this!!! (6, 2) is not 6 !!! reset this!!! board completed
基本上，not empty仅在正确填充电路板时才为真。因为如果任何数字位于错误的位置，则最终该错误的数字将由grid[y][x] = 0重置，并使用另一个数字进行测试。[如果开发板完成并且执行了
if not empty: return True，则if solve(grid):将知道它不再应该重新设置开发板，因此它返回True。这将从函数中逸出，这意味着grid[y][x] = 0行将被跳过。如果您不理解，请尝试在每行之间打印，以便您了解发生了什么。希望这对您有所帮助：）