如何用Python更高效快速生成数独 现有随机填充算法性能不足如何优化

问题描述 #

我的目标是构造大小为N²×N²的网格，填入1~N²范围内的正整数，满足如下规则：

1~N²范围内的每个整数在每行、每列及每个N×N区块中仅出现一次。

我已经编写了3×3规格的数独生成代码，支持指定预填充单元格，但尝试生成全填充数独时设备算力无法支撑，这类算法可以从以下方向优化：

现有实现代码 #

import random

def MakeSudoku():
    Grid = [[0 for x in range(9)] for y in range(9)]
            
    for i in range(9):
        for j in range(9):
            Grid[i][j] = 0
            
    # 这里的range参数控制网格里预填数字的数量
    for i in range(5):
        # 随机选择位置和数字
        row = random.randrange(9)
        col = random.randrange(9)
        num = random.randrange(1,10)
        # 位置被占用或者数字不合法就重新随机
        while(not CheckValid(Grid,row,col,num) or Grid[row][col] != 0):
            row = random.randrange(9)
            col = random.randrange(9)
            num = random.randrange(1,10)
        Grid[row][col]= num;
        
    Printgrid(Grid)

def Printgrid(Grid):
    TableTB = "|--------------------------------|"
    TableMD = "|----------+----------+----------|"
    print(TableTB)
    for x in range(9):
        for y in range(9):
            if ((x == 3 or x == 6) and y == 0):
                print(TableMD)
            if (y == 0 or y == 3 or y== 6):
                print("|", end=" ")
            print(" " + str(Grid[x][y]), end=" ")
            if (y == 8):
                print("|")
    print(TableTB)
    
def CheckValid(Grid,row,col,num):
    valid = True
    # 检查行和列是否已有重复数字
    for x in range(9):
        if (Grid[x][col] == num):
            valid = False
    for y in range(9):
        if (Grid[row][y] == num):
            valid = False
    rowsection = row // 3
    colsection = col // 3
    # 检查所属N×N区块是否有重复数字
    for x in range(3):
        for y in range(3):
            if(Grid[rowsection*3 + x][colsection*3 + y] == num):
                valid = False
    return valid

MakeSudoku()

核心优化方向 #

你现有代码的核心问题是纯随机填充的逻辑冲突概率随空白格减少指数级上升，后续基本会陷入死循环，可从以下角度优化：

• 改用回溯+剪枝替换纯随机填充：按顺序逐格填数，每次仅选择当前格子的合法候选数，一旦后续格子无合法可选值就立即回溯回退上一步，避免无意义的随机重试。可以提前维护每个格子的候选数列表，不需要每次校验都遍历整行、整列、整个区块，能省掉大量重复计算。
• 用位运算优化合法性校验：用三个长度为9的整数分别记录每行、每列、每个区块已使用的数字，用位掩码判断数字是否存在，校验时间复杂度从O(N)降到O(1)。比如行掩码row_mask[i]的第k位为1，就说明第i行已经使用了数字k+1，判断时只需执行(row_mask[i] & (1 << (num-1))) == 0即可。
• 采用最小剩余值启发式规则调整填充顺序：不要按固定行列顺序填格子，每次优先选择当前候选数最少的格子填充，能大幅减少回溯的分支数，提前剪掉大概率失败的路径。
• 无需完全随机数独时可采用基模板变换生成：先生成一个合法的完整数独作为基础模板，再通过同区块内行交换、区块行整体交换、同区块内列交换、区块列整体交换、全局数字映射（比如把所有1换成2、所有2换成7这类全局置换）生成新的合法数独，生成效率接近O(N⁴)，完全不需要回溯，适合批量生成场景。
• 预填充阶段保证合法性：你当前的预填逻辑本身也可能生成冲突的预填值（比如同区块出现两个相同数字），直接导致后续无论怎么填都不可能合法，预填充阶段就可以加入规则校验，避免死局。

内容的提问来源于stack exchange，提问作者Mike Ângelo