数独back-tracking递归程序2秒超时退出base case问题求助

• 计时逻辑错误：你将计时起点start = time.time()写在了递归函数内部，每次调用solver进入新的递归层时都会重置计时起点，end-start统计的永远是当前递归层的运行时长，而非整个求解过程的总时长，自然几乎不可能触发2秒的超时阈值。
• 超时后未立即终止执行：你检测到超时后仅修改了global_length = 0，没有立刻触发返回，当前层的循环、合法性校验甚至新的递归调用仍会继续执行，无法快速退出整个递归栈。
• 合法性判断逻辑反向：正常来说isValid返回True代表当前值可以填入对应格子，但你代码中写的是if Checker == False:才执行填数逻辑，等于合法值被跳过、非法值才会被填入，直接导致回溯逻辑无法正常运行。

核心修改点：将计时起点移到递归外全局初始化、超时后立即返回、修正合法性判断逻辑：

import time

# 全局变量提前初始化
global_length = 待填格子总数
global_row_index = -3
global_column_index = -3
global_val_index = -3
# 计时起点移到递归外，仅初始化一次
start_global = time.time()

def solver(Domains,SudokuSolv):
    global global_length
    global global_row_index
    global global_column_index
    global global_val_index
    global start_global

    if global_length == 0:
        return True
    else:
        global_row_index+=3
        global_column_index+=3
        global_val_index+=3
        row = Domains[global_row_index]
        col = Domains[global_column_index] 
        val = global_val_index

    for i in Domains[val]:
        # 超时判断提到循环最开头，避免执行无意义逻辑
        end = time.time()
        if end - start_global > 2:
            global_length = 0
            # 立即返回触发base case，逐层退出递归
            return True

        Checker = isValid(i,row,col,SudokuSolv)
        # 修正判断逻辑：合法值才填入格子
        if Checker:
            SudokuSolv[row][col] = i
            global_length-= 1
            if solver(Domains, SudokuSolv):
                return True
            global_length+=1
            SudokuSolv[row][col] = 0
        else:
            print("Trying next value...")

    global_row_index-=3
    global_column_index-=3
    global_val_index-=3
    return False

• 尽量避免用全局变量维护递归状态，可将行列索引、剩余待填数作为递归入参传递，状态管控更清晰，也能避免全局变量被意外修改的问题。
• 可以加入剪枝逻辑，优先选择可选值最少的格子进行填数，大幅提升数独求解速度，降低触发超时的概率。

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