为什么我的回溯算法不起作用，并产生重复条目的正方形？

Question

嗨，我正在尝试使用回溯来解决Sudoku Puzzle。

board = [[0, 0, 0, 7, 0, 0, 0, 0, 0],
         [1, 0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 4, 3, 0, 2, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0, 6],
         [0, 0, 0, 5, 0, 9, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 4, 1, 8],
         [0, 0, 0, 0, 8, 1, 0, 0, 0],
         [0, 0, 2, 0, 0, 0, 0, 5, 0],
         [0, 4, 0, 0, 0, 0, 3, 0, 0]]

def findBlank(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i,j)
    return False

def feasibleMove(board, coordinate, number):
    x, y = coordinate
    #check row
    for i in range(9):
        if board[x][i] == number and y != i:
            return False
    #check column
    for i in range(9):
        if board[i][y] == number and x != i:
            return False
    #check box
    row = coordinate[0] // 3
    col = coordinate[1] // 3

    for i in range(x * 3, x * 3 + 3):
        for j in range(y * 3, y * 3 + 3):
            if board[row][col] == number and (i, j) != coordinate:
                return False

    return True

def solver(board):
    blankCell = findBlank(board)
    if not blankCell:
        return True
    else:
        row, col = blankCell

    for i in range(1, 10):
        if feasibleMove(board, (row, col), i):
            board[row][col] = i

            if solver(board):
                return True

            board[row][col] = 0

    return False

我编写了一个函数来返回空白值（如果存在），这里0表示空白。另一个用于测试将数字放置在棋盘中特定位置是否有效的功能（基于Sudoku规则），另一个用于实现回溯以实际解决难题的功能。

使用运行算法时提供的电路板，我得到了：

[[2, 1, 3, 7, 4, 5, 6, 8, 9],
 [1, 3, 4, 2, 5, 6, 8, 9, 7],
 [5, 6, 9, 4, 3, 8, 2, 7, 1],
 [7, 5, 8, 1, 2, 4, 9, 3, 6],
 [4, 8, 7, 5, 6, 9, 1, 2, 3],
 [3, 2, 5, 6, 9, 7, 4, 1, 8],
 [9, 7, 6, 3, 8, 1, 5, 4, 2],
 [6, 9, 2, 8, 1, 3, 7, 5, 4],
 [8, 4, 1, 9, 7, 2, 3, 6, 5]]

似乎在逐列和逐行的基础上工作。但是3x3平方不正确。

例如以左上角的正方形为准>>

[[2, 1, 3],
 [1, 3, 4],
 [5, 6, 9]]
这具有重复的条目，例如3，并且每个数字1-9也不精确地包含一次。

基于我的feasibleMove方法，不应该这样做！

显然我犯了一个错误，但是我看不到哪里...

有什么想法吗？

[嗨，我正在尝试使用回溯来解决数独难题。板= [[0，0，0，7，0，0，0，0，0]，[1，0，0，0，0，0，0，0，0]，[0，0，0， 4，3，0，2，0，0]，[0，0，0，0，0，...

Answer 1

原因是feasibleMove的这一部分有错误：