Bonjour,

dans un projet pour mes cours, je doit réaliser un solveur de sudoku grâce a une fonction récursive. Ce dernier ce décline en deux étapes. La premier est un solveur pour grille simple, qui ne fait pas appel a du backtracking, celui la est réussi.
Le second lui, me pose plus de problème. Le prof me demande de faire appel a du backtracking afin de pouvoir revenir sur mes pas lorsqu'une case a plusieurs possibilité.

voici comment il souhaite qu'on s'y prenne :

Nom : 122271676_824038058404816_1871014062356512482_n.jpg Affichages : 551 Taille : 123,8 Ko

voici ou j'en suis pour l'instant (j'importe une bibliothèque "sudolib" qui répertorie toutes les fonction utilisée) :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from sudolib import *
 
grille2=[[0,0,0,1,5,0,3,0,0],[0,0,1,0,0,0,7,9,5],[0,5,6,0,0,4,0,0,0],[9,0,3,0,8,0,0,0,0],[0,2,0,0,0,0,0,8,0],[0,0,0,0,3,0,1,0,4],[0,0,0,9,0,0,4,3,0],[8,9,2,0,0,0,6,0,0],[0,0,4,0,2,6,0,0,0]]
 
def sudoku2(grille) :
    if reste(grille) == 0 : # Teste d'arret
        affiche2(grille)    # si il ne reste pas de case vide la fonction s'arrete, affiche la grille et return True
        return True
    else :
 
        case = repere(grille) # definit la case à remplire
        if len(possibles(grille,case[0],case[1])) == 0 : #si la case n'a pas de solution retourn False
            return False
        else :
            poss = possibles(grille,case[0],case[1]) # cree la liste des possibilités pour une case donnée
 
            while len(poss) != 0  : # tant qu'il reste des possibilités
                grille[case[0]][case[1]] = possibles(grille,case[0],case[1])[0] # la case prend la premiere valeur possible
                test = sudoku2(grille) # verifie si le sudoku est possible pour la nouvelle grille
                if not bool(test) :
                    poss.pop(0)  # si le test est faux la premiere possibilite est retire et la grille "nettoye"
                    grille[case[0]][case[1]] = 0
                elif bool(test) :
                    poss=[]# si le sudoku est possible toutes les valeures sont retire pour pouvoir sortir de la grille
 
            return sudoku2(grille) # ré-execute la fonction avec la nouvelle grille pour enclache la recursivite
 
 
sudoku2(grille2)
voici ma bibliothèque :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
def affiche (grille):
    """affiche sous forme matricielle
0 7 0 0 0 9 4 0 1
9 6 0 1 0 0 5 0 7
0 0 0 5 0 0 0 9 0
0 0 1 0 0 0 7 6 2
0 2 4 0 0 0 3 1 0
5 3 7 0 0 0 8 0 0
0 1 0 0 0 6 0 0 0
4 0 2 0 0 1 0 7 6
7 0 6 2 0 0 0 8 0
"""
    for i in range(9):
        ligne=""
        for j in range (9) :
            ligne += str(grille[i][j])
        # A compléter
        print(ligne)
 
def affiche2 (grille):
    """affiche sous forme matricielle mis en forme avec des bordures
----------------------
|  7   |    9 |4   1 |
|9 6   |1     |5   7 |
|      |5     |  9   |
----------------------
|    1 |      |7 6 2 |
|  2 4 |      |3 1   |
|5 3 7 |      |8     |
----------------------
|  1   |    6 |      |
|4   2 |    1 |  7 6 |
|7   6 |2     |  8   |
----------------------
"""
 
    # A compléter à l'aide des caractères  - et | ainsi que de la division euclidienne %
    for i in range (9) :
        if i%3 == 0 :
            print("-------------------------")
        ligne=""
        for j in range (9) :
            if  j%3 ==0:
                ligne+="| "
            if grille[i][j] == 0 :
                ligne+= "  "
            else :
                ligne+= str(grille[i][j])+" "
        ligne+="|"
        print(ligne)
    print("-------------------------")
 
 
def ligne(grille,i):
    """retourne la liste des chiffres présents sur la ligne autres que 0
    print(ligne(grille,0))
    >>>[7, 9, 1, 4]"""
    ligne=[]
    for j in range(9) :
        if grille[i][j] != 0:
            ligne.append(grille[i][j])
    # A compléter
    return ligne
 
 
 
 
def colonne(grille,j):
    """retourne la liste des chiffres présents sur la colonne autre que 0
    print(colonne(grille,0))
    >>>[9, 5, 4, 7]"""
    colonne=[]
    for i in range (9):
        if grille[i][j] != 0 :
            colonne.append(grille[i][j])
    # A compléter
    return colonne
##print(colonne(grille,3))
 
 
def bloc(grille,i,j):
    bloc=[]
    """retourne la liste des chiffres autre que 0 présents sur le bloc contenant (i,j)
    print(bloc(grille,3,2))
    >>>[1, 2, 4, 5, 3, 7]"""
    for k in range (9) :
        for l in range(9) :
            if grille[k][l] != 0 and k//3 == i//3 and l//3 == j//3:
                bloc.append(grille[k][l])
    # A compléter
    return bloc
##print(bloc(grille,4,1))
 
 
def possibles(grille,i,j):
    """retourne la liste des chiffres possibles pour la case de coordonnées (i,j)
    print(possibles(grille,0,0))
    >>>[2, 3, 8]"""
    poss=[]
    for g in range(1,10):
        if (g not in bloc(grille,i,j)) and (g not in ligne(grille,i)) and (g not in colonne(grille,j)) :
            poss.append(g)
    # A compléter
    return poss
##print(possibles(grille,5,7),bloc(grille,5,7))
    # A compléter
 
def reste(grille):
    """retourne le nombre de cases restant à remplir"""
    n=0
    for i in range (len(grille)) :
            n+=grille[i].count(0)
    # A compléter
    return n
 
 
def repere(grille):
    """ retourne sous forme de tuple le couple (i,j), coordonnées de la case ayant le moins de valeurs possibles
print(repere(grille))
>>> (3, 0)
"""
    min=(0,0)
    minCombi = 9
    for i in range (9) :
        for j in range (9) :
            if grille[i][j] == 0:
                poss = possibles(grille,i,j)
                if len(poss)<minCombi :
                    minCombi = len(poss)
                    min=(i,j)
 
    return min


Cela fait beaucoup de code (dont surement pas mal d'inutile mais c'est ce qu'on nous demande de faire)
J'espère que quelqu'un comprendra mon problème et saura me dire pourquoi mon backtracking ne fonctionne pas

Merci d'avance !

Tom