为什么我的回溯算法不起作用并生成包含重复条目的方块？

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

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

当我运行算法时提供的板子我得到：

[[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 方法，这是不允许的！

很明显我犯了错误，但我看不出哪里...

有什么想法吗？

Answer 1

原因是feasibleMove这部分有错误：

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

迭代应该基于 row 和 col，而不是基于 x 和 y。而当你从board中读出值时，你应该使用i和j作为索引。现在，您正在看板上的同一个单元格 9 次。

row = (x // 3) * 3
col = (y // 3) * 3

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

但是，您的算法速度太慢，无法在合理的时间内解决难题。您应该通过以下方式改进您的算法：

不要实时查找空白单元格。相反，将它们收集到一个队列中，然后从那里弹出它们（并在回溯时将它们放回去）
与其检查值是否对单元格有效，不如保持领先一步，并跟踪每个单元格的哪些值仍然有效（在 set 中）。在算法的一开始就初始化它。
放置值时会更新受影响的单元格集

最后两点似乎没有任何好处，因为它只是将扫描行、列和框的工作转移到算法中的另一个时刻，但好处就在这里：

为了使递归树变窄，请优先考虑剩余可能值最少的单元格，最好只有一个。你可以使用python的heapq，它应该应用于我在第一点中提到的队列。

我把实现留给你，因为这不是你的问题。无论如何，网上有很多工作示例。

为什么我的回溯算法不起作用并生成包含重复条目的方块？

Why is my backtracking algorithm not working and producing squares with duplicated entries?

python

algorithm

recursion

backtracking

python-3.x