如何用Python快速判断数独谜题是否可解？

问题背景 #

用Python开发数独求解器，需要实现判断数独谜题是否可解的功能。已实现is_valid、find_next_full、find_next_empty三个基础函数，希望判断逻辑尽可能简洁。现有尝试存在两个问题：

• 输入含两个以上数字的谜题时程序冻结
• 直接调用求解函数会陷入耗时循环，需要快速判断方案

用-1表示空白格，已实现的代码如下：

def find_next_empty(puzzle):
    """找到下一个空白格"""
    for row in range(9):
        for column in range(9):
            if puzzle[row][column] == -1:
                return row, column
    return None, None

def find_next_full(puzzle):
    """找到下一个已填格"""
    for row in range(9):
        for column in range(9):
            if puzzle[row][column] != -1:
                return row, column
    return None, None

def is_valid(puzzle, guess, row, col):
    """判断某位置填入指定数字是否合法"""
    row_vals = puzzle[row]
    if guess in row_vals:
        return False
    col_vals = [puzzle[i][col] for i in range(9)]
    if guess in col_vals:
        return False
    row_start = (row // 3) * 3
    col_start = (col // 3) * 3
    for r in range(row_start, row_start + 3):
        for c in range(col_start, col_start + 3):
            if puzzle[r][c] == guess:
                return False
    return True

def is_possible(puzzle):
    row, col = find_next_empty(puzzle)
    if row == None:
        print("This sudoku is already solved.")
        return False
    row, col = find_next_full(puzzle)
    while row != None:
        now = puzzle[row][col]
        puzzle[row][col] = -1
        if is_valid(puzzle, now, row, col):
            print("Square ", row, col, " is possible")
        else:
            print("This is an impossible sudoku.")
            return False
        previousrow, previouscol = row,col
        row, col = find_next_full(puzzle)
        puzzle[previousrow][previouscol] = now

补充：之前尝试直接调用求解函数，但耗时过长，求解函数代码如下：

def solve_sudoku(puzzle):
    global count
    row, col = find_next_empty(puzzle)
    if row is None and col is None:
        print("Solved")
        return True
    for guess in range(1,10):
        count += 1
        if is_valid(puzzle, guess, row, col):
            puzzle[row][col] = guess
            print("Square ", row, col, " is valid with ", guess)
            if solve_sudoku(puzzle):
                return True, puzzle
        puzzle[row][col] = -1
    return False

问题分析 #

1. 现有is_possible函数逻辑错误：仅验证单个已填数字的合法性，无法判断整体谜题是否存在解——合法的初始填数也可能组合后无解
2. 原始求解函数未做优化，盲目回溯导致耗时过长

优化后的快速可解性判断方案 #

基于现有基础函数，加入最少候选数启发式（优先处理候选数最少的空格），大幅减少回溯分支，同时不修改原谜题：

def count_valid_guesses(puzzle, row, col):
    """统计当前空格的合法候选数数量"""
    count = 0
    for guess in range(1, 10):
        if is_valid(puzzle, guess, row, col):
            count += 1
    return count

def find_best_empty(puzzle):
    """找到候选数最少的空格，减少回溯次数"""
    min_guesses = 10
    best_row, best_col = None, None
    for row in range(9):
        for col in range(9):
            if puzzle[row][col] == -1:
                guesses = count_valid_guesses(puzzle, row, col)
                if guesses == 0:
                    return None, None  # 无候选数，直接无解
                if guesses < min_guesses:
                    min_guesses = guesses
                    best_row, best_col = row, col
                    if min_guesses == 1:  # 找到唯一候选的格子，直接返回
                        return best_row, best_col
    return best_row, best_col

def is_solvable(puzzle):
    """判断数独是否可解，不修改原谜题"""
    # 第一步：检查初始填数是否合法
    for row in range(9):
        for col in range(9):
            val = puzzle[row][col]
            if val != -1:
                # 临时移除当前值，验证合法性
                puzzle[row][col] = -1
                if not is_valid(puzzle, val, row, col):
                    puzzle[row][col] = val
                    return False
                puzzle[row][col] = val

    # 复制谜题，避免修改原数据
    puzzle_copy = [row.copy() for row in puzzle]
    row, col = find_best_empty(puzzle_copy)
    if row is None:
        return True  # 谜题已完成

    # 回溯尝试填充候选数
    for guess in range(1, 10):
        if is_valid(puzzle_copy, guess, row, col):
            puzzle_copy[row][col] = guess
            if is_solvable(puzzle_copy):
                return True
        puzzle_copy[row][col] = -1
    return False

使用示例 #

# 测试示例
test_puzzle = [
    [9, 8, -1, -1, -1, -1, -1, -1, -1],
    [-1, -1, -1, -1, -1, -1, -1, -1, -1],
    [-1, -1, -1, -1, -1, -1, -1, -1, -1],
    [-1, -1, -1, -1, -1, -1, -1, -1, -1],
    [-1, -1, -1, -1, -1, -1, -1, -1, -1],
    [-1, -1, -1, -1, -1, -1, -1, -1, -1],
    [-1, -1, -1, -1, -1, -1, -1, -1, -1],
    [-1, -1, -1, -1, -1, -1, -1, -1, -1],
    [-1, -1, -1, -1, -1, -1, -1, -1, -1]
]

print(is_solvable(test_puzzle))  # 输出 True

优化点说明 #

1. 最少候选数启发式：优先处理候选数最少的空格，能快速剪枝无效分支，比原始回溯快数倍甚至数十倍
2. 不修改原谜题：内部复制谜题副本，避免影响原始输入数据
3. 前置合法性检查：先验证初始填数是否合法，提前排除明显无解的情况

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