为什么这个递归算法（数独求解器）将棋盘打印回其原始状态？
Why does this recursive algorithm (sudoku solver) prints the board back into its original state?
我正在学习回溯和递归，但我不明白（或无法在脑海中想象）为什么我的初始算法将电路板打印回其原始状态，而不是打印解决方案。
这是我第一次尝试解决问题：
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)
将求解函数改成下面的代码后，得到了预期的结果。
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
函数 "if not empty" 中的第一个退出点是否足够？
我也很难理解所有这些疯狂的递归，但我有点理解了。您的错误是由于行
grid[y][x] = 0
因为这实际上在解决后覆盖了正确的板（尝试在条件if not empty:中添加print_grid(grid)）。
我认为理解正确的代码比理解原始代码为何不起作用更快。
我添加了一些打印行，这样更容易理解。
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): 将知道它不应该再重置板，因此 returns 正确。这将从函数中退出，这意味着 grid[y][x] = 0 行将被跳过。
如果您不明白，请尝试在每行之间打印，以便了解发生了什么。希望这对您有所帮助:)
我正在学习回溯和递归，但我不明白（或无法在脑海中想象）为什么我的初始算法将电路板打印回其原始状态，而不是打印解决方案。
这是我第一次尝试解决问题：
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)
将求解函数改成下面的代码后，得到了预期的结果。
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
函数 "if not empty" 中的第一个退出点是否足够？
我也很难理解所有这些疯狂的递归，但我有点理解了。您的错误是由于行
grid[y][x] = 0
因为这实际上在解决后覆盖了正确的板（尝试在条件if not empty:中添加print_grid(grid)）。
我认为理解正确的代码比理解原始代码为何不起作用更快。 我添加了一些打印行，这样更容易理解。
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): 将知道它不应该再重置板，因此 returns 正确。这将从函数中退出，这意味着 grid[y][x] = 0 行将被跳过。
如果您不明白，请尝试在每行之间打印，以便了解发生了什么。希望这对您有所帮助:)