Python数独生成器9x9模式无响应问题求助

我编写了支持4x4、6x6、9x9三种尺寸的Python数独生成器代码，但运行9x9尺寸时程序无响应，任务管理器显示CPU占用20%、磁盘占用0%。

import numpy as np
from reportlab.lib.pagesizes import A4
from reportlab.lib.units import cm
from reportlab.pdfgen import canvas
from tkinter import *
from tkinter import filedialog

def generate_sudoku(size):
    grid = np.zeros((size, size), dtype=int)
    solve(grid)
    return grid

def solve(grid):
    size = len(grid)
    for row in range(size):
        for col in range(size):
            if grid[row][col] == 0:
                numbers = np.random.permutation(range(1, size + 1))
                for num in numbers:
                    if is_valid(grid, row, col, num):
                        grid[row][col] = num
                        if solve(grid):
                            return True
                        grid[row][col] = 0
                return False
    return True

def is_valid(grid, row, col, num):
    size = len(grid)
    # Check row
    if num in grid[row]:
        return False
    # Check column
    if num in grid[:, col]:
        return False
    # Check box
    box_size = int(size**0.5)
    box_row = row // box_size * box_size
    box_col = col // box_size * box_size
    box = grid[box_row:box_row+box_size, box_col:box_col+box_size]
    if num in box:
        return False
    return True

def remove_numbers(grid, num_clues):
    size = len(grid)
    cells = np.random.permutation(size * size)
    num_removed = 0
    for cell in cells:
        row = cell // size
        col = cell % size
        temp = grid[row][col]
        grid[row][col] = 0
        if not is_unique_solution(grid):
            grid[row][col] = temp
        else:
            num_removed += 1
            if num_removed >= size * size - num_clues:
                break

def is_unique_solution(grid):
    temp = grid.copy()
    return solve(temp)

