Python数独生成器无限循环问题求助及代码修复方案

原代码核心问题 #

• 区块检查逻辑错误：硬编码每个3x3区块的所有元素，包含大量未填充的0，导致错误排除合法数字；且重复编写区块判断代码，极易出错。
• 行列检查逻辑混乱：行检查用计数器判断的逻辑完全错误，列检查通过统计非目标数字行数来判断，逻辑颠倒且低效。
• 缺少回溯机制：暴力随机填充，一旦前面的选择导致后续单元格无合法数字可填，就会陷入无限循环，无法回退修正。

修复后的代码 #

import random

def is_valid(grid, row, col, num):
    # 检查行
    if num in grid[row]:
        return False
    # 检查列
    if num in [grid[r][col] for r in range(9)]:
        return False
    # 检查3x3区块
    block_row = (row // 3) * 3
    block_col = (col // 3) * 3
    for r in range(block_row, block_row + 3):
        for c in range(block_col, block_col + 3):
            if grid[r][c] == num:
                return False
    return True

def fill_grid(grid):
    for row in range(9):
        for col in range(9):
            if grid[row][col] == 0:
                # 生成1-9的随机排列，避免重复尝试相同数字
                nums = random.sample(range(1, 10), 9)
                for num in nums:
                    if is_valid(grid, row, col, num):
                        grid[row][col] = num
                        # 递归填充下一个单元格，成功则返回True
                        if fill_grid(grid):
                            return True
                        # 失败则回溯，重置当前单元格为0
                        grid[row][col] = 0
                # 所有数字都尝试过，返回False触发回溯
                return False
    # 所有单元格填充完成
    return True

def generate_sudoku():
    sudoku_grid = [[0 for _ in range(9)] for _ in range(9)]
    fill_grid(sudoku_grid)
    return sudoku_grid

# 测试生成并打印
sudoku = generate_sudoku()
for row in sudoku:
    print(row)

关键改进说明 #

1. 封装合法性检查函数：is_valid函数统一处理行、列、区块的合法性验证，自动计算当前单元格所在区块，避免硬编码错误。
2. 采用回溯算法：递归填充单元格，当当前数字导致后续无法完成时，自动回退重置当前单元格，尝试下一个数字，从根本上避免无限循环。
3. 随机数字排列：对每个单元格，生成1-9的随机排列再尝试，避免重复尝试相同数字，提升生成效率。
4. 简化代码结构：去除冗余的区块判断代码，逻辑清晰易维护。

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