sudoku solver失败中的回溯

Question

我正在用Python编写一个数独求解器，它接受一个部分填充的板，并使用回溯和前向检查来填充其余部分并解决难题。前向检查是指每次为空白单元格赋值时，检查其行、列和框中未赋值的“邻居”在赋值后是否仍有非空域。

为了表示我的board（dimensitions：N x N board with P x Q box)，我使用了一个2D列表，其中每个条目的形式为[value,[domain]]，其中value是为单元格分配的编号（如果未分配则为0)，domain是使数独游戏保持一致的单元格的可能值。

我相信我的递归做错了什么，但不知道是什么。函数总是失败并返回false。下面是我的递归求解函数的一部分，预处理代码被删除了。如果有必要，我可以发布整个函数及其助手函数。

def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
    ###some preprocessing here to check if puzzle is solved and find next empty cell if not

    vals = board[row][col][1] #domain/possible values for the empty cell
    for num in vals:
        #if num doesn't violate the row, col, and box sudoku constraints
        if constraintCheck(row, col, num, P, N, Q, board):
            #make copy of cell's domain for backtracking
            tempDomain = copy.deepcopy(board[row][col][1])

            board[row][col][0] = num        #assign num to the cell

            #remove num from domains of neighbors,
            #if an empty domain results after removing num, 
            #return False and the original board,
            #else return True and the updated board
            noEmptyDomains, board = propagate_fc(board, N, P, Q, row, col, num)
            if noEmptyDomains:
                board[row][col][1] = [num]  #update domain to be num and then recurse
                if fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
                    return True
                #backtrack -- reset value and domain of assigned cell
                board[row][col][1] = tempDomain
                board[row][col][0] = 0
            else:
                board[row][col][0] = 0
    return False

编辑：更多代码和试用Blckknght的解决方案

def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
    if time.clock() >= timeout:
        return "timeout"

    while row < N and board[row][col][0] != 0: #find next blank
        if col == N-1:
            row = row + 1
            col = 0
        else:
            col = col + 1

    if row == N: #solved
        return True

    for num in vals:
        if constraintCheck(row, col, num, P, N, Q, board):
            board[row][col][0] = num
            noEmptyDomains, new_board = propagate_fc(board, N, P, Q, row, col, num) # new var
            if noEmptyDomains:
                new_board[row][col][1] = [num]   # this doesn't modify board, only new_board
                if fc_recursive_solve(new_board, N, P, Q, row, col, outputFile, timeout):
                    return True
            board[row][col][0] = 0   # the only thing that's required to backtrack
    return False

def propagate_fc(board, N, P, Q, row, col, num):
    origBoard = copy.deepcopy(board)
    #row propagate
    for x in range(N):
        if board[x][col][0] == 0:
            if num in board[x][col][1]:
                board[x][col][1].remove(num)
        if len(board[x][col][1]) == 0:
            return False, origBoard #domain is empty; return original board

    #col propagate
    for y in range(N):
        if board[row][y][0] == 0:
            if num in board[row][y][1]:
                board[row][y][1].remove(num)
        if len(board[row][y][1]) == 0:
            return False, origBoard #domain is empty

    #box propagate
    rDiv = row/P
    cDiv = col/P
    for i in range((rDiv * P), ((rDiv + 1) * P)):
        for j in range((cDiv * Q), ((cDiv + 1) * Q)):
            if board[i][j][0] == 0:
                if num in board[i][j][1]:
                    board[i][j][1].remove(num)
            if len(board[i][j][1]) == 0:
                return False, origBoard #domain is empty

    return True, board #success; return board with updated domains

Answer 1

如果您正在进行回溯，您需要能够将您的板的状态返回到以前的状态。您当前的代码不能这样做。propagate_fc函数以不容易撤消的方式修改board。

由于我认为没有一种简单的方法可以逆转propagate_fc的逻辑，所以我建议更改求解器的设计，使其复制板，并且在将其传递到进一步的递归步骤之前只修改副本。如果副本没有导致解决方案，可以扔掉它，而不是试图编写回溯代码来修复它。

（我肯定可以追溯，只是不清楚跟踪变化的好方法是什么，而且对这个答案来说，弄清楚它是太多的工作了。）

无论如何，以下是我对求解器修改版本的建议：

def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
    if time.clock() >= timeout:
        return "timeout"

    while row < N and board[row][col][0] != 0: #find next blank
        if col == N-1:
            row = row + 1
            col = 0
        else:
            col = col + 1

    if row == N: #solved
        return board

    for num in vals:
        if constraintCheck(row, col, num, P, N, Q, board):
            new_board = copy.deepcopy(board)
            new_board[row][col][0] = num
            if propagate_fc(new_board, N, P, Q, row, col, num):
                new_board[row][col][1] = [num] 
                result = fc_recursive_solve(new_board, N, P, Q, row, col, outputFile, timeout)
                if result is not None and result != "timeout":
                    return result
        return None

以下是propagate_fc的更改版本：

def propagate_fc(board, N, P, Q, row, col, num):
    # no copying any more here

    #row propagate
    for x in range(N):
        if board[x][col][0] == 0:
            if num in board[x][col][1]:
                board[x][col][1].remove(num)
        if len(board[x][col][1]) == 0:
           return False

    #col propagate
    for y in range(N):
        if board[row][y][0] == 0:
            if num in board[row][y][1]:
                board[row][y][1].remove(num)
        if len(board[row][y][1]) == 0:
            return False

    #box propagate
    rDiv = row/P
    cDiv = col/P
    for i in range((rDiv * P), ((rDiv + 1) * P)):
        for j in range((cDiv * Q), ((cDiv + 1) * Q)):
            if board[i][j][0] == 0:
                if num in board[i][j][1]:
                    board[i][j][1].remove(num)
            if len(board[i][j][1]) == 0:
                return False

    return board #success; return new board

这里唯一真正的变化是，我不需要返回板，因为我们总是在原地修改它。只需要bool结果（来说明board是否有效）。

（我最初认为还有另一个问题，If len（...）==0检查每个块，但最终证明这并不是问题。只有当从当前board[x][y][1]列表中删除d a值（通过将这些块缩进两个级别）时，执行这些检查的性能可能会稍好一些，但这不太可能是性能上的巨大提升。）