def save_as_pdf(puzzles, solutions, puzzle_filename, solution_filename):
    # Save puzzles
    if puzzle_filename:
        c = canvas.Canvas(puzzle_filename, pagesize=A4)
        c.setFont("Helvetica", 14)

        num_puzzles = len(puzzles)
        num_per_page = 4  # Number of puzzles per page

        page_width, page_height = A4  # Get the page dimensions
        puzzle_width = 0.8 * page_width / (num_per_page // 2)
        puzzle_height = 0.8 * page_height / (num_per_page // 2)
        puzzle_margin = 0.05 * page_width  # Margin between puzzles

        total_puzzle_width = (puzzle_width + puzzle_margin) * (num_per_page // 2) - puzzle_margin
        puzzle_spacing = (page_width - total_puzzle_width) / 2

        for i in range(0, num_puzzles, num_per_page):
            c.showPage()
            for j in range(num_per_page):
                index = i + j
                if index < num_puzzles:
                    puzzle_x = puzzle_spacing + (j % (num_per_page // 2)) * (puzzle_width + puzzle_margin)
                    puzzle_y = page_height - (((j // (num_per_page // 2)) % 2) * (puzzle_height + puzzle_margin) + 0.1 * page_height)
                    draw_sudoku(c, puzzles[index], puzzle_x, puzzle_y)

        c.save()
        print("Puzzle PDF saved successfully!")

    # Save solutions
    if solution_filename:
        c = canvas.Canvas(solution_filename, pagesize=A4)
        c.setFont("Helvetica", 14)

        num_solutions = len(solutions)
        num_per_page = 4  # Number of solutions per page

        page_width, page_height = A4  # Get the page dimensions
        solution_width = 0.8 * page_width / (num_per_page // 2)
        solution_height = 0.8 * page_height / (num_per_page // 2)
        solution_margin = 0.05 * page_width  # Margin between solutions

        total_solution_width = (solution_width + solution_margin) * (num_per_page // 2) - solution_margin
        solution_spacing = (page_width - total_solution_width) / 2

        for i in range(0, num_solutions, num_per_page):
            c.showPage()
            for j in range(num_per_page):
                index = i + j
                if index < num_solutions:
                    solution_x = solution_spacing + (j % (num_per_page // 2)) * (solution_width + solution_margin)
                    solution_y = page_height - (((j // (num_per_page // 2)) % 2) * (solution_height + solution_margin) + 0.1 * page_height)
                    draw_sudoku(c, solutions[index], solution_x, solution_y)

        c.save()
        print("Solution PDF saved successfully!")


def draw_sudoku(canvas, grid, x, y):
    cell_width = 1.4224 * cm  # Cell width in inches
    cell_height = 1.4224 * cm  # Cell height in inches
    font_size = 0.5 * cm  # Decrease font size for 6x6 Sudoku

    size = len(grid)
    box_width = int(size**0.5)  # Number of cells in a row of the rectangular box
    box_height = int(size**0.5)  # Number of cells in a column of the rectangular box

    for i in range(size + 1):
        canvas.setLineWidth(0.1)  # Set line width to a smaller value for all lines
        canvas.line(x, y - i * cell_height, x + size * cell_width, y - i * cell_height)  # horizontal lines

        if i == 0 or i == size:  # Bold the outermost upper border and the outermost lower border
            canvas.setLineWidth(1)  # Set line width to a larger value for the outer borders
            canvas.line(x, y - i * cell_height, x + size * cell_width, y - i * cell_height)  # horizontal line

        if i % box_height == 0 and i > 0 and size > 4:
            canvas.setLineWidth(1)  # Set line width to a larger value for the rectangles
            canvas.line(x, y - i * cell_height, x + size * cell_width, y - i * cell_height)  # horizontal line

    for j in range(size + 1):
        canvas.setLineWidth(0.1)  # Set line width to a smaller value for all lines
        canvas.line(x + j * cell_width, y, x + j * cell_width, y - size * cell_height)  # vertical lines

        if j == 0 or j == size:  # Bold the outermost left border and the outermost right border
            canvas.setLineWidth(1)  # Set line width to a larger value for the outer borders
            canvas.line(x + j * cell_width, y, x + j * cell_width, y - size * cell_height)  # vertical line

        if j % box_width == 0 and j > 0 and size > 4:
            canvas.setLineWidth(1)  # Set line width to a larger value for the rectangles
            canvas.line(x + j * cell_width, y, x + j * cell_width, y - size * cell_height)  # vertical line

    canvas.setLineWidth(0.1)  # Set line width to a larger value for outer borders
    canvas.rect(x, y - size * cell_height, size * cell_width, size * cell_height)  # Draw the outer border

    # Draw text outside the table
    canvas.setFontSize(14)
    canvas.drawString(x, y + 0.3 * cm, "Sudoku")  # Example text

    for i in range(size):
        for j in range(size):
            cell_value = str(grid[i][j])
            if cell_value != '0':
                canvas.setFontSize(font_size)
                text_width = canvas.stringWidth(cell_value, fontName="Helvetica", fontSize=font_size)
                cell_x = x + j * cell_width + (cell_width - text_width) / 2
                cell_y = y - i * cell_height - (cell_height - font_size) / 2
                canvas.drawString(cell_x, cell_y, cell_value)


def generate_sudoku_set(size, num_puzzles):
    puzzles = []
    solutions = []

    for _ in range(num_puzzles):
        puzzle = generate_sudoku(size)
        solution = puzzle.copy()
        remove_numbers(puzzle, get_num_clues(size))  # Adjust the number of clues as per your preference
        puzzles.append(puzzle)
        solutions.append(solution)

    puzzle_filename = filedialog.asksaveasfilename(defaultextension=".pdf")
    solution_filename = filedialog.asksaveasfilename(defaultextension=".pdf")

    save_as_pdf(puzzles, solutions, puzzle_filename, solution_filename)

def get_num_clues(size):
    if size == 4:
        return 8
    elif size == 6:
        return 12  # Decrease the number of clues for 6x6 Sudoku
    elif size == 9:
        return 22  # Decrease the number of clues for 9x9 Sudoku
    else:
        return 0

root = Tk()
root.title("Sudoku Generator")
root.geometry("300x200")

size_label = Label(root, text="Select Sudoku Size:")
size_label.pack(pady=10)

size_var = IntVar()
size_var.set(4)

radio_4x4 = Radiobutton(root, text="4x4", variable=size_var, value=4)
radio_4x4.pack()

radio_6x6 = Radiobutton(root, text="6x6", variable=size_var, value=6)
radio_6x6.pack()

radio_9x9 = Radiobutton(root, text="9x9", variable=size_var, value=9)
radio_9x9.pack()

num_puzzles_label = Label(root, text="Number of Puzzles:")
num_puzzles_label.pack(pady=10)

num_puzzles_entry = Entry(root)
num_puzzles_entry.pack()

generate_btn = Button(root, text="Generate Sudoku Set", command=lambda: generate_sudoku_set(size_var.get(), int(num_puzzles_entry.get())))
generate_btn.pack(pady=10)

root.mainloop()

核心问题 #

1. 数独生成效率极低：当前solve函数按固定顺序遍历空单元格，且随机尝试数字，9x9网格下回溯次数呈指数级增长，导致程序长时间卡住。
2. 唯一解判断错误：is_unique_solution仅判断网格是否有解，而非解是否唯一，导致移除数字逻辑失效，进一步增加无效计算。

优化方案 #

1. 优化数独生成算法（采用MRV启发式）

修改solve函数，优先选择候选数最少的单元格（最少剩余值启发式，MRV），大幅减少回溯次数：

def solve(grid):
    size = len(grid)
    # 找到候选数最少的空单元格
    min_candidates = size + 1
    target_row, target_col = -1, -1
    for row in range(size):
        for col in range(size):
            if grid[row][col] == 0:
                candidates = [num for num in range(1, size+1) if is_valid(grid, row, col, num)]
                if len(candidates) < min_candidates:
                    min_candidates = len(candidates)
                    target_row, target_col = row, col
                    if min_candidates == 0:
                        return False
                    if min_candidates == 1:
                        break
        if min_candidates == 1:
            break
    if target_row == -1:
        return True  # 网格已填满
    
    # 对候选数随机排序，增加生成多样性
    candidates = [num for num in range(1, size+1) if is_valid(grid, target_row, target_col, num)]
    np.random.shuffle(candidates)
    for num in candidates:
        grid[target_row][target_col] = num
        if solve(grid):
            return True
        grid[target_row][target_col] = 0
    return False

2. 修复唯一解判断逻辑

修改is_unique_solution函数，统计解的数量，当解超过1个时立即返回False：

def count_solutions(grid):
    size = len(grid)
    for row in range(size):
        for col in range(size):
            if grid[row][col] == 0:
                count = 0
                for num in range(1, size+1):
                    if is_valid(grid, row, col, num):
                        grid[row][col] = num
                        sub_count = count_solutions(grid)
                        count += sub_count
                        grid[row][col] = 0
                        if count > 1:
                            return count
                return count
    return 1

def is_unique_solution(grid):
    temp = grid.copy()
    return count_solutions(temp) == 1

3. 优化移除数字逻辑

减少不必要的唯一解检查，优先保留能维持唯一解的空单元格：

def remove_numbers(grid, num_clues):
    size = len(grid)
    total_cells = size * size
    target_empty = total_cells - num_clues
    empty_cells = []
    
    # 先随机标记要移除的单元格
    cells = np.random.permutation(total_cells)
    for cell in cells:
        if len(empty_cells) >= target_empty:
            break
        row = cell // size
        col = cell % size
        temp = grid[row][col]
        grid[row][col] = 0
        if is_unique_solution(grid):
            empty_cells.append((row, col))
        else:
            grid[row][col] = temp

效果说明 #

优化后的代码生成9x9数独的速度会大幅提升，唯一解判断逻辑也能正确工作，避免无效计算导致的程序无响应。

内容的提问来源于stack exchange，提问作者Mostafa Abdel Mohsen