Sudoku

def is_valid(board, row, col, num):
    # Check row and column
    for i in range(9):
        if board[row][i] == num&nbs***bsp;board[i][col] == num:
            return False

    # Check 3x3 box
    start_row, start_col = 3 * (row // 3), 3 * (col // 3)
    for i in range(start_row, start_row + 3):
        for j in range(start_col, start_col + 3):
            if board[i][j] == num:
                return False

    return True

def solve_sudoku(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                for num in range(1, 10):
                    if is_valid(board, i, j, num):
                        board[i][j] = num
                        if solve_sudoku(board):
                            return True
                        board[i][j] = 0
                return False
    return True

def print_sudoku(board):
    for row in board:
        print(" ".join(map(str, row)))

# Read input
board = []
for _ in range(9):
    row = list(map(int, input().split()))
    board.append(row)

# Solve and print
solve_sudoku(board)
print_sudoku(board)

def value(x, y):
    i, j = x // 3, y // 3
    grid = [m[i * 3 + r][j * 3 + c] for r in range(3) for c in range(3)]
    row_val = m[x]
    col_val = list(zip(*m))[y]
    return {1, 2, 3, 4, 5, 6, 7, 8, 9} - set(grid) - set(row_val) - set(col_val)


def sudoku(pos):
    if not pos:  # 填完了
        res.append([' '.join(map(str, i)) for i in m])
    else:
        x, y = pos[0]
        val = value(x, y)
        if val:
            for v in val:
                m[x][y] = v
                sudoku(pos[1:])
                m[x][y] = 0  # 回溯

m = [list(map(int, input().split())) for i in range(9)]
pos = [(x, y) for y in range(9) for x in range(9) if not m[x][y]]
res = []
sudoku(pos)
print('\n'.join(res[0]))

g = [] # 
for i in range(9):
    g.append(list(map(int, input().split())))
# print(g) 

row = [[],[],[],[],[],[],[],[],[]]
col = [[],[],[],[],[],[],[],[],[]] 
three = [[],[],[],[],[],[],[],[],[]] 
# print(row)
# print(col)
# print(three)
fill = []
for r in range(9):
    for c in range(9):
        cur = g[r][c]
        if cur == 0:
            # 要填的数 
            fill.append((r,c))
            continue
        
        # row 行的数
        row[r].append(cur)
        # lie 列的数
        col[c].append(cur)
        # three 的数 
        # print("r // 3 , c % 3: ", r // 3 , c // 3)
        # print("r,c, ",r, c, 2 * (r  // 3) + c // 3 )
        three[3 * (r  // 3) + c // 3].append(cur) 

# print(row)
# print(col)
# print(three)
# print(fill)

def fun(index):
    # for r, c in fill:
    
    if index == len(fill):
        return True 
    # print(">>>>:",index)
    # print("--:", index, fill[index])
    r, c = fill[index]
    # print("r, c", r,c )


    for i in range(1,10):
        if i in row[r]&nbs***bsp;i in col[c]&nbs***bsp;i in three[ 3 * ( r // 3) + c // 3] :
            continue 
        else:
            # print("res:", i)
            g[r][c] = i
            row[r].append(i)
            col[c].append(i)
            three[ 3 * ( r // 3) + c // 3 ].append(i)
            if fun(index + 1):
                return True 
            row[r].remove(i)
            col[c].remove(i)
            three[3 * ( r // 3) + c // 3 ].remove(i)

# print("fill:", fill)
for i in range(len(fill)):
    # print("***:", i)
    fun(i) 


for i in range(9):
    for j in range(9):
        print(g[i][j], end=" ")
    
    print()

#借鉴了一下评论里大佬的方法。然后用例是跑不过的自己判断过没过就行了
def check(ans,n,m,i):
    if i not in ans[n] and i not in list(zip(*ans))[m]:
        return True
    return False
def sudoKu(res):
    if len(res)==0:
        return True
    n,m=res[0]
    for i in range(1,10):
        if check(ans,n,m,i):
            ans[n][m]=i
            if sudoKu(res[1:]):#这里之前想的是没有做判断 所以递归有问题
                return True
            ans[n][m]=0#自己写到这了不晓得怎么回溯 原来这么简单
    return False

ans=[]
resq=[]
for i in range(9):
    ans.append(list(map(int,input().split())))
for i in range(9):
    for j in range(9):
        if ans[i][j]==0:
            resq.append((i,j))

sudoKu(resq)
for i in ans:
    print(" ".join(list(map(str,i))))

def getMatrixMissingValues(r,c,a):
    #向下取整
    r = r // 3
    c = c //3
    alist = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
    for rr in range(3):
        row = r*3 + rr
        for cc in range(3):
            col = c*3 + cc
            val = a[row][col]
            try:
                alist.remove(val)
            except:
                continue
    return  alist  



def checkRowRepeat(r,a):
    dic = {}
    l = []
    # print(a)
    for i in range(9):
        if a[r][i] =='0':
            l.append((r,i))
            continue
        if a[r][i] in dic.keys():
            # print('重复！  a[{}][{}] = {}   {}'.format(r,i,a[r][i],dic))
            return False,[(r,i)]
        else:
            dic[a[r][i]] = ''
        # print(dic)

    return  True,l

def checkColRepeat(c,a):
    dic = {}
    l= []
    for i in range(9):
        if a[i][c] =='0':
            l.append((i,c))
            continue
        if a[i][c] in dic.keys():
            return False,[(i,c)]
        else:
            dic[a[i][c]] = ''
    return  True,l





#单点检查，本矩阵是否需要填充
def checker(r,c,a,q):
    #压如队列
    # print('加入队列({},{})'.format(r,c))
    q.append((r,c))
    if a[r][c] != '0':
        return True
        
    available = getMatrixMissingValues(r, c,a)
    # print('a[{}][{}] 可选值 {}'.format(r, c, available))

    
    for v in available:
        # 赋值 检查 横向 检查纵向
        a[r][c] = v
        # print('尝试a[{}][{}]={}'.format(r,c,v))
        # 行里是否有重复，无重复，本次取值可行，查看行里有没有空白
        flag, empty = checkRowRepeat(r,a)
        # print('尝试a[{}][{}]={}  row {}  {}'.format(r,c,v,flag,empty))

        if flag:
            if len(empty) > 0:
                loc = empty[0]
                re = checker(loc[0],loc[1],a,q)
                if not re:
                    a[r][c] = '0'  # 还原
                    # print('row尝试a[{}][{}] 可能值时，都不满足'.format(loc[0], loc[1], v))
                    continue
        else:
            # 设为该值后，行内不满足条件，尝试下一个值
            a[r][c] = '0' #还原
            # print('尝试a[{}][{}]={} 失败 row'.format(r, c, v))
            continue 

        flag1, empty1 = checkColRepeat(c,a)
        # print('尝试a[{}][{}]={}  col {}  {}'.format(r, c, v, flag1, empty1))

        if flag1:
            if len(empty1) > 0:
                loc = empty1[0]
                re = checker(loc[0],loc[1],a,q)
                if not re:
                    a[r][c] = '0'  # 还原
                    # print('col  尝试a[{}][{}] 可能值时，都不满足'.format(loc[0], loc[1], v))
                    continue
        else:
            # 设为该值后，行内不满足条件，尝试下一个值
            a[r][c] = '0' #还原
            # print('尝试a[{}][{}]={} 失败 col'.format(r, c, v))
            continue

        if flag and flag1:
            return True

    if a[r][c] == '0':
        #上层取值不合理， 释放队列中所有该节点后的合法赋值
        while True:
            try:
                tmp = q.pop()
                if tmp == (r,c):
                    q.append((r,c))
                    break
                else:
                    # print(r,c,'清除赋值 ',tmp)
                    a[tmp[0]][tmp[1]] = '0'
            except:
                break
        return False

    return True







    
a = []
    
while True:
    try:
        tmp = input().split(' ')
        a.append(tmp)
    except:
        break
        
queue = []
for r in range(9):
    for c in range(9):
        # 为0 需要填充
        if a[r][c] == '0':
            # print('------------loc : ',r,c)
            checker(r,c,a,queue)
        else:
            continue
            
for i in a:
    print(' '.join(i))