请排查Valid Sudoku验证代码错误并解答递归实现可行性

错误点定位 #

原代码存在多处逻辑错误，导致输出始终为False：

1. 行左侧检查循环条件错误：
   检查当前单元格左侧行元素时，循环条件 while col1>len(board) 完全错误，列索引范围是0-8，正确条件应为 while col1 >= 0，否则该循环不会执行，无法检测左侧重复。
2. 列上方检查的双重错误：
   • 循环条件 while row1>0 错误，应改为 while row1 >= 0，才能覆盖所有上方行索引（0到duprow-1）；
   • 循环体内错误修改了row变量，而非循环变量row1，导致循环无法正常终止，且无法正确遍历上方行。
3. 递归solve函数逻辑缺陷：
   • 当col>=len(board)时，直接return（默认返回None），而非返回True，导致递归终止时无法传递有效验证结果；
   • 在遍历行时，调用solve(col+1)后未处理其返回值，且重复递归会导致多次重复验证，一旦某个递归分支返回False，无法正确向上传递结果；
   • 遍历逻辑错误：按列遍历每个单元格后递归下一列，会导致同一列的每个单元格都触发一次全列验证，冗余且逻辑混乱。

修正后的代码 #

from typing import List

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        def check(row: int, col: int) -> bool:
            val = board[row][col]
            if val == ".":
                return True
            
            # 检查当前行
            for c in range(9):
                if c != col and board[row][c] == val:
                    return False
            
            # 检查当前列
            for r in range(9):
                if r != row and board[r][col] == val:
                    return False
            
            # 检查3x3子格
            start_row = row - row % 3
            start_col = col - col % 3
            for i in range(3):
                for j in range(3):
                    curr_row = start_row + i
                    curr_col = start_col + j
                    if (curr_row != row or curr_col != col) and board[curr_row][curr_col] == val:
                        return False
            
            return True
        
        # 遍历所有单元格进行验证
        for row in range(9):
            for col in range(9):
                if not check(row, col):
                    return False
        return True

关于递归实现验证的说明 #

可以通过递归实现数独有效性验证，核心思路是按顺序遍历每个单元格，验证当前单元格符合规则后，递归验证下一个单元格（例如按行优先，从(0,0)到(8,8)），当所有单元格验证通过时返回True，一旦某个单元格验证失败则返回False。

示例递归实现的核心逻辑如下：

from typing import List

def is_valid_recursive(board: List[List[str]], row=0, col=0) -> bool:
    # 所有单元格验证完成
    if row == 9:
        return True
    # 当前行遍历完成，进入下一行
    if col == 9:
        return is_valid_recursive(board, row + 1, 0)
    # 空单元格直接递归下一个
    if board[row][col] == ".":
        return is_valid_recursive(board, row, col + 1)
    
    val = board[row][col]
    # 检查当前行
    for c in range(9):
        if c != col and board[row][c] == val:
            return False
    # 检查当前列
    for r in range(9):
        if r != row and board[r][col] == val:
            return False
    # 检查3x3子格
    start_row = row - row % 3
    start_col = col - col % 3
    for i in range(3):
        for j in range(3):
            curr_row = start_row + i
            curr_col = start_col + j
            if (curr_row != row or curr_col != col) and board[curr_row][curr_col] == val:
                return False
    
    # 验证通过则递归下一个单元格
    return is_valid_recursive(board, row, col + 1)

不过需要注意：递归实现的效率与迭代方式基本一致，但迭代代码通常更直观易读，适合数独验证这类简单遍历场景。

内容的提问来源于stack exchange，提问作者117__pushpak raj__