python - 递归调用中的退出子句

Question

我正在创建一个递归算法来暴力破解数独谜题。我已经让一切正常工作，但是，我试图弄清楚如何在正确完成拼图后停止该过程。这是我到目前为止所拥有的。

def solve(board, cell):

    #calculate row and column of board
    row = cell // 9
    col = cell - (row*9)

    #check if unfilled cell
    if board[row][col] == 0:

        #calculates possible numbers for cell 
        nums = getCandidates(row, col)

        #if no possibilities previous cell must be wrong
        if(len(nums) == 0):
            return 0

        #Iterate all possibilities assume each num is correct until proven wrong
        for i in nums:
            board[row][col] = i
            solve(board, cell + 1)

        #No possibilities were correct previous cell must be wrong
        #Clear current cell and return to previous instance of solve()
        board[row][col] = 0

    else:
        #Cell already filled skip to next
        solve(board, cell+1)

我需要一个退出语句，一旦达到谜题解决方案，该语句将退出所有递归调用。我不知道如何做到这一点并且需要帮助。将来我还想添加一个功能，算法将继续通过解决方案检查任何其他可能的解决方案。请记住这一点，以便退出语句能够适应这种情况。谢谢!

Answer 1

我可以为您提供有效的确切代码，但是

1. 我觉得您正在尝试自己发现事物，
2. 互联网上已有大量示例。

所以这里有一个更一般的提示 - 您可以重新设计算法以如下方式工作:

def solve(problem):
    if problem is trivial / all candidates were filled:
        return if it succeeded

    for candidate in possible candidates:
        try candidate
        if solve(smaller problem):
            return True

    raise RuntimeError('Problem has no solutions')

基本上，利用 solve() 返回值并在每次递归调用时检查它们。这是面向暴力的搜索中非常常见的方法。 IE。利用您在一个地方返回的 0 (顺便说一句，应该是 False)，添加一些 return True 和一个 if...你就准备好了。

请注意，暴力破解数独谜题虽然可能是很好的教育体验，但并不是 the best approach in general .