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

发布时间：2020-12-16 21:59:11 所属栏目：Python 来源：网络整理

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

我正在做功课的数独拼图解决方案,但遇到了一些困难.现在的代码已经超越了解决方案,虽然它确实可以轻松解决问题,而对于更难的谜题,它会因为没有明显原因而被困在几个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 False

def 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 return
return 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 True
print "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的板)可能需要更长的时间.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!