編寫一個程序，通過已填充的空格來解決數獨問題。

一個數獨的解法需遵循如下規則：

數字?1-9?在每一行只能出現一次。

數字?1-9?在每一列只能出現一次。

數字?1-9?在每一個以粗實線分隔的?3x3?宮內只能出現一次。

空白格用?'.'?表示。

一個數獨。

答案被標成紅色。

Note:

• 給定的數獨序列只包含數字?1-9?和字符?'.'?。
• 你可以假設給定的數獨只有唯一解。
• 給定數獨永遠是?9x9?形式的。

DFS

唉，一言難盡。

Code

from typing import Listclass Solution:def solveSudoku(self, board: List[List[str]]) -> None:def dfs(pos: int):nonlocal validif pos == len(spaces):valid = Truereturni, j = spaces[pos]for digit in range(9):if lines[i][digit] == columns[j][digit] == block[i // 3][j // 3][digit] == False:lines[i][digit] = columns[j][digit] = block[i // 3][j // 3][digit] = Trueboard[i][j] = str(digit + 1)dfs(pos + 1)lines[i][digit] = columns[j][digit] = block[i // 3][j // 3][digit] = Falseif valid:return lines = [[False] * 9 for _ in range(9)]columns = [[False] * 9 for _ in range(9)]block = [[[False] * 9 for _ in range(3)] for _ in range(3)]valid, spaces = False, list()for i in range(9):for j in range(9):if board[i][j] == '.':spaces.append((i, j))else:digit = int(board[i][j]) - 1lines[i][digit] = columns[j][digit] = block[i // 3][j // 3][digit] = Truedfs(0)

總結

以上是生活随笔為你收集整理的37. Sudoku Solver的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。