具有暴力回溯错误的Python Sudoku递归

概述我正在做功课的数独拼图解决方案,但遇到了一些困难.现在的代码已经超越了解决方案,虽然它确实可以轻松解决问题,而对于更难的谜题,它会因为没有明显原因而被困在几个9中.我将不胜感激任何帮助. (check_cell确定放置是否有效.)>在此代码中是否正确实现了回溯,如果没有,将如何修复？>如何阻止求解器冻结？它解决了大约3行然后冻结,将大多数值更改为

我正在做功课的数独拼图解决方案,但遇到了一些困难.现在的代码已经超越了解决方案,虽然它确实可以轻松解决问题,而对于更难的谜题,它会因为没有明显原因而被困在几个9中.我将不胜感激任何帮助. (check_cell确定放置是否有效.)

>在此代码中是否正确实现了回溯,如果没有,将如何修复？
>如何阻止求解器冻结？它解决了大约3行然后冻结,将大多数值更改为9s.

一些代码：

def solve_helper(self,row,col):# Try placing a number in each column of current row    board = self.the_board    if board[row][col] != 0:        ?????    elif board[row][col] == 0:        for i in range(1,10):            print("Setting value at i with ") + str (i) + (" located at " ) + str(row) + str(col)            self.set_cell(row,col,i)            self.guesses = self.guesses + 1            if self.check_cell(row,col):                if self.solve_helper(row,col): return True            else:                self.set_cell(row,0)    else:        return self.mover(row,col)    return Falsedef mover(self,col):    if col + 1 != 9:        return self.solve_helper(row,(col+1))    elif row + 1 != 9:        print "Moving to row" + str(row + 1)        return self.solve_helper((row+1),0)    else:        print "SolUTION FOUND"        return True

最佳答案你遇到的麻烦是你的一些递归调用没有正确返回结果,所以你的解决方案一旦被发现,就会被遗忘在递归堆栈的几个层次上.这是您需要的第一个修复,添加返回到移动器中的递归调用：

def mover(self,(col+1))  # added return    elif row + 1 != 9:        print "Moving to row" + str(row + 1)        return self.solve_helper((row+1),0)     # here too    else:        print "SolUTION FOUND"        return True

在您的solve_helper函数的特殊情况下,您还需要类似的东西,其中您跳过预解码的单元格.函数的结尾应该是：

else:    return self.mover(row,col)  # added returnreturn False

编辑：

好的,我在代码中发现了一些问题.其中两个是解算器的逻辑问题,一个是显示问题,除了在解决过程中看起来很奇怪之外不会引起任何实际问题.

问题：

>首先,你是最新的代码,其中solve_helper调用自己,而不是调用mover.这使得它在移动之前需要额外的函数调用(尽管我认为它实际上可能不会破坏解算器).
>其次,如果solve_helper将一个单元格设置为9,但随后又回溯到(在一些后来的单元格无法解决之后),则9在进一步回溯之前不会重置为零.
>最后,显示问题.将单元格设置为0不会停止显示旧值.这看起来很像#2中的问题,(回溯后留下了9s),但实际上它只是装饰性的.

第一个问题很容易解决.只需将solve_helper调用更改为移动器调用即可.这实际上就是你在问题中提出的原始代码中的内容.直接调用solve_helper实际上并没有得到错误的结果(因为solve_helper将第二次跳过已填充的单元格),但它会为递归的每个级别添加一个不必要的额外函数调用.

第二个问题稍微复杂一点,这就是你被困在某些板上的地方.你需要做的是将self.set_cell(row,0)的行移出它当前所在的else块.实际上,如果你愿意的话,你实际上可以完全将它移出循环外(从那以后)如果你在当前单元格的任何值都没有工作的情况下进行回溯,那么它才真正是必要的.以下是我认为这是for循环的最佳排列(也是返回False语句)：

for i in range(1,10):    print("Setting value ") + str (i) + (" at " ) + str(row) + "," + str(col)    self.set_cell(row,i)    self.guesses = self.guesses + 1    if self.check_cell(row,col):        if self.mover(row,col):            return Trueprint "Backtracking"self.set_cell(row,0)return False

最后,修复显示问题需要两处更改.首先,摆脱set_cell中的条件.您想要始终更新显示.接下来,在update_textfIEld中,将删除调用移到if块之外,以便始终发生(将插入保留在if下).这使得将单元格设置为零将擦除先前的值,但不会使其显示实际的0字符(它将不显示任何内容).

我认为应该这样做.请注意,您使用的算法仍然很慢.解决a board I found on the internet in a quick Google search需要122482个猜测和超过5分钟,但它终于工作了.其他板(特别是那些在前几个开放空间需要8s或9s的板)可能需要更长的时间. 总结

以上是内存溢出为你收集整理的具有暴力回溯错误的Python Sudoku递归全部内容，希望文章能够帮你解决具有暴力回溯错误的Python Sudoku递归所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。