回溯循环返回值问题及数独求解数组拷贝疑惑

一、return语句缩进问题的根源与解决 #

原代码的核心问题是回溯递归的终止逻辑缺失，导致要么无限循环，要么返回被回溯清空的初始棋盘：

问题拆解 #

1. return放循环内部：递归找到解后，上层递归会继续执行self.board[i][j] = 0回溯清空，最后返回的是被重置后的初始棋盘。
2. return放循环外部：没有判断递归是否找到解，递归调用后继续执行回溯，加上每次调用solve都重置self.board = self.input_array，导致一直重复尝试，陷入无限循环。

正确的回溯逻辑 #

回溯算法需要在找到解后立即终止所有递归栈，不再执行回溯步骤。修改后的solve方法逻辑如下：

def solve(self):
    # 仅初始化一次board为原数组的深拷贝，避免修改原输入且防止递归重置
    if not hasattr(self, 'board'):
        self.board = copy.deepcopy(self.input_array)
    
    for i in range(9):
        for j in range(9):
            if self.board[i][j] == 0:
                for val in range(1, 10):
                    if self.isPossible(self.board, i, j, val):
                        self.board[i][j] = val
                        # 递归求解并判断是否找到解
                        solution = self.solve()
                        if solution:
                            # 找到解直接返回，跳过回溯
                            return solution
                        # 未找到解，回溯清空当前位置
                        self.board[i][j] = 0
                # 当前位置所有数字尝试失败，返回None让上层递归重试
                return None
    # 遍历完所有格子（无空值），说明找到解
    self.print_board(self.board)
    return self.board

关键修改点 #

• 初始化board为深拷贝，避免递归过程中修改原输入数组，也防止每次递归重置棋盘。
• 递归调用后判断返回值，若找到解直接向上传递，不再执行回溯步骤。
• 当当前位置所有数字尝试失败时返回None，触发上层递归的其他尝试。

二、数组拷贝问题的解释 #

数独棋盘是二维嵌套列表，不同拷贝方式的差异：

• 浅拷贝：copy()或切片[:]仅复制外层列表，内部的子列表还是原数组的引用。修改原数组的子元素时，浅拷贝的副本会同步变化。
• 深拷贝：copy.deepcopy()会递归复制所有层级的元素，创建完全独立的副本，修改原数组不会影响副本。

示例验证：

original = [[1,2],[3,4]]
shallow_copy = original.copy()
shallow_copy[0][0] = 99
print(original)  # 输出 [[99,2],[3,4]]，原数组被修改

deep_copy = copy.deepcopy(original)
deep_copy[0][0] = 1
print(original)  # 输出 [[99,2],[3,4]]，原数组不受影响

所以你代码中只有self.unsolved3 = copy.deepcopy(self.input_array)是真正独立的初始棋盘副本。

三、完整修改后的代码 #

import copy
from termcolor import colored

def fileToArray(inputFile):    
    createdBoard = []
    with open(inputFile, "r", encoding='utf-8') as fichier: 
        for line in fichier:
            createdBoard.append(line.rstrip())
    for i in range(len(createdBoard)):
        createdBoard[i] = list(createdBoard[i].replace(u'_',u'0').strip())
    for i in range(len(createdBoard)):
        for j in range(len(createdBoard[i])):
            createdBoard[i][j] = int(createdBoard[i][j])
    return createdBoard        

array1 = fileToArray("/home/dennis/Dev/PythonDev/Divers/grilles_sudoku/sudoku2.txt")
print("初始棋盘：", array1)

class SudokuSolver:
    """
    求解数独并在终端打印，初始数字为绿色，求解出的数字为白色
    """
    def __init__(self,input_array):
        self.input_array = input_array
        # 仅保留深拷贝的初始棋盘副本
        self.unsolved = copy.deepcopy(self.input_array)

    def print_board(self,x):
        print("\n求解结果：")
        for i in range(9):
            for j in range(9):
                print(str(x[i][j]) if self.unsolved[i][j] == 0 else colored(str(self.unsolved[i][j]), 'green'), end=" ")
            print() 
        
    def isPossible(self,board, row, col, val):
        for j in range(9):
            if board[row][j] == val:
                return False
        for i in range(9):
            if board[i][col] == val:
                return False
        startRow = (row // 3) * 3
        startCol = (col // 3) * 3
        for i in range(3):
            for j in range(3):
                if board[startRow+i][startCol+j] == val:
                    return False
        return True      
    
    def solve(self):
        if not hasattr(self, 'board'):
            self.board = copy.deepcopy(self.input_array)
        
        for i in range(9):
            for j in range(9):
                if self.board[i][j] == 0:
                    for val in range(1, 10):
                        if self.isPossible(self.board, i, j, val):
                            self.board[i][j] = val
                            solution = self.solve()
                            if solution:
                                return solution
                            self.board[i][j] = 0
                    return None
        self.print_board(self.board)
        return self.board

a = SudokuSolver(array1)
b = a.solve()
print("\n返回的求解棋盘：", b)

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