讨论/《深度优先搜索》 - 练习:数独/
《深度优先搜索》 - 练习:数独
共 1 个回复
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        ci = lambda i, j: i // 3 * 3 + j // 3
        row , col , cel = [[512] * 9 for _ in range(3)]
        empty = []
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    empty.append((i, j))
                else:
                    n = 1 << int(board[i][j]) - 1
                    row[i] |= n
                    col[j] |= n
                    cel[ci(i,j)] |= n
        N = len(empty)
        def dfs(pos):
            if pos == N:
                return True
            i, j = empty[pos]
            for k, v in enumerate(bin(row[i]|col[j]|cel[ci(i,j)])[3:]):
                if v == '0':
                    n = 1 << (8-k)
                    board[i][j] = str(9-k)
                    row[i] |= n
                    col[j] |= n
                    cel[ci(i,j)] |= n
                    if dfs(pos + 1):  return True
                    row[i] &= ~n
                    col[j] &= ~n
                    cel[ci(i,j)] &= ~n
        dfs(0)