Concours blanc d'informatique : fonction "solutionSudoku"

from copy import deepcopy

def rechercheDansListe(elt,L):
    for i in range(0,len(L)):
        if L[i]==elt:
            return(i)
    return(-1)

def caseSuivante(pos):
    x,y = pos[0],pos[1]
    if y==8:
        y=0
        x+=1
    else:
        y+=1
    return([x,y])

def casePrecedente(pos):
    x,y = pos[0],pos[1]
    if y==0:
        y=8
        x=x-1
    else:
        y=y-1
    return([x,y])

def caseLibreSuivante(pos,L):
    suivante=caseSuivante(pos)
    if suivante[0]==9 or L[suivante[0]][suivante[1]]==0:
        return(suivante)
    else:
        return(caseLibreSuivante(suivante,L))

def caseLibrePrecedente(pos,L):
    prec=casePrecedente(pos)
    if prec[0]==-1 or L[prec[0]][prec[1]]==0:
        return(prec)
    else:
        return(caseLibrePrecedente(prec,L))


def ligne(L,i,j):
    chiffre=[]
    for k in range(0,9):
        if L[i][k]>0 and k!=j:
            chiffre.append(L[i][k])
    return chiffre

def colonne(L,i,j):
    chiffre=[]
    for k in range(0,9):
        if L[k][i]>0 and k!=j:
            chiffre.append(L[k][i])
    return chiffre

def carre(L,i,j):
    icoin = 3*(i//3)
    jcoin=3*(j//3)
    chiffre=[]
    for x in range(icoin, icoin+3):
        for y in range(jcoin,jcoin+3):
            if (L[x][y] > 0 and (x,y)!=(i,j)):
                chiffre.append(L[x][y])
    return chiffre


def conflit(L,i,j):
    return(ligne(L,i,j) + colonne(L,i,j) + carre(L,i,j))

def chiffresOk(L,i,j):
    listeOk=[]
    listeConf=conflit(L,i,j)
    for k in range(1,10):
        if k not in listeConf:
            listeOk.append(k)
    return(listeOk)

def solutionSudoku(L):
        M=deepcopy(L)
        pos = caseLibreSuivante([-1,8],L)

        compteur=0

        while pos[0]>=0 and pos[0]<=8 and compteur<5:
            compteur+=1

            Elt = M[pos[0]][pos[1]]
            M[pos[0]][pos[1]] = 0
            listeChiffresOk=chiffresOk(M,pos[0],pos[1])
            if len(listeChiffresOk)==0:
                pos=caseLibrePrecedente(pos,L)
            elif Elt==0:
                M[pos[0]][pos[1]]=listeChiffresOk[0]
                pos = caseLibreSuivante(pos,L)
            else:
                i = rechercheDansListe(Elt,listeChiffresOk)
                if i==len(listeChiffresOk)-1:
                    pos=caseLibrePrecedente(pos,L)
                else:
                    M[pos[0]][pos[1]]=listeChiffresOk[i+1]
                    pos=caseLibreSuivante(pos,L)
            print(compteur)
            print("pos",pos)
            print("elt",Elt)
            print("listeChiffresOk",listeChiffresOk)
            print("M0",M[0])
            print("------")
        return(M)

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

####################################
""" La suite est ce qu'il se passe en exécutant "solutionSudoku(L)" (avec les print) :
1
pos [0, 7]
elt 0
listeChiffresOk [1, 7]
M0 [2, 5, 4, 1, 9, 6, 3, 0, 0]
------
2
pos [0, 8]
elt 0
listeChiffresOk [8]
M0 [2, 5, 4, 1, 9, 6, 3, 8, 0]
------
3
pos [0, 7]
elt 0
listeChiffresOk []
M0 [2, 5, 4, 1, 9, 6, 3, 8, 0] # Le corrigé donne [2,5,4,1,9,6,3,0,0]
------
4
pos [0, 3]
elt 8
listeChiffresOk [8]
M0 [2, 5, 4, 1, 9, 6, 3, 0, 0] # Le corrigé donne [2,5,4,0,9,6,3,0,0]
------
5
pos [0, 7]
elt 1
listeChiffresOk [1, 7]
M0 [2, 5, 4, 7, 9, 6, 3, 0, 0]
"""