题解 | #Sudoku#

DFS

class Solution:
    def getAns(self, board):
        def dfs(pos):
            nonlocal valid
            if pos == len(spaces):
                valid = True
                return
            i, j = spaces[pos]
            for digit in range(9):
                if line[i][digit] == column[j][digit]==block[i // 3][j // 3][digit] == False:
                    line[i][digit] = column[j][digit]= block[i // 3][j // 3][digit] = True
                    board[i][j] = str(digit+1)
                    dfs(pos + 1)
                    line[i][digit] = column[j][digit]=block[i // 3][j // 3][digit] = False
                if valid:
                    return
        line = [[False]*9 for _ in range(9)]
        column = [[False]*9 for _ in range(9)]
        block = [[[False]*9 for _ in range(3)] for __ in range(3)]
        valid = False
        spaces= []
        for i in range(9):
            for j in range(9):
                if board[i][j] == '0':
                    spaces.append((i,j))
                else:
                    digit = int(board[i][j]) - 1
                    line[i][digit] = column[j][digit]=block[i // 3][j // 3][digit] = True
        dfs(0)

while True:
    try:
        board = []
        for i in range(9):
            board.append(input().split())
        test = Solution()
        test.getAns(board)
        for i in range(9):
            print(" ".join(board[i]))
    except:
        break