def ligne(S,i):
    return [S[i][j] for j in range(0,9) if S[i][j] != 0 ]

def colonne(S,j):
    return [S[i][j] for i in range(0,9) if S[i][j] != 0 ]

def bloc(S,i,j):
    r = []
    ligne = (i // 3) * 3
    colonne = (j // 3) * 3
    for l in  [ligne,ligne+1,ligne+2]:
        for c in [colonne,colonne+1,colonne+2]:
            if S[l][c] != 0:
                r.append(S[l][c])
    return r

def possibles(S,i,j):
    return [k for k in range(1,10) if k not in bloc(S,i,j) and k not in ligne(S,i) and k not in colonne(S,j)]

def suivante(i,j):
    if j == 8:
        i += 1
        j = 0
    else:
        j += 1

    return i,j

def solve(S,i,j):
    if i == 9:
        return True
    elif S[i][j] > 0:
        i,j = suivante(i,j)
        return solve(S,i,j)
    for k in possibles(S,i,j):
        S[i][j] = k
        a,b = suivante(i,j)
        if solve(S,a,b):
            return True
    S[i][j] = 0
    return False

S = [
        [0,1,0,0,7,8,0,0,0],
        [0,8,0,0,4,0,9,0,0],
        [0,0,5,6,0,0,0,1,0],
        [1,0,0,0,6,0,0,0,5],
        [0,4,0,9,1,5,0,7,2],
        [0,6,7,0,8,0,4,0,0],
        [0,0,0,3,0,0,1,0,0],
        [0,7,0,8,9,0,0,2,3],
        [0,0,0,0,0,4,0,0,0]
]

if solve(S,0,0):
    print(S)
