递归函数不会在预期的地方返回。

Question

这是一个sudoku解算器，在第二个函数中，当我试图返回已解决的板子时，它看起来是空的，但是如果您打印板，您可以看到解决方案。以下是代码：

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

def solution(row, col, number):
    for i in range(9):
        if board[row][i] == number:
            return False
        if board[i][col] == number:
            return False
        row0 = (row // 3) *3
        col0 = (col // 3) * 3
        for i in range(3):
            for j in range(3):
                if board[row0+i][col0+j] == number:
                    return False
    return True

def solve():
    global board
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for number in range(1,10):
                    if solution(row, col, number):
                        board[row][col] = number
                        solve()
                        board[row][col] = 0
                return
    [print(x) for x in board] 
    return board


print(solve())

如何使解题功能返回新板？

Answer 1

代码的问题是，您有两个退出点，一个返回board

`return board`

一个什么也不返回的人(即None)

`return`

如果遵循递归调用的调用方式，就会发现父调用实际上是从None退出点返回的。但是，仅仅将board传递到退出点并不能解决这个问题，因为您有对solve()的递归调用，然后是返回到0特定的单元格。所以从本质上讲，首先解决sudoku，然后将整个解决方案解压到您开始的位置。要解决这个问题，您需要跟踪实际解决sudoku的时间，如果sudoku被解决，则跳过设置返回到0。

这样做的一种方法(为了避免global的危险使用而略作重写)是：

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


def solution(board, row, col, number):
    for i in range(9):
        if board[row][i] == number:
            return False
        if board[i][col] == number:
            return False
    row0 = (row // 3) *3
    col0 = (col // 3) * 3
    for i in range(3):
        for j in range(3):
            if board[row0+i][col0+j] == number:
                return False
    return True


def solve(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                is_solved = False
                for number in range(1, 10):
                    if solution(board, row, col, number):
                        board[row][col] = number
                        is_solved = solve(board)
                        if not is_solved:
                            board[row][col] = 0
                return is_solved
    return True


def print_board(board):
    for row in board:
        print(row)
    print()

print_board(board)
# [5, 3, 0, 0, 7, 0, 0, 0, 0]
# [6, 0, 0, 1, 9, 5, 0, 0, 0]
# [0, 9, 8, 0, 0, 0, 0, 6, 0]
# [8, 0, 0, 0, 6, 0, 0, 0, 3]
# [4, 0, 0, 8, 0, 3, 0, 0, 1]
# [7, 0, 0, 0, 2, 0, 0, 0, 6]
# [0, 6, 0, 0, 0, 0, 2, 8, 0]
# [0, 0, 0, 4, 1, 9, 0, 0, 5]
# [0, 0, 0, 0, 8, 0, 0, 7, 9]
solve(board)
print_board(board)
# [5, 3, 4, 6, 7, 8, 9, 1, 2]
# [6, 7, 2, 1, 9, 5, 3, 4, 8]
# [1, 9, 8, 3, 4, 2, 5, 6, 7]
# [8, 5, 9, 7, 6, 1, 4, 2, 3]
# [4, 2, 6, 8, 5, 3, 7, 9, 1]
# [7, 1, 3, 9, 2, 4, 8, 5, 6]
# [9, 6, 1, 5, 3, 7, 2, 8, 4]
# [2, 8, 7, 4, 1, 9, 6, 3, 5]
# [3, 4, 5, 2, 8, 6, 1, 7, 9]

从本质上说，solve()函数被更改为：

它接受一个修改过的visualization)

• 参数，如果board已经解决了，返回的是
• ，如果板卡已经解决了，它不会解除解决方案

H 124(一个print_board()辅助函数用于简单的

• )。

(此外，solution()已更改为包含board参数，以避免依赖全局board定义，最后一个块在主循环之外，因为它在那里被无意义地循环)。

该函数不需要返回board，因为它是就地修改的。

如果一个人真的需要董事会被归还，你可以简单地包括它在回报。

注意，如果您只是将循环中的唯一return替换为一个break，这似乎是行不通的。如果确实有效，它将需要大量的时间。我怀疑这最终会导致无限循环，因为您只需找到一些部分解决方案，并将其永远地展开(这个假设是基于将我的代码中的return替换为一个生成部分解决方案的break )。