Discussion :

[Tom_Co]

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 :



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

[wiztricks]

Salut,

J'espère que quelqu'un comprendra mon problème et saura me dire pourquoi mon backtracking ne fonctionne pas

Pourquoi ne pas chercher sur Internet avec les mots clefs "python sudoku backtracking" et en essayant de comprendre comment ces codes marchent essayer de mettre au point le votre?

- W

[Tom_Co]

Salut,



Pourquoi ne pas chercher sur Internet avec les mots clefs "python sudoku backtracking" et en essayant de comprendre comment ces codes marchent essayer de mettre au point le votre?

- W

salut, d'abord merci de ta réponses. J'ai déjà cherchez plusieurs solution en ligne et je n'en ai malheureusement compris aucune. je suis donc venue ici pour avoir des éclaircissement.
De plus je ne cherche pas forcement avoir des réponses toutes faite mais juste que quelqu'un puisse pointer ce qui ne va pas et me proposer des solution ou des démarches a suivre.

Encore merci

Tom

[wiztricks]

De plus je ne cherche pas forcement avoir des réponses toutes faite mais juste que quelqu'un puisse pointer ce qui ne va pas et me proposer des solution ou des démarches a suivre.

Comprendre comment est fait le code des autres est une démarche à suivre...

Après pour corriger son code, il faut commencer par exposer le problème, réduire le code pour permettre de le reproduire facilement, et faire des théories qu'on cherche à valider/infirmer. Par exemple si vous pensez que çà ne marche pas parce que telle valeur n'est pas "à jour" un "print" permet de...

- W

[Tom_Co]

Comprendre comment est fait le code des autres est une démarche à suivre...

Après pour corriger son code, il faut commencer par exposer le problème, réduire le code pour permettre de le reproduire facilement, et faire des théories qu'on cherche à valider/infirmer. Par exemple si vous pensez que çà ne marche pas parce que telle valeur n'est pas "à jour" un "print" permet de...

- W

D'accord merci pour ta réponse, je vais voir comment mettre ça en pratique.

Merci encore,
Tom

[Tom_Co]

Re-bonjour, après de nombreuses recherches et tentatives de modification/compréhension, je n'ai toujours pas trouver comment adapté le backtracking au la structure de l'algorithme demande.

En effet, j'ai bien compris le principe mais les nombreuses solutions sur internet proposent un remplissage de la grille de gauche a droite et de haute en bas. Or, dans mon cas je dois remplir la grille en déterminant les cases ayant le moins de possibilités.

J'espère que quelqu'un pourra m'aider rapidement

Merci d'avance !

Tom

[wiztricks]

Salut,

En effet, j'ai bien compris le principe mais les nombreuses solutions sur internet proposent un remplissage de la grille de gauche a droite et de haute en bas. Or, dans mon cas je dois remplir la grille en déterminant les cases ayant le moins de possibilités.

Çà change juste le choix de la case à jouer, pour le reste, c'est pareil.

Prenez le code que je trouve ici, le moteur est:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
def solve(bo):
    find = find_empty(bo)
    if not find:
        return True
    else:
        row, col = find
    for i in range(1,10):
        if valid(bo, i, (row, col)):
            bo[row][col] = i
            if solve(bo):
                return True
            bo[row][col] = 0
    return False

la case à jouer suivante est retournée par find_empty...

Si on veut que çà retourne la case qui a le moins de possibilités plutôt que la première case vide... çà ne change pas grand chose sinon que çà serait mieux (dans ce cas) de tester les possibilités plutôt que tous les entiers dans 1..9.

- W

[Tom_Co]

Salut ! Encore merci pour ta réponse si rapide.

Malheureusement elle ne m’aide pas beaucoup car même en replacement la case de l’exemple par la case que je souhaite, l’algorithme n’a pas la structure qui m’ait imposé pour le projet. C’est la qu’est mon problème, je n’arrive pas à adapté le principe de backtracking à la structure demande. J’espère avoir été assez claire et j’espère que quelqu’un saura m’aider ^^

Encore merci !

[wiztricks]

C’est la qu’est mon problème, je n’arrive pas à adapté le principe de backtracking à la structure demande.

Je vous ai suggéré de partir d'un code existant (et des explications qui vont avec) et de l'adapter... Vous revenez avec une question qui n'a ni queue ni tête...

J’espère avoir été assez claire et j’espère que quelqu’un saura m’aider

La récursivité est compliquée... Ça pompe pas mal d'énergie mentale de se plonger dans code (passablement pourri, vous débutez, ce n'est pas votre faute, mais désolé, la gamelle est loin d'être appétissante...) et vous avez pu constater que dans d'autres forums, pas grand monde ne s'est aventuré à vous répondre.

De toutes façons, ne vous prenez pas martel en tête, le professeur vous donnera une solution que vous pourrez étudier à souhait... D'ici là, si vous voulez progresser, il faudrait travailler un peu plus efficacement plutôt que de tourner en rond en attendant une aide hypothétique.

- W

[Tom_Co]

D’accord merci beaucoup pour votre aide !