leetcode-solution/Python/0037-sudoku-solver.py at main · hogan-tech/leetcode-solution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# time complexity: O(9!^9)
# space complexity: O(1)
from collections import defaultdict
from typing import List


class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        n = len(board)

        rows, cols, boxes = defaultdict(
            set), defaultdict(set), defaultdict(set)

        for r in range(n):
            for c in range(n):
                if board[r][c] == '.':
                    continue

                digit = int(board[r][c])
                rows[r].add(digit)
                cols[c].add(digit)
                boxes[(r // 3) * 3 + c // 3].add(digit)

        def isValid(r: int, c: int, digit: int):
            boxId = (r // 3) * 3 + c // 3
            return digit not in rows[r] and digit not in cols[c] and digit not in boxes[boxId]

        def backtrack(r: int, c: int):
            if r == n - 1 and c == n:
                return True
            elif c == n:
                c = 0
                r += 1

            if board[r][c] != '.':
                return backtrack(r, c + 1)

            boxId = (r // 3) * 3 + c // 3
            for digit in range(1, n + 1):
                if not isValid(r, c, digit):
                    continue

                board[r][c] = str(digit)
                rows[r].add(digit)
                cols[c].add(digit)
                boxes[boxId].add(digit)

                if backtrack(r, c + 1):
                    return True

                board[r][c] = '.'
                rows[r].remove(digit)
                cols[c].remove(digit)
                boxes[boxId].remove(digit)

            return False

        backtrack(0, 0)


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"]
]
print(Solution().solveSudoku(board))