Leetcode 37. Sudoku Solver - 程程下班學

編寫一個程序，通過填充空白單元格來解決數獨難題。數獨解法必須滿足以下所有規則：

每行中的每個數字 1-9 都必須恰好出現一次。
每個數字 1-9 必須在每一列中恰好出現一次。
在網格的 9 個 3×3 子框中，每個數字 1-9 都必須恰好出現一次。
‘。’ 字符表示空單元格。

Python

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def valid_move(r, c, n):
            for i in range(9):
                if board[i][c]==n: return False
                if board[r][i]==n: return False
                if board[3*(r//3)+i//3][3*(c//3)+i%3]==n: return False
            return True
        
        def backtrack():
            for r in range(9):
                for c in range(9):
                    if board[r][c]!=".": continue
                    for n in "123456789":
                        if valid_move(r, c, n):
                            board[r][c] = n
                            if backtrack(): return True
                            board[r][c] = "."
                    return False
            return True
        backtrack()

Python

相關