编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
空白格用 '.' 表示。
1.png
一个数独。
2.png
答案被标成红色。
class Solution:
def solveSudoku(self, board):
# 由于leetcode题目要求无返回值，所以判断函数用dfs，这里来调用
self.dfs(board)
def dfs(self, board):
# 从头循环来判断每个格子里填什么数字
for x in range(9):
for y in range(9):
if board[x][y] == '.':
for nbr in '123456789':
board[x][y] = nbr
# 如果检测有效且继续向后判断有效返回True,如果False继续用其它数字循环
if self.is_valid(board, x, y) and self.dfs(board):
return True
# 如果没有找到有效的数字恢复值为"."，说明数字有问题返回False
board[x][y] = '.'
return False
# 所有的"."都填完，返回True
return True
def is_valid(self, board, x, y):
# 判断每行是重复，不含自身
for col in range(9):
if board[x][y] == board[x][col] and col != y:
return False
# 判断每列是重复，不含自身
for row in range(9):
if board[x][y] == board[row][y] and row != x:
return False
# 判断每个宫是否重复，不含自身
x_point = 3 * (x // 3)
y_point = 3 * (y // 3)
for x_move in range(3):
for y_move in range(3):
x_addr = x_point + x_move
y_addr = y_point + y_move
if x != x_addr and y != y_addr and board[x_addr][y_addr] == board[x][y]:
return False
return True
su = Solution()
board = [["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"]]
res = su.solveSudoku(board)
print(board)
