题解 | #Sudoku#

# dfs深度优先算法

#判断填了数之后,是否符合数独规则
def isValue(board, x, y):
    # 检查已经填入的坐标是否和列中有的元素相等
    for i in range(9):
        if i != x and board[i][y] == board[x][y]:
            return False
    # 检查已经填入的坐标是否和行中有的元素相等
    for j in range(9):
        if j != y and board[x][j] == board[x][y]:
            return False

    # 检查每个3X3粗线宫是否符合（粗线框内只有1~9）
    m, n = 3 * (x // 3), 3 * (y // 3)  # 这里求出的是3x3网格的左上角的坐标
    for i in range(3):
        for j in range(3):
            if(i + m != x or j + n != y) and board[i + m][j + n] == board[x][y]:
                return False 
    return True

#深度优先算法    
def dfs(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                for k in '123456789':  # 从里面选择一个
                    board[i][j] = int(k)#尝试设置一个值
                    if isValue(board, i, j) and dfs(board):
                        return True
                    # 尝试结束,退回设置
                    board[i][j] = 0
                # 都不行，说明上次的数字不合理
                return False
    # 全部遍历完,没有0了，返回True
    return True

while True:
    try:
        board = []
        for i in range(9):
            board.append(list(map(int, input().split())))

        dfs(board)
        for i in range(9):
            print(' '.join(list(map(str, board[i]))))
    except:
        break