时间戳

首页 > 解决方案 > 如何优化涉及数独求解器回溯的函数运行速度

python - 如何优化涉及数独求解器回溯的函数运行速度

问题描述

最近我正在整理和调试我的函数，它是一个回溯数独求解器，并意识到它无法完成更大的数独板的运行：

我的代码：

def areLegalValues(values: list):
    if len(values) in [1,4,9,16,25]:
        for value in values:
            if value <= len(values):
                if value != 0 and values.count(value)>1:
                    return False
            else:
                return False
        return True
    return False

def isLegalRow(board: list, row: list):
    compareList = [ ]

    for r in range(len(board)):

        if r == row:

            for c in range(len(board[0])):
                #print(board[r][c])
                compareList.append(board[r][c])
    return areLegalValues(compareList)

def isLegalCol(board: list, col: list):
    compareList = [ ]
    for r in range(len(board)):
        for c in range(len(board[0])):
            if c == col:
                compareList.append(board[r][c])
                #print(compareList)
    return areLegalValues(compareList)

def isLegalBlock(board: list, block: list):
    compareList = [ ]
    N = int((len(board))**(1/2))
    blockRowNumber = int(block//N)
    blockColNumber = int(block%N)
    for row in range(blockRowNumber*N, blockRowNumber*N+N):
        #print(row)
        for col in range(len(board[0])):
            if col in range(blockColNumber*N, blockColNumber*N+N):
                #print(board[row][col])
                compareList.append(board[row][col])
                # print(compareList)
    return areLegalValues(compareList)

def isLegalSudoku(board: list):
    boardLength = len(board)
    for row in range(len(board)):
        if isLegalRow(board,row) != True:
            return False
        for col in range(len(board[0])):
            if isLegalCol(board,col) != True:
                return False
    for block in range(boardLength):
        if isLegalBlock(board, block) != True:
            return False
    return True

def solveSudoku(board: list):
    """takes in a sudoku board and solves the board through use of backtracking
    and returns the dectructively changed board"""
    checkZeroes = True
    for row in range(len(board)):
        for col in range(len(board[0])):
            if board[row][col] == 0:
                checkZeroes = False
    
    if checkZeroes == True:
        return board
    else:
        for row in range(len(board)):
            for col in range(len(board[0])):
                if board[row][col] == 0:
                    for number in range(1,len(board)+1):
                        board[row][col] = number
                        if isLegalSudoku(board) == True:
                            solution = solveSudoku(board)
                            if solution != None:
                                return solution
                        board[row][col] = 0
                    return None

我想知道如何优化/简化它，以便它运行得更快并且可以处理更大的输入大小而无需花费很长时间？

谢谢

标签： python

解决方案

正如评论中提到的其他人，您可能需要重新考虑算法，因为回溯非常慢。

话虽如此，从技术上讲，有一些方法可以稍微优化它。例如，您可以预先计算缺少的数字（除了根据网格的大小在网格中具有一定数量的每个值），而不是尝试每个零的每个数字，并计算有多少每一个都不见了。然后，一旦你用完一个数字的分配数量，if 将不再尝试将它放在网格中。

例如，网格

[
[0,2,3,4],
[0,4,1,0],
[2,3,4,1],
[4,1,0,3],
[

缺少 1 1、 13和 2 2s。您不必尝试放置任何 4，前 1 或 2 个数字只有 3 个选项可供选择，然后再减少。对于少数缺失值，这将是一个重大改进，而对于较大的网格，这将是一个次要的改进。

您可以进行的另一项改进是法律委员会检查。无需检查行、列和区域的实际值，您可以简单地将它们相加并检查它们是否都等于正确的值（从 1 到棋盘大小的总和）。例如，在尺寸为 9 的板上，所有行、列和区域的总和应为 45。在尺寸为 4 的板上，它们的总和应为 10。这种方法的一个缺点是它不区分板是否有任何非法移动与如果它只是缺少一个条目。因此，这只能用于检查没有剩余零的板。

推荐阅读