时间戳

首页 > 解决方案 > 为数独编写回溯求解器时出错

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, row=0):
    if row == len(board):
        return board
    else:
        for col in range(len(board[row])):
            if board[row][col] == 0:
                for number in range(1, len(board)+1):
                    board[row][col] == number
                    if isLegalSudoku(board) == True:
                        solution = solveSudoku(board, row+1)
                        if solution != None:
                            return solution
                    board[row][col] == 0
        return None

测试代码：

def testSolveSudoku():
    print('Testing solveSudoku()...', end='')
    Board = [
        [1, 0, 3, 0],
        [4, 3, 0, 1],
        [2, 0, 1, 0],
        [0, 0, 4, 2]
    ]
    Sol = [
        [1, 2, 3, 4],
        [4, 3, 2, 1],
        [2, 4, 1, 3],
        [3, 1, 4, 2]
    ]
    print(solveSudoku(Board))
    assert(solveSudoku(Board) == Sol)
    print('Passed!')

*正如名字所暗示的，isLegalValues 接受一个列表，如果该列表包含合法值，则返回，也就是说，该列表不能有非零数字的重复，0 可以工作。isLegalRow 和 isLegalCol 遍历数独板并建立一个包含特定行/列值的列表并将它们插入 isLegalValues。isLegalBlock 找到板子中的块，并获取一个块号并将其插入 isLegalValues。（通过广泛的测试，这些似乎都有效）

我目前遇到的问题是，由于某种原因，我的代码完成了解决难题，但设法完成了运行。例子：

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

应该改为

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

但我一直返回上面 2 行的代码。（带 0 的那个）

似乎部分代码正在工作，因为所有被替换的值都是有效的，但回溯似乎有问题。我想知道是否有人可以指出出了什么问题，我该如何解决？

谢谢

标签： python

解决方案

基本上，我犯了一个错误，我不断地用这段代码跳过同一列中的值，并且也从未尝试解决最后一列。

解决方案：

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

这完成了任务，虽然有点慢，首先检查整个电路板是否有 0（基本情况），然后循环遍历电路板中的所有值，如果值为 0，则测试所有可能的值（合法）数字。然后它检查整个董事会是否合法，然后继续。如果有错误，它会回溯。如果没有解决方案，则返回 None。

推荐阅读