python - 下面的递归函数是如何工作的?
问题描述
我最近观看了这个视频,展示了一个解决数独的递归函数,这似乎不合理,因为最后我们总是将值改回零。
为什么该功能在视频中有效但对我不起作用?网格是否应该对我们双方保持不变,因为最后我们使用grid[y][x] = 0
哪个重置网格丢弃所做的所有更改?
此代码的想法是遍历每个数字单元格和每个数字(1-9)并检查是否可以将数字放入该单元格中。如果我们走到了死胡同,我们就会原路返回。
这是我手动复制的代码:
import numpy as np
global grid
grid = [[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,6],
[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]]
def possible(y,x,n):
global grid
for i in range(0, 9):
if grid[y][i] == n:
return False
for i in range(0, 9):
if grid[i][x] == n:
return False
x0 = (x//3)*3
y0 = (y//3)*3
for i in range(0, 3):
for j in range(0, 3):
if grid[y0+i][x0+j] == n:
return False
return True
def solve():
global grid
for y in range(9):
for x in range(9):
if grid[y][x] == 0:
for n in range(1, 10):
if possible(y,x,n):
grid[y][x] = n
solve()
grid[y][x] = 0
return
print(np.matrix(grid))
print("")
solve()
print(np.matrix(grid))
解决方案
问题是该solve
函数确实在完成执行后将网格重置回其初始状态,但它也解决了数独问题。
在视频中,请注意网格是在solve
函数内部打印的,而不是在它之后:
def solve():
global grid
for y in range(9):
for x in range(9):
if grid[y][x] == 0:
for n in range(1, 10):
if possible(y,x,n):
grid[y][x] = n
solve()
grid[y][x] = 0
return
print(np.matrix(grid))
print(np.matrix(grid))
print("")
solve()
这是有效的,因为它循环遍历每个单元格,并且仅在该单元格尚未填充值时递归,然后在尝试了每个值之后,它返回。完成循环的唯一方法for y in range(9):
是它永远找不到不为 0 的单元格,即如果数独已解决,因此通过在循环完成后打印矩阵将确保它打印已解决的数独。
推荐阅读
- testing - 在 ExUnit 中为库测试查询
- arrays - 我的选项列表的 urlencode 数组
- javascript - 每次更改文件时,NodeJS都会获取文件的最后一行
- java - PostConstruct没有在junits中被调用
- python - 从特定日历 Google API Python 获取事件
- python - 不安全的登录 Facebook API
- xamarin - Xamarin 表单导航堆栈为空
- android - Kotlin 自定义对话框
- android - Android Wear 应用在商店中不可见(内部测试轨道)
- java - 在Java中将int转换为double期间精度会略有变化吗?