数独

import sys

mat = []

for _ in range(9):
    mat.append([int(x) for x in input().split(" ")])

slots = []

s_i = [set(range(1, 10)) for _ in range(9)]
s_j = [set(range(1, 10)) for _ in range(9)]
s_c = [set(range(1, 10)) for _ in range(9)]


for i in range(9):
    for j in range(9):
        if mat[i][j] == 0:
            slots.append((i, j))
        else:
            s_i[i].remove(mat[i][j])
            s_j[j].remove(mat[i][j])
            c = (i // 3) * 3 + j // 3
            s_c[c].remove(mat[i][j])

def aux(n):
    if n == -1:
        lines = [" ".join(map(str, row)) for row in mat]
        print("\n".join(lines))
        return
    i, j = slots[n]
    c = (i // 3) * 3 + j // 3
    for num in s_i[i].intersection(s_j[j]).intersection(s_c[c]):
        s_i[i].remove(num)
        s_j[j].remove(num)
        s_c[c].remove(num)
        mat[i][j] = num
        aux(n - 1)
        s_i[i].add(num)
        s_j[j].add(num)
        s_c[c].add(num)
        mat[i][j] = 0

aux(len(slots) - 1)

def isOk(mat,i,j,num):
    #判断行中有无此数，有输出F
    if num in mat[i]:
        return False
    #判断列中有无此数，有输出F
    if num in [mat[x][j] for x in range(9)]:
        return False
    #判断所在格子里有无此数，有输出F
    ii,jj = i//3*3,j//3*3
    piece = []
    for k in range(3):
        for l in range(3):
            piece.append(mat[ii+k][jj+l])
    if num in piece:
        return False
    #剩下的情况都合法，输出T
    return True
 
def remain(mat,i,j):
    remain_list=[]
    for num in range(1,10):
        if isOk(mat,i,j,str(num)):
            remain_list.append(str(num))
    remain_list.append('0')
    return remain_list
 
def all_remain(mat):
    all_remain_list=[]
    for i in range(9):
        for j in range(9):
            if mat[i][j] == '0':
                remain_list = remain(mat,i,j)
                all_remain_list.append({'index':(i,j),'remain_list':remain_list,'remain_num':len(remain_list)})
    all_remain_list=sorted(all_remain_list,key=lambda e:e.__getitem__('remain_num'))
    return all_remain_list
 
def dfs(mat,all_remain_list,n):
    if n == len(all_remain_list):
        return mat
    else:
        (i,j) = all_remain_list[n]['index']
        for num in all_remain_list[n]['remain_list']:
            if num == '0':
                return
            if isOk(mat,i,j,num):
                mat[i][j] = num
                result = dfs(mat,all_remain_list,n+1)
                if type(result) == type(None):
                    mat[i][j] = '0'
                    continue
                else:
                    return result
            else:
                continue
 
mat=[]
for i in range(9):
    mat.append([x for x in input().split()])
mat = dfs(mat,all_remain(mat),0)
for row in mat:
    print(' '.join(row))

import sys
def isOk(mat, i, j,num):#判断填入数字是否合法
    for row in range(0,9):#遍历该列，若该数字已出现过，则不合法
        if mat[row][j] == num:
            return False
    for col in range(0,9):#遍历该行，若该数字已出现过，则不合法
        if mat[i][col] == num:
            return False
    ii = i//3
    jj = j//3
    for row in range(ii*3,ii*3+3):#遍历该位置所处的3*3矩阵，若该数字已出现过，则不合法
        for col in range(jj*3,jj*3+3):
            if mat[row][col] == num:
                return False
    return True

def dfs(mat,i,j):#深度优先遍历
    if i==9:#所有行已遍历完，则结束
        return mat
    if j==9:#所有列已遍历完，则进入到下一行
        return dfs(mat,i+1,0)
    flag = False#flag表示该行有需要填充的格子
    for col in range(j,9):#遍历该行的所有列，如果有值为0，则需要进行填充
        if mat[i][col]==0:
            flag = True
            isChange =False#ischange表示是否已进行填充
            for num in range(1,10):
                if isOk(mat,i,col,num):#找出1-9中能够合法填入的数字
                    isChange =True
                    mat[i][col] = num
                    tpp = dfs(mat,i,col+1)#将该位置填充后，该行的后续位置是否有解
                    if tpp == None:#如果后续位置无解，则将该位置重新置为0，未填充状态
                        isChange = False
                        mat[i][col] = 0
                        continue#尝试下一个数字
                    else:
                        return  tpp
            if isChange==False:#找不到合法数字进行填充
                return None
    if flag==False:#该行所有位置已填满，进入到下一行
        return dfs(mat,i+1,0)
    
while True:
    isCon = True
    mat = []
    for i in range(9):
        line = sys.stdin.readline().strip()
        if not line:
            isCon = False
            break
        line =[int(i) for i in line.split(' ')]
        mat.append(line)
    if isCon ==False:
        break
    mat = dfs(mat,0,0)
    for line in mat:
        print(' '.join(str(j) for j in line))

import sys

ALL_SET = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}
matrix = []
row_available = []
col_available = []
block_available = [[ALL_SET.copy() for _ in xrange(3)] for _ in xrange(3)]
positions = []


# print block_available

def sudoku(step=0):
    if step == len(positions):
        for i in xrange(9):
            print ' '.join(matrix[i])
        print
        return
    pos_x, pos_y = positions[step]
    block_x, block_y = pos_x / 3, pos_y / 3
    for num in row_available[pos_x].intersection(col_available[pos_y]).intersection(
            block_available[block_x][block_y]):
        matrix[pos_x][pos_y] = num
        row_available[pos_x].remove(num)
        col_available[pos_y].remove(num)
        block_available[block_x][block_y].remove(num)
        sudoku(step + 1)
        row_available[pos_x].add(num)
        col_available[pos_y].add(num)
        block_available[block_x][block_y].add(num)


for _ in xrange(9):
    input_args = sys.stdin.readline()
    row = input_args.split()
    matrix.append(row)
    row_available.append(ALL_SET - set(row))

for i in xrange(9):
    col_available.append(ALL_SET - {matrix[n][i] for n in xrange(9)})

for i in xrange(9):
    for j in xrange(9):
        if matrix[i][j] == '0':
            positions.append((i, j))
        else:
            block_x, block_y = i / 3, j / 3
            block_available[block_x][block_y].remove(matrix[i][j])

sudoku(0)