1
class Solution:
2
    def solveSudoku(self, board: List[List[str]]) -> None:
3
        """
4
        Do not return anything, modify board in-place instead.
5
        """
6
        full = set("123456789")
7
        # lets keep rows, columns and boxes sets in hashmaps
8
        rows = [set() for _ in range(9)]
9
        cols = [set() for _ in range(9)]
10
        boxes = [[set() for _ in range(3)] for _ in range(3)]
11
        # and remember empty cell to fill them in
12
        empty = set()
13

14
        for i in range(9):
15
            for j in range(9):
16
                if board[i][j] == ".":
17
                    empty.add((i, j))
18
                    continue
19
                rows[i].add(board[i][j])
20
                cols[j].add(board[i][j])
21
                boxes[i // 3][j // 3].add(board[i][j])
22

23
        def options(i, j):
24
            """returns possible options for i,j intersecting options from row, col and box"""
25
            return (full - rows[i]) & (full - cols[j]) & (full - boxes[i // 3][j // 3])
26

27
        psingle = True  # did we have single option decisions in previos traverse
28
        while empty:
29
            single = False  # for single option decisions in this traverse
30

31
            for i, j in deepcopy(empty):
32
                opts = options(i, j)
33
                if len(opts) == 0:
34
                    # we've made a wrong assumption - sudoku is unsolvable
35
                    return None, None
36
                elif (
37
                    len(opts) == 2 and not psingle
38
                ):  # we have no single-option decisions so have to take an assumption
39
                    board1 = deepcopy(board)
40
                    board1[i][j] = opts.pop()
41
                    board1, empty1 = self.solveSudoku(board1)
42
                    if board1 != None:  # if solved - we're done
43
                        empty = empty1
44
                        for i, b1 in enumerate(board1):
45
                            board[i] = (
46
                                b1  # have to modify initial list, not just replace the reference
47
                            )
48
                        return board, empty
49
                if len(opts) == 1:  # hey, we have a predetermined choice. nice
50
                    single = True
51
                    board[i][j] = opts.pop()
52
                    empty.remove((i, j))
53
                    rows[i].add(board[i][j])
54
                    cols[j].add(board[i][j])
55
                    boxes[i // 3][j // 3].add(board[i][j])
56

57
            psingle = single
58

59
        return board, empty