def possible(sudoku, x, y, n):
"""验证值的可能性"""
for i in range(9):
if sudoku[i][y] == n:
return False
for j in range(9):
if sudoku[x][j] == n:
return False
# 所在小九宫格第一个元素的坐标
grid_x = x // 3 * 3
grid_y = y // 3 * 3
for i in range(3):
for j in range(3):
xx = grid_x + j
yy = grid_y + i
if sudoku[xx][yy] == n:
return False
return True
def solve(sudoku):
"""数独求解
深度优先穷举法
"""
for x in range(9):
for y in range(9):
if sudoku[x][y] == 0:
for n in range(1, 10):
if possible(sudoku, x, y, n):
sudoku[x][y] = n
solve(sudoku)
sudoku[x][y] = 0
return
for row in sudoku:
print(row)
if __name__ == '__main__':
sudoku = [
[0, 9, 0, 1, 0, 0, 3, 7, 8],
[0, 0, 0, 7, 0, 9, 0, 0, 0],
[0, 1, 0, 4, 0, 8, 0, 0, 6],
[0, 0, 0, 2, 0, 0, 6, 5, 9],
[0, 0, 0, 0, 4, 3, 0, 0, 0],
[0, 5, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 2, 3, 5, 1, 7, 0, 0],
[0, 6, 0, 8, 9, 0, 5, 0, 2],
[0, 0, 0, 0, 0, 2, 8, 0, 0]
]
solve(sudoku)