Python 中数独的回溯算法

Question

我正在尝试使用回溯来制作数独求解器。当我手动完成代码时，它运行得很好，但是当我运行它时，我的返回解决方案中会出现空单元格。我花了如此荒谬的时间试图修复它，但我什至无法弄清楚它到底出了什么问题。我相当确定我检查细胞溶液的功能是正确的。代码如下：

import numpy as np
board = np.array([[0, 0, 0, 8, 4, 0, 0, 0, 3],
[0, 7, 5, 0, 0, 0, 0, 0, 0],
[0, 4, 3, 0, 0, 6, 0, 0, 0],
[0, 0, 7, 0, 0, 8, 4, 9, 0],
[0, 0, 0, 9, 3, 1, 0, 0, 0],
[0, 5, 2, 7, 0, 0, 8, 0, 0],
[0, 0, 0, 2, 0, 0, 3, 4, 0],
[0, 0, 0, 0, 0, 0, 6, 2, 0],
[2, 0, 0, 0, 7, 3, 0, 0, 0]])
#check if input is viable solution for a cell
def isSolution(row, col, n):
#return 0 for false (not a possible solution)
#return 1 for true (possible solution)
a = 0
for i in range(0,9):
if(board[row,i] == n):
a += 1
if(board[i,col] == n):
a += 1
h = (1 - (2 * ((row % 3) != 0)))
i = (1 - (2 * ((col % 3) != 0)))
j = (2 - (row % 3)**2)
k = (2 - (col % 3)**2)
if(board[row + h, col + i] == n):
a += 1
elif(board[row + h, col + k] == n):
a += 1
elif(board[row + j, col + i] == n):
a += 1
elif(board[row + j, col + k] == n):
a += 1
if(a == 0):
return 1
else:
return 0
def solve():
for row in range(0, 9):
for col in range(0,9):
if(board[row,col] == 0):
for n in range(1, 10):
if(isSolution(row, col, n) == 1):
board[row,col] = n
print(board)
solve()
board[row,col] = 0
return

#main
solve()

如果可以的话，请帮忙，我正在努力在 python 方面做得更好，感觉我在这里碰壁了

Answer 1

Thierry Lathuille 的扩展评论

def solve():
for row in range(0, 9):
for col in range(0,9):
if(board[row,col] == 0):
for n in range(1, 10):
if(isSolution(row, col, n) == 1):
board[row,col] = n
# print(board)
if (board != 0).all():
raise StopIteration
solve()
board[row,col] = 0
return

#main
try:
solve()
except StopIteration:
print(board)