递归调用中的退出子句

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)

我需要一个 exit 语句，该语句将在达到拼图解决方案后退出所有递归调用。我不知道该怎么做，需要帮助。将来，我还想添加一个功能，让算法继续通过解决方案检查任何其他可能的解决方案。请记住这一点，以便退出语句适用于此。谢谢！

Answer 1

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

我觉得你在尝试自己发现事物，
互联网上已经有很多例子了。

所以这里有一个更一般的提示 - 您可以重新设计您的算法以像这样工作：

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() return 值并在每次递归调用时检查它们。在面向蛮力的搜索中，这是非常常见的方法。 IE。利用那个 0（应该是 False 顺便说一句）你 return 在一个地方，添加一些 return True 和一个 if... 然后你'重新设置。

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

递归调用中的退出子句

Exit clause in recursive call

python

recursion

sudoku