数独生成器需要很长时间才能移除瓷砖

Question

我正在尝试根据难度生成数独板。我的一切都基于这样一个事实：我不在乎它是否有一个或多个解决方案。生成完整的棋盘还可以，速度很快，但是当涉及到高级难度的消除图块时，它就变成了一场噩梦。最多可能需要 30 秒才能生成内容。

def is_valid(array, r, c, e):
    size = 3

    not_in_row = e not in array[r]
    if not not_in_row:
        return False

    not_in_column = e not in [array[i][c] for i in range(len(array))]
    if not not_in_column:
        return False

    not_in_cell = e not in [array[i][j] for i in range(int(r // size * size), int(r // size * size + size)) for j in
                            range(int(c // size * size), int(c // size * size + size))]
    if not not_in_cell:
        return False

    return True


def solve(board, r=0, c=0):
    if c == 9:
        if r == 8:
            return True
        r += 1
        c = 0

    if board[r][c] > 0:
        return Sudoku.solve(board, r, c + 1)

    for k in range(1, 10):

        if Sudoku.is_valid(board, r, c, k):
            board[r][c] = k
            if Sudoku.solve(board, r, c + 1):
                return True

        board[r][c] = 0

    return False


def remove_cells(board, cells, difficulty = Difficulty.EASY):
    n_cells = 81 - {
        Difficulty.ADVANCED: rd.randint(20, 29),
        Difficulty.INTERMEDIATE: rd.randint(30, 39),
        }.get(difficulty, rd.randint(40, 49))

    cpt = 0

    while n_cells != 0:
        i, j = cells[cpt]
        temp = board[i][j]
        board[i][j] = 0
        if Sudoku.solve(board.copy()):
            n_cells -= 1
        else:
            board[i][j] = temp
        cpt += 1

Answer 1

当您创建一个已解决的数独，然后清空一个或多个单元格时，您永远不必检查该变异板是否仍然可以解决，因为它确实可以解决。

因此，您应该从解决的数独开始，然后清除一些单元格而不进行任何检查。

其他一些备注：

• is_valid

  代码可以稍微优化一下，避免创建列表，而是使用combrehension进行迭代（使用

  all

  或

  any

  ）
• 在

  solve

  中，当当前单元格有值时，我也会避免进行递归调用：只需使用循环而不是递归查找下一个空单元格。
• 在

  solve

  中，如果您将 1..9 中的值打乱并按打乱的顺序尝试它们（如

  k

  ），平均而言，您将获得更快的解决方案。这还有一个很好的副作用，如果你在空板上运行它，你会得到一个完全随机解决的数独。

这是完成这项工作的完整代码：

import random as rd

def is_valid(array, r, c, value):
    # Some optimizations applied here:
    return (value not in array[r] 
        and all(row[c] != value for i, row in enumerate(array))
        and all(
            value not in array[i] or array[i].index(value) // 3 != c // 3
            for i in range(r - r % 3, r - r % 3 + 3) 
        ))

def solve(board, r=0, c=0):
    while r < 9: # Iterate here instead of making recursive calls
        if board[r][c] == 0:
            break
        c = (c + 1) % 9
        r += not c
    else:
        return True

    values = list(range(1, 10))
    rd.shuffle(values)  # Shuffle to get faster results on average
    for k in values:
        if is_valid(board, r, c, k):
            board[r][c] = k
            if solve(board, r + (c == 8), (c + 1) % 9):
                return True

        board[r][c] = 0

    return False


def remove_cells(board, num_cells_to_remove):
    # Get all possible cell coordinates and shuffle them
    cells = [(i, j) for i in range(9) for j in range(9)]
    # Select the desired number from them
    for i, j in rd.sample(cells, k=num_cells_to_remove):
        # If we started out with a solved board,
        #   it is not needed to see if the sudoku is solvable
        board[i][j] = 0

def print_board(board):
    for row in board:
        print(" ".join(map(str, row)))
    print()


if __name__ == "__main__":
    # Create empty board
    board = [ [0] * 9 for _ in range(9) ]
    # Randomly populate as completed, valid sudoku (solved)
    solve(board)
    print_board(board)
    
    # Remove desired number of cells:
    remove_cells(board, 50)
    print_board(board)```