回溯数独仅适用于 Python 3

Question

我正在努力完成这项工作。它得到了几位数字，但我不知道问题出在哪里。我已经阅读了各种其他代码，虽然我了解它们是如何工作的，但我不知道我的代码的问题出在哪里。我尝试了很多东西，这是我最接近的。

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

    [0, 0, 5,   0, 3, 0,  1, 0, 0],
    [0, 7, 0,   5, 0, 1,  0, 3, 0],
    [0, 0, 3,   0, 9, 0,  8, 0, 0],

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

def p(board):
    for i in board:
        print(i)

def find(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                return row, col
    return 1

def check_horizontal(board, row, number):
    for i in range(0, 9):
        if board[row][i] == number:
            return False
    return True

def check_vertical(board, col, number):
    for i in range(0, 9):
        if board[i][col] == number:
            return False
    return True

def check_sqaure(board, row, col, number):
    a = int(row / 3)
    b = int(col / 3)
    for i in range(a * 3, a * 3 + 3):
        for j in range(b * 3, b * 3 + 3):
            if board[i][j] == number:
                return False
    return True

def check_all(board, row, col, number):
    if check_horizontal(board, row, number) and check_vertical(board, col, number) and check_sqaure(board, row, col,number):
        return True

def play(board):
    if find(board) == 1:
        return 1
    row, col = find(board)
    for i in range(1, 10):
        if check_all(board, row, col, i):
            board[row][col] = i
            if play(board) == 1:
                return board
            else:
                if check_all(board, row, col,board[row][col] + 1):
                    board[row][col] = board[row][col] + 1   
play(board)
p(board)

这是输出：

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

正确的结果是：

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

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

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

Answer 1

我发现您的 play 函数存在一些问题。

第一个问题是你没有正确回溯。回溯意味着当你放弃当前的部分解决方案时，你需要将你一直在测试的板上的 space 标记为未知。如果递归找不到解决方案，您目前有一些奇怪的代码会尝试跳转。我认为你应该删除这些行：

else:
    if check_all(board, row, col,board[row][col] + 1):
        board[row][col] = board[row][col] + 1

相反，如果循环找不到任何解决方案，则需要重置。所以把它放在代码的末尾，在循环之外：

board[row][col] = 0

另一个问题是关于 return 值应该来自 play 的逻辑有些混乱。在基本情况下，您正在 returning 标记值 1，您稍后的递归代码会对此进行检查。但是后面的代码如果认为它从递归中得到了解决方案，将 return board 而不是标记值。您需要选择其中之一并与之保持一致！另一方面，当您从函数末尾掉下来时，您依赖 None 的默认 return 值来指示失败。您可能应该通过添加 return None.

来明确 return 值

这是我的做法，return董事会：

def play(board):
    if find(board) == 1:
        return board            # first change, return the board here!
    row, col = find(board)
    for i in range(1, 10):
        if check_all(board, row, col, i):
            board[row][col] = i
            if play(board) is not None: # second change, check for a non-None value, not == 1
                return board
    board[row][col] = 0         # third change, do proper backtracking (replaced three lines)
    return None                 # fourth change, be explicit about our return value on failure

你调用 find 两次的地方仍然有一个小缺点，但这不会使代码出错，只是比必要的慢了一点。您可以通过更改前几行来改进它：

coords = find(board)
if coords == 1:
    return board
row, col = coords

我也更喜欢使用 None 作为失败 find 的标志，但这更多的是品味问题，而不是真正错误或低效的问题。

回溯数独仅适用于 Python 3

Backtracking Sudoku only sort of works in Python 3

python

algorithm

sudoku

backtracking

python-3.x