题解 | #Sudoku#

有点又长又臭的味道
剪纸版dfs，先预先算出0的位置和该位置可用的数字，可以省点时间

while True:
    try:
        sudo = []
        for _ in range(9):
            sudo.append(list(map(int, input().split())))
            
        def check_raw(i, j):
            tmp = [0] * 10
            for c in range(9):
                if sudo[i][c] != 0:
                    tmp[sudo[i][c]] += 1
                    if tmp[sudo[i][c]] > 1:
                        return False
            return True
        
        def check_col(j, idx):
            tmp = [0] * 10
            for i in range(9):
                if sudo[i][idx] != 0:
                    tmp[sudo[i][idx]] += 1
                    if tmp[sudo[i][idx]] > 1:
                        return False
            return True
        
        def check_box(i, j):
            row = i // 3
            col = j // 3
            tmp = [0] * 10
            for r in range(row * 3, row * 3 + 3):
                for c in range(col * 3, col * 3 + 3):
                    if sudo[r][c] != 0:
                        tmp[sudo[r][c]] += 1
                        if tmp[sudo[r][c]] > 1:
                            return False
            return True
        
        def get_0():
            zero = []
            for i in range(9):
                for j in range(9):
                    if sudo[i][j] == 0:
                        zero.append([i,j])
            return zero
        
        def get_zero_avai(pos):
            tmp = [0]
            cnt = [0] * 10
            for i in range(9):
                tmp.append(sudo[pos[0]][i])
                tmp.append(sudo[i][pos[1]])
            row = pos[0] // 3
            col = pos[1] // 3
            for r in range(row * 3, row * 3 + 3):
                for c in range(col * 3, col * 3 + 3):
                    tmp.append(sudo[r][c])
            return list(set(range(10)) - set(tmp))

        def dfs(sudo, zero):
            for i in range(len(zero)):
                x, y = zero[i]
                cur_avai = get_zero_avai(zero[i])
                for num in cur_avai:
                    sudo[x][y] = num
                    if check_raw(x,y) and check_col(x,y) and check_box(x,y) and dfs(sudo, zero[1:]):
                        return True
                    sudo[x][y] = 0
                return False
            return True
        
        zero = get_0()
        dfs(sudo,zero)
        for i in range(9):
            sudo[i] = [str(c) for c in sudo[i]]
            print(' '.join(sudo[i]))
    except:
        break