gpt4 book ai didi

python 回溯

转载 作者:太空宇宙 更新时间:2023-11-04 06:22:01 30 4
gpt4 key购买 nike

我最近发了几个理解递归和回溯的问题,我觉得我现在得到了一些东西,并尝试编写一个测试,我确实解决了数独问题,但是当我以另一种格式编写代码时,代码卡了一会儿,返回False,说明这个问题无解。

grid 是一个 9x9 的列表列表,如果 list[i][j] 为零则表示需要填写。

这是解决问题的代码:

def correct_solve(grid):

# if there is no more zeros
if found_solution(grid):
return True

for row in xrange(9):
for col in xrange(9):
if grid[row][col] == 0:
for num in xrange(1, 10):
grid[row][col] = num
if check_sudoku(grid) == True:
if correct_solve(grid) == True:
return True
# there are no numbers which could make
# a valid solution, so backtrack
grid[row][col] = 0
return False

这是另一个函数,我试图用不同的方式解决问题,但失败了,我找不到问题出在哪里

def buggy_solve(grid, col):

# if there is no more zeros
if found_solution(grid):
return True

# if the col is over 8, make it to 0
if col > 8:
col = 0

for row in xrange(9):
if grid[row][col] == 0:
for num in xrange(1, 10):
grid[row][col] = num
if check_sudoku(grid) == True:
# I tend to move to the next cell, and it seems that
# this is correct.
if buggy_solve(grid, col + 1) == True:
return True

# if there are no valid solutions, backtrack.
grid[row][col] = 0
return False

我尝试调试程序但没有发现任何有用的东西,顺便说一下,调试一段递归代码有什么好的做法吗?

编辑:

这是我用来测试的矩阵:

easy = [[2,9,0,0,0,0,0,7,0],
[3,0,6,0,0,8,4,0,0],
[8,0,0,0,4,0,0,0,2],
[0,2,0,0,3,1,0,0,7],
[0,0,0,0,8,0,0,0,0],
[1,0,0,9,5,0,0,6,0],
[7,0,0,0,9,0,0,0,1],
[0,0,1,2,0,0,3,0,6],
[0,3,0,0,0,0,0,5,9]]

最佳答案

correct_solve 查看所有网格,而 buggy_solve 查看单个列。这意味着,如果问题还没有解决,buggy_solve 将只在当前列中查找要填充的单元格——如果该列恰好没有空单元格,它将跳出外部 for 循环并退出,无需使用显式 return 语句。因此,当发生这种情况时,您需要代码在下一列调用 buggy_solve(并使用适当的 return 语句)。

关于 python 回溯,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11538611/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com