編寫一個程序粹排，通過已填充的空格來解決數(shù)獨問題。
一個數(shù)獨的解法需遵循如下規(guī)則：
- 數(shù)字
1-9在每一行只能出現(xiàn)一次睦刃。 - 數(shù)字
1-9在每一列只能出現(xiàn)一次。 - 數(shù)字
1-9在每一個以粗實線分隔的3x3宮內(nèi)只能出現(xiàn)一次禾嫉。
空白格用 '.' 表示。
1.png
一個數(shù)獨蚊丐。
2.png
答案被標(biāo)成紅色熙参。
class Solution:
def solveSudoku(self, board):
# 由于leetcode題目要求無返回值，所以判斷函數(shù)用dfs麦备，這里來調(diào)用
self.dfs(board)
def dfs(self, board):
# 從頭循環(huán)來判斷每個格子里填什么數(shù)字
for x in range(9):
for y in range(9):
if board[x][y] == '.':
for nbr in '123456789':
board[x][y] = nbr
# 如果檢測有效且繼續(xù)向后判斷有效返回True,如果False繼續(xù)用其它數(shù)字循環(huán)
if self.is_valid(board, x, y) and self.dfs(board):
return True
# 如果沒有找到有效的數(shù)字恢復(fù)值為"."孽椰，說明數(shù)字有問題返回False
board[x][y] = '.'
return False
# 所有的"."都填完，返回True
return True
def is_valid(self, board, x, y):
# 判斷每行是重復(fù)凛篙，不含自身
for col in range(9):
if board[x][y] == board[x][col] and col != y:
return False
# 判斷每列是重復(fù)黍匾，不含自身
for row in range(9):
if board[x][y] == board[row][y] and row != x:
return False
# 判斷每個宮是否重復(fù)，不含自身
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)
