## Exemple

# Exemple 1
sudoku1 = [[0 for _ in range (9)] for _ in range (9)]

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


# Exemple 2

sudoku2 = [[0 for _ in range (9)] for _ in range (9)]

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




def a_remplir(sudoku) :
    list = []
    for i in range(9) :
        for j in range(9) :
            if sudoku[i][j] == 0 :
                list.append((i,j))
    return list























def verif_ligne(sudoku,i) :
    dic = {}
    for j in range(0,9) :
        elt = sudoku[i][j]
        if elt != 0 :
            if elt in dic :
                return False
            else :
                dic[elt] = True
    return True

def verif_ligne2(sudoku,i) :
    for j in range(0,9) :
        for jp in range (j+1,9) :
            elt = sudoku[i][j]
            if elt != 0 and elt == sudoku[i][jp] :
                return False

    return True











def verif_col(sudoku,j) :
    dic = {}
    for i in range (0,9) :
        elt = sudoku[i][j]
        if elt != 0 :
            if elt in dic :
                return False
            else :
                dic[elt] = True
    return True

def indice_carre(i,j) :
    I = i//3
    J = j//3
    rep = []
    for k in range(0,3) :
        for l in range(0,3) :
            rep.append((I*3 + k,J*3+l))
    return rep

def verif_carre(sudoku,i,j) :
    pos = indice_carre(i,j)
    dic = {}
    for k,l in pos :
        elt = sudoku[k][l]
        if elt != 0 :
            if elt in dic :
                return False
            else :
                dic[elt] = True
    return True


def verif_sudo(sudoku) :
    for i in range (9) :
        if not verif_ligne(sudoku,i) :
            return False

    for j in range (9) :
        if not verif_col(sudoku,j) :
            return False

    for i in range (3) :
        for j in range (3) :
            if not verif_carre(sudoku,i*3,j*3) :
                return False
    return True





## Recherche exhaustive


def incrementer(l_choix) :
    ind = 0
    while l_choix[ind] == 9 :
        l_choix[ind] = 1
        ind += 1
    l_choix[ind] += 1

















def exhaustif_sudoku(sudoku) :
    a_remp = a_remplir(sudoku)
    l_choix = [1 for elt in a_remp]
    for ind in range(len(a_remp)) :
        i,j = a_remp[ind]
        sudoku[i][j] = l_choix[ind]


    while not verif_sudo(sudoku) :
        incrementer(l_choix)
        for ind in range(len(a_remp)) :
            i,j = a_remp[ind]
            sudoku[i][j] = l_choix[ind]

    return a_remp, l_choix





## Retour sur trace

def initialiser_choix(l) :
    dic = {}
    for i,j in l :
        dic[(i,j)] = 1
    return dic

def remonter(sudoku,l_fait,l_choix,dic) :
    i,j = l_fait.pop()
    sudoku[i][j] = 0
    l_choix.append((i,j))
    dic[(i,j)] += 1
    if dic[(i,j)] == 10 :
        dic[(i,j)] = 1
        remonter(sudoku,l_fait,l_choix,dic)




def backtracking_sudoku(sudoku) :
    l_choix = a_remplir(sudoku)
    dic_choix = initialiser_choix(l_choix)
    l_fait = []
    while (len(l_choix) != 0) :
        i,j = l_choix.pop()
        sudoku[i][j] = dic_choix[(i,j)]
        l_fait.append((i,j))
        bool1 = verif_ligne(sudoku,i)
        bool2 = verif_col(sudoku,j)
        bool3 = verif_carre(sudoku,i,j)
        if not (bool1 and bool2 and bool3) :
            remonter(sudoku,l_fait,l_choix,dic_choix)
    return dic_choix



## Optimisation

def nombre_vide_voisine(sudoku) :
    l_choix = a_remplir(sudoku)
    rep = {}
    for (i,j) in l_choix :
        rep[(i,j)] = 0
        for k in range(9) :
            if k != i :
                if sudoku[k][j] == 0 :
                    rep[(i,j)] += 1
        for l in range(9) :
            if l != j :
                if sudoku[i][l] == 0 :
                    rep[(i,j)] += 1
        for k in range(3) :
            for l in range (3) :
                kp = (i//3)*3 + k
                lp = (j//3)*3 + l
                if kp != i and lp != j :
                    if sudoku[kp][lp] == 0 :
                        rep[(i,j)] += 1
    return rep


## Algorithme main

def trouver_case(sudoku) :
    for i in range(9) :
        for j in range(9) :
            if sudoku[i][j] == 0 :
                possible = [True for _ in range (9)]
                for k in range(9) :
                    chi = sudoku[k][j]
                    if chi != 0 :
                        possible[chi-1] = False
                for l in range(9) :
                    chi = sudoku[i][l]
                    if chi != 0 :
                        possible[chi-1] = False
                vois = indice_carre(i,j)
                for (k,l) in vois :
                    chi = sudoku[k][l]
                    if chi != 0 :
                        possible[chi-1] = False
                somme = 0
                rep = -1
                for ind in range (len(possible)) :
                    if possible[ind] :
                        somme += 1
                        rep = ind+1
                if somme == 1 :
                    return i,j, rep


def resolution(sudoku) :
    l_choix = a_remplir(sudoku)
    for _ in range (len(l_choix)) :
        i,j, rep = trouver_case(sudoku)
        sudoku[i][j] = rep