数独回溯擦除答案

由 发布于 pythonsudokurecursive-backtracking
 收藏

我使用递归和回溯创建了我认为是简单的数独求解器。我的代码运行了，但问题是输出始终是原始的数独。我认为发生的事情是我正确地解决了数独问题，但是在解决了最后一个网格之后，我的代码将具有解决方案，但是由于board [y] [x] = 0，当我返回递归时，我删除了通过将它从board [y] [x] = 0归零，可以在网格上正确地编号，因为在我的递归调用之后，该行紧随其后。需要board [y] [x] = 0进行回溯，但它也会擦除解决方案。我该如何解决？

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

def possible(x, y, n):
    if n in board[y]: # Check if in row
        return False
    for i in range(0, 9):
        if n == board[i][x]: # Check if in column
            return False
    y //= 3
    x //= 3
    for i in range(y*3, y*3 + 3): # Check if in squares
        for j in range(x*3, x*3 + 3):
            if n == board[i][j]:
                return False
    return True

def solution():
    for y in range(9):
        for x in range(9):
            if board[y][x] == 0: # Found an empty grid
                for n in range(1, 10):
                    if possible(x, y, n):
                        board[y][x] = n
                        solution() # Recursion here
                        board[y][x] = 0 # If no solution then reset the grid and go back
                return True

solution()

for i in range(9):
    print(board[i])
评论