我有一个递归求解数独的代码,并打印出它找到的一个解. 但我想找出多种解决方案的数量. 您将如何修改代码以查找所有可能的解决方案并给出解决方案的数量? 谢谢!:)
代码:
board = [
[7,8,0,4,0,0,1,2,0],
[6,0,0,0,7,5,0,0,9],
[0,0,0,6,0,1,0,7,8],
[0,0,7,0,4,0,2,6,0],
[0,0,1,0,5,0,9,3,0],
[9,0,4,0,6,0,0,0,5],
[0,7,0,3,0,0,0,1,2],
[1,2,0,0,0,7,4,0,0],
[0,4,9,2,0,6,0,0,7]
]
def solve(bo):
find = find_empty(bo)
if not find:
return True
else:
row, col = find
for num in range(1,10):
if valid(bo, num, (row, col)):
bo[row][col] = num
if solve(bo):
return True
bo[row][col] = 0
return False
def valid(bo, num, pos):
# Check row
for field in range(len(bo[0])):
if bo[pos[0]][field] == num and pos[1] != field:
return False
# Check column
for line in range(len(bo)):
if bo[line][pos[1]] == num and pos[0] != line:
return False
# Check box
box_x = pos[1] // 3
box_y = pos[0] // 3
for i in range(box_y*3, box_y*3 + 3):
for j in range(box_x * 3, box_x*3 + 3):
if bo[i][j] == num and (i,j) != pos:
return False
return True
def print_board(bo):
for i in range(len(bo)):
if i % 3 == 0 and i != 0:
print("- - - - - - - - - - - - - ")
for j in range(len(bo[0])):
if j % 3 == 0 and j != 0:
print(" | ", end="")
if j == 8:
print(bo[i][j])
else:
print(str(bo[i][j]) + " ", end="")
def find_empty(bo):
for i in range(len(bo)):
for j in range(len(bo[0])):
if bo[i][j] == 0:
return (i, j) # row, col
return None
if __name__ == "__main__":
print_board(board)
solve(board)
print("___________________")
print("")
print_board(board)
我已经try 在Solve(Bo)函数中将返回True项更改为Return None/Delete(对于两个返回项),它将继续… 然后算法继续并找到多个解,但最终将最后找到的解中的正确数字再次填入0.这就是随后打印出的解.