题解 | Sudoku

import sys
from collections import deque

#判断i，j中能否填入数字a
def judge(mat,i,j,a):   
    #判断行\列是否满足
    row = []
    col = []
    for k in range(9):
        row.append(mat[i][k])
        col.append(mat[k][j])
    if a in row or a in col:
        return 0
    #判断当前九宫格是否满足
    ri,ci=i//3,j//3
    nine = []
    for k in range(ri*3,(ri+1)*3):
        for p in range(ci*3,(ci+1)*3):
            nine.append(mat[k][p])
    if a in nine:
        return 0 
    return 1

def solve(mat,todo,i):
    # 当遍历完todo，返回1
    if i >= len(todo):
        return True
    # 对于当前的todo，遍历数字1~9
    for num in range(1,10):
        #如果数字可以填上
        if judge(mat,todo[i][0],todo[i][1],num):
            #那就填上
            mat[todo[i][0]][todo[i][1]]=num
            #填上之后，如果后面的todo都可以正确填上，那就返回1
            if solve(mat,todo,i+1):
               return True
            #否则当前数字回溯为0
            mat[todo[i][0]][todo[i][1]]=0
    # 全部数字都不行，返回0，让前面的todo换成其他数字
    return False

mat = []

for line in sys.stdin:
    a =list(map(int,line.split()))  
    mat.append(a)
todo=[]
for i in range(9):
    for j in range(9):
        if mat[i][j]==0:
            todo.append([i,j])

solve(mat,todo,0)

# 输出答案
for row in mat:
    print(' '.join(map(str, row)))