我使用递归和回溯创建了我认为是简单的数独求解器。我的代码运行了,但问题是输出始终是原始的数独。我认为发生的事情是我正确地解决了数独问题,但是在解决了最后一个网格之后,我的代码将具有解决方案,但是由于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])