数独问题

屏幕快照 2019-01-04 下午8.33.50.png

#例如输入为：
0 0 5 3 0 0 0 0 0
8 0 0 0 0 0 0 2 0 
0 7 0 0 1 0 5 0 0
4 0 0 0 0 5 3 0 0
0 1 0 0 7 0 0 0 6
0 0 3 2 0 0 0 8 0
0 6 0 5 0 0 0 0 9
0 0 4 0 0 0 0 3 0
0 0 0 0 0 9 7 0 0

mat=[[0]*9 for i in range(9)]
find=0

def ok(x,y):    
    global mat
    up = 3*(x//3)
    down = up+3
    left= 3*(y//3)
    right = left+3
    for i in range(9):
        if mat[x][y]==mat[i][y] and x!=i and mat[i][y]!=0:
            return False
    for j in range(9):
        if mat[x][y]==mat[x][j] and y!=j and mat[x][j]!=0:
            return False
    for row in range(up,down):
        for col in range(left,right):
            if x!=row or y!=col:
                if mat[x][y]==mat[row][col] and mat[row][col]!=0:
                    return False
    return True
    
def printMat():
    global mat
    for i in range(9):
        for j in range(9):
           print(mat[i][j],end=' ')
       print()
    
def traceback(x,y):
    global mat,find
    if find==1:
        return
    if mat[x][y]!=0:
        if y==8:
            if x==8:
                printMat()
                find=1
            else:
                traceback(x+1,y)
        else:
            if x==8:
                traceback(0,y+1)
            else:
                traceback(x+1,y)
    else:
        for i in range(1,10):
            mat[x][y]=i
            if ok(x,y):
                if y==8:
                    if x==8:
                        printMat()
                        find=1
                    else:
                        traceback(x+1,y)
                else:
                    if x==8:
                        traceback(0,y+1)
                    else:
                        traceback(x+1,y)
            mat[x][y]=0
            
                    
while True:
    try:
        inputMat=[]
        for i in range(9):
            s= input().split()
            for j in range(9):
                mat[i][j]=int(s[j])
        find=0
        traceback(0,0)
    except:
        break