LeetCode 37数独求解器：递归函数中原地修改列表的保存问题

递归内的print(board)能输出正确解，但最终返回的board仍是原始输入，问题核心是：找到解后没有及时终止整个回溯流程，后续的回溯步骤会把已经填好的数字重新改回.，导致最终board回到初始状态。

不需要额外用路径变量记录，最高效的方法是给回溯函数添加返回标记，找到解后立即终止所有递归，不再执行撤销操作。

原代码问题点 #

原回溯函数找到解后仅打印，并未终止递归，上层递归仍会执行board[i][j] = '.'，把填好的数字改回去。

修改后的代码 #

class Solution:
    def solveSudoku(self, board):
        def options(board, i, j):
            numbers = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
            choices = numbers.copy()

            for col in range(9):
                if board[i][col] in choices:
                    choices.remove(board[i][col])

            for row in range(9):
                if board[row][j] in choices:
                    choices.remove(board[row][j])

            corner_x, corner_y = (i // 3) * 3, (j // 3) * 3
            for row in range(corner_x, corner_x + 3):
                for col in range(corner_y, corner_y + 3):
                    if board[row][col] in choices:
                        choices.remove(board[row][col])

            return choices
        
        def back_tracking(board, pos):
            if pos == 81:
                # 找到解，返回True标记
                return True
            i, j = divmod(pos, 9)
            if board[i][j] != '.':
                # 已有数字，递归下一个位置，若找到解直接返回True
                if back_tracking(board, pos + 1):
                    return True
            else:
                for choice in options(board, i, j):
                    board[i][j] = choice
                    # 递归后若返回True，说明找到解，直接返回，不执行撤销
                    if back_tracking(board, pos + 1):
                        return True
                    # 没找到解才撤销当前选择
                    board[i][j] = '.'
            # 当前位置所有可能都试过，没找到解，返回False
            return False
        
        back_tracking(board, 0)
        return board

修改说明 #

1. 让back_tracking返回布尔值：True表示找到解，False表示当前路径无解
2. 当pos == 81（所有位置填充完成），立即返回True
3. 递归调用后如果收到True，直接向上层返回True，跳过board[i][j] = '.'的撤销操作
4. 处理已有数字的位置时，递归返回True也直接向上传递，终止后续流程

这样修改后，找到解时所有递归会立即终止，原board上的修改会被保留，不需要额外拷贝或保存路径，效率最高。

内容的提问来源于stack exchange，提问作者LarryC