Python回溯法数独解器卡顿问题求助

问题背景 #

我正在用Python开发一款数独游戏，目前在生成已解数独板时遇到了问题。下方的两个函数分别用于生成数独板和验证落子是否有效。

数独板中的每个列表对应最终数独的一个3×3宫格，宫格的索引如下：

0 1 2
3 4 5
6 7 8

每个宫格内元素的索引如下：

0 1 2 
3 4 5
6 7 8

create_Board()函数会随机出现卡顿的情况，我认为原因是下一个位置没有可行的落子方案。恳请提供解决建议，以下是我的代码：

import random as rand

def create_Board():
    board = [ # initiates the board
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0]
    ]
    i = 0
    while i < 81: # loops through each square in the board
        square = ((i // 9) // 3) * 3 + ((i % 9) // 3)
        spot = ((i // 9) % 3) * 3 + ((i % 9) % 3)
        board[square][spot] = 0
        nums = [j for j in range(1, 10)] # the possible numbers that can be put in the spot
        rand.shuffle(nums) # shuffles the numbers
        for n in nums:
            if is_Valid_Move(board, n, square, spot): # checks if putting that number there is valid
                board[square][spot] = n
                i += 1 # continues to the next spot
                break
            elif n == nums[-1]: # if the number is invalid and we reach the end of the array of nums, this moves back 1 spot and tries again
                board[square][spot] = 0
                i -= 1
    return board

def is_Valid_Move(board, num, square, spot):
    board[square][spot] = num
    f = True
    count = 0
    for s in board[square]: # checks this square
        if s == num:
            count += 1
    if count > 1:
        f = False 

    count = 0
    for i in range(square // 3 * 3, square // 3 * 3 + 3): # checks the row
        for j in range(spot // 3 * 3, spot // 3 * 3 + 3):
            if board[i][j] == num:
                count += 1
    if count > 1:
        f = False
    #return True
    count = 0
    for i in range(square % 3, 9, 3): # checks the column
        for j in range(spot % 3, 9, 3):
            if board[i][j] == num:
                count += 1
    if count > 1:
        f = False 
    return f

问题分析 #

你的生成逻辑存在几个核心问题，直接导致了卡顿甚至死循环：

1. 回溯逻辑有漏洞：当当前位置试完所有数字都无效时，仅把i减1回到上一个位置，但上一个位置没有记录已经尝试过哪些数字，会重复试同样的无效组合，陷入循环。
2. 验证函数有副作用：is_Valid_Move会直接修改传入的board，验证时改变了原板状态，可能导致后续判断出错。
3. 低效的计数验证：每次验证都遍历计数，虽然能判断重复，但效率偏低（不过这不是卡顿的主要原因）。

解决建议 #

1. 改用递归回溯逻辑 #

递归回溯是数独生成的标准方案，逻辑更清晰，能避免重复尝试无效组合。每个位置尝试数字后，递归处理下一个位置；如果后续无法完成填充，就撤销当前选择，尝试下一个数字。

2. 修复验证函数的副作用 #

验证时不要直接修改原板，而是通过计算行、列、宫格的对应位置来检查重复，避免污染原板状态。

3. 优化验证逻辑 #

直接检查是否存在重复数字，无需计数，提升效率。

改进后的代码 #

import random

def is_valid_move(board, num, square, spot):
    # 转换为标准数独的行、列索引，方便检查行和列
    row = 3 * (square // 3) + (spot // 3)
    col = 3 * (square % 3) + (spot % 3)
    
    # 检查当前宫格是否有重复
    for cell in board[square]:
        if cell == num:
            return False
    
    # 检查当前行是否有重复
    row_squares = [(row // 3) * 3 + col_offset for col_offset in range(3)]
    row_spots = [(row % 3) * 3 + col_in_sq for col_in_sq in range(3)]
    for sq, sp in zip(row_squares, row_spots):
        if board[sq][sp] == num:
            return False
    
    # 检查当前列是否有重复
    col_squares = [row_offset * 3 + (col // 3) for row_offset in range(3)]
    col_spots = [row_in_sq * 3 + (col % 3) for row_in_sq in range(3)]
    for sq, sp in zip(col_squares, col_spots):
        if board[sq][sp] == num:
            return False
    
    return True

def create_board():
    board = [[0]*9 for _ in range(9)]
    
    def backtrack(pos):
        # 所有位置填充完成，返回True表示成功
        if pos == 81:
            return True
        
        # 计算当前位置对应的宫格和宫内索引
        square = ((pos // 9) // 3) * 3 + ((pos % 9) // 3)
        spot = ((pos // 9) % 3) * 3 + ((pos % 9) % 3)
        
        # 随机打乱数字顺序，保证生成的数独是随机的
        nums = list(range(1, 10))
        random.shuffle(nums)
        
        for num in nums:
            if is_valid_move(board, num, square, spot):
                board[square][spot] = num
                # 递归处理下一个位置，如果成功就返回
                if backtrack(pos + 1):
                    return True
                # 回溯，撤销当前选择
                board[square][spot] = 0
        
        # 所有数字都尝试过，无法填充，返回False触发回溯
        return False
    
    backtrack(0)
    return board

# 测试生成并打印标准格式数独
if __name__ == "__main__":
    sudoku_board = create_board()
    for row_idx in range(9):
        current_row = []
        square_row = row_idx // 3
        spot_row = row_idx % 3
        # 拼接每行的三个宫格对应行的元素
        for sq_col in range(3):
            sq = square_row * 3 + sq_col
            current_row.extend(sudoku_board[sq][spot_row*3 : spot_row*3+3])
        print(" ".join(map(str, current_row)))

代码说明 #

• 递归回溯：backtrack函数从第0个位置开始填充，每个位置尝试随机打乱的数字，若当前数字能让后续所有位置填充成功则保留，否则撤销选择。
• 无副作用验证：is_valid_move通过计算行、列、宫格的对应位置检查重复，不会修改原板。
• 随机化填充：每次尝试前打乱数字顺序，确保生成的数独是随机的，而非固定模式。

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