Discussion :

[clem_alain]

Bonjour tout le monde,
Dans cadre de mon projet de développement d'une "petite" application de résolution de Sudoku, je suis tombé sur cette solution écrite en Python :
https://github.com/foxxpy/Algorithmi...%20de%20Sudoku
Cet algorithme fonctionne à merveille et j'avais l'ambition de le transcrire en C# (langage dans lequel je développe mon application), je me dois de reconnaître que je n'y suis pas arrivé la preuve avec le code ci-après.
Le cœur de mon problème est cette portion du code Python :

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
def solve():
    global grid
    for y in range(9):
        for x in range(9):
            if grid[y][x] == 0:
                for n in range(1,10):
                    if n_valide(y, x, n):
                        grid[y][x] = n
                        solve()
                        grid[y][x] = 0
                return
    for i in range(9):
        for j in range(9):
            print(grid[i][j], end="")
        print()
    exit(0)

Et en particulier la sortie de la boucle for n in range(1,10).
Voici ma tentative de transcription :

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
        static void solve()
        {
            bool numberInGrid;
            for (int l = 0; l < 9; l++)
            {
                for (int c = 0; c < 9; c++)
                {
                    if (grid[l, c] == 0)
                    {
                        int valeur;
                        numberInGrid = true;
                        for (int val = 1; val < 10; val++)
                        {
                            valeur = val;
                            numberInGrid = IsInGrid(l, c, val);
                            if (!numberInGrid)
                            {
                                grid[l, c] = val;
                                solve();
                                grid[l, c] = 0;
                            }
                        }
                        return;
                    }
                }
            }
        }

Comme vous devez vous douter cela ne fonctionne pas la ligne grid[l, c] = 0; est SYSTEMATIQUEMENT appelée alors qu'elle ne devrait l'être qu'en cas d'impossibilité de placer un chiffre dans une case, ce qui provoque (normalement et c'est le cas dans le code Python) un dépilage des valeurs précédemment déposées pour revenir à une situation propre et repartir sur d'autres valeurs !
Je tourne en rond depuis plusieurs jours, j'ai bien sûr essayé de suivre l'exécution en déboguant, en simplifiant le jeu d'essai, en notant manuellement les différentes étapes, mais rien n'y fait je n'arrive pas à trouver la solution :-(
En fait je ne vois plus rien, j'ai donc besoin d'un regard extérieur !
Aussi je vous serais très reconnaissant si vous pouviez éclairer ma lanterne :-)

[wiztricks]

Salut,

Pourquoi poser une question de codage C# dans un forum Python?

- W

[umfred]

Tu as regardé la vidéo associé au code ?

La problématique pour toi c'est que l'affichage de la solution se fait aussi dans solve et ensuite le programme quitte sans repasser par cette ligne grid[x,y]=0le code python lui aussi passerait par cette ligne mais après l'affichage de la solution sauf que le exit(0) fait quitter le programme (remplace exit(0) par print("fin") et ajoute un print("passe à 0") juste après solve(), tu verras l'affichage du résultat, l'affichage de "fin" puis 7 affichages de 'passage à 0" en utilisant l'exemple de la vidéo (7 correspondant au nombre de 0 initial)

Il faut rajouter une condition de sortie dans le code pour ne pas passer par la réinitialisation

[clem_alain]

Salut,

Pourquoi poser une question de codage C# dans un forum Python?

- W

Bonjour,
Tout simplement parce que je pensais que des développeurs Python pouvaient aussi avoir des compétences en C# et surtout qu'ils auraient une expertise sur la récursivité de ce langage que je ne maîtrise pas du tout, même si des langages j'en ai vu pas mal.
Autre raison, si j'avais posté côté C#, il est aussi possible (probable ?) que quelqu'un m'aurait demandé pourquoi poser une question Python dans le forum C# :-))

[clem_alain]

Tu as regardé la vidéo associé au code ?

La problématique pour toi c'est que l'affichage de la solution se fait aussi dans solve et ensuite le programme quitte sans repasser par cette ligne grid[x,y]=0le code python lui aussi passerait par cette ligne mais après l'affichage de la solution sauf que le exit(0) fait quitter le programme (remplace exit(0) par print("fin") et ajoute un print("passe à 0") juste après solve(), tu verras l'affichage du résultat, l'affichage de "fin" puis 7 affichages de 'passage à 0" en utilisant l'exemple de la vidéo (7 correspondant au nombre de 0 initial)

Il faut rajouter une condition de sortie dans le code pour ne pas passer par la réinitialisation

Bonsoir,
Merci pour la réponse, j'ai bien essayé de mettre une condition de sortie avec un return mais ce return provoque le dépilage de la récursivité, j'ai même tenté le throw new Exception() mais rien n'y fait, en fait je me demande s'il y a un moyen de vider la pile de la récursivité.
Je vais chercher de ce côté, et probablement poser une question chez les C# ;-)

[wiztricks]

j'ai bien essayé de mettre une condition de sortie avec un return

La condition de sortie est que la grille est remplie (ce que le code teste par l'absence de 0 dans la grille).
Et dans ce cas, on affiche la grille et on sort via exit() (qui existe aussi en C#).

Pour une sortie moins violente, il faut revoir l'algo.

- W

[clem_alain]

Bon,
J'ai suivi ton conseil et voici mon code :

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
 
        static void solve(bool numberInGrid)
        {
            for (int l = 0; l < 9; l++)
            {
                for (int c = 0; c < 9; c++)
                {
                    if (grid[l, c] == 0)
                    {
                        int valeur;
                        numberInGrid = true;
                        for (int val = 1; val < 10; val++)
                        {
                            valeur = val;
                            numberInGrid = IsInGrid(l, c, val);
                            if (!numberInGrid)
                            {
                                grid[l, c] = val;
                                solve(numberInGrid);
                                grid[l, c] = 0;
                            }
                        }
                        return;
                    }
                }
            }
            if (!numberInGrid )
            {
                display();
                Console.ReadKey();
                Environment.Exit(0);
            }
        }

Alors ça fonctionne, par contre (AMHA) ce n'est pas très propre, du coup je me demande si un bon while de derrière les fagots ne serait pas plus pertinent, cela va m'obliger à gérer une pile (comme au bon vieux temps), mais ce sera quand même plus propre non ?

[wiztricks]

Alors ça fonctionne, par contre (AMHA) ce n'est pas très propre, du coup je me demande si un bon while de derrière les fagots ne serait pas plus pertinent, cela va m'obliger à gérer une pile (comme au bon vieux temps), mais ce sera quand même plus propre non ?

Je ne vois pas en quoi cela n'est pas "très propre": (avec python) exit génère une exception qu'on peut gérer et on peut toujours remplacer cet exit par le retour d'un booléen qu'on teste pour savoir si on dépile ou si on continue.
=> inutile de sortir du programme pour tester la grille suivante.

- W

[Sve@r]

Bonjour

Alors ça fonctionne, par contre (AMHA) ce n'est pas très propre, du coup je me demande si un bon while de derrière les fagots ne serait pas plus pertinent, cela va m'obliger à gérer une pile (comme au bon vieux temps), mais ce sera quand même plus propre non ?

Il n'y a pas de "plus propre/moins propre". Un while n'est qu'un outil qui permet de créer une boucle. Si la boucle se justifie, alors le while se justifie. Si elle ne se justifie pas...
Accessoirement il n'est pas besoin de récursivité (ni de pile qui n'est qu'un simulateur de récursivité) pour résoudre un sudoku. Celui-ci se résout par l'association de 2 techniques

• l'énumération : tu testes chaque chiffre de 1 à 9 sur une case. Si un seul chiffre convient (c'est à dire que tous les autres sont refusés pour une raison ou une autre), alors c'est le bon. Puis tu passes à la case suivante
• positionnement : tu prends le 1 et tu le testes sur chaque case de la ligne (colonne, carré). S'il ne va qu'à une seule place, alors c'est sa place. Puis tu passes au chiffre suivant

Généralement (sauf malchance), chaque technique aura positionné au-moins un chiffre ce qui permettra alors de la relancer dans une itération suivante (et effectivement là le while prend son sens).

Et enfin si malchance (parfois ça arrive qu'une position particulière amène une espèce de blocage où aucune de ces deux techniques ne marche plus) là on peut passer en récursif. Mais là on est dans une position bien avancée dans laquelle le récursif devient possible.

PS: Il y a aussi une 3° technique mais pas évidente à programmer : les couples. S'il y a 2 cases qui n'acceptent que les 2 mêmes chiffres (exemple le 3 et le 7) et qu'une 3° case accepte aussi le 3 et le 7 plus un autre (exemple le 5) alors comme le 3 et le 7 ne peuvent aller que sur les deux premières, la 3° ne peut alors avoir que le dernier chiffre (ici le 5).

[umfred]

moi je te propose de vérifier le nombre de 0 dans la grille juste après l'appel à solve(), et si il n'y a pas de 0, de sortir de la fonction
je met le code complet issu de la vidéo avec les modifications (j'ai ajouté une fonction pour compter l'occurrence d'une valeur dans la grille)
l'utilisation de l'exit(0) empêche la fonction d'être utilisée dans un autre contexte (graphique par exemple) vu que ça fait sortir du programme.

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
 import numpy as np
 
grid = [[1,2,3,4,5,6,7,8,9],
        [4,5,6,7,8,9,1,2,3],
        [0,8,9,0,2,3,4,5,6],
        [0,1,2,3,4,5,6,7,8],
        [3,4,5,6,7,8,0,1,2],
        [6,0,8,9,1,2,3,4,5],
        [8,9,1,2,3,4,5,6,7],
        [2,3,4,0,6,7,8,9,1],
        [5,6,7,8,9,1,2,3,0]]
 
def n_valide(y, x, n):
    """Détermine si un nombre n peut être mis sur une case à la colonne x et à la ligne"""
    global grid
    #On détermine si le nombre est valide sur sa ligne
    for x0 in range(len(grid)):
        if grid[y][x0] == n:
            return False
 
    #On détermine si le nombre est valide sur sa colonne
    for y0 in range(len(grid)):
        if grid[y0][x] == n:
            return False
 
    x0 = (x//3) * 3
    y0= (y//3) * 3
    #On détermine si le nombre est valide dans sa sous-grille 3x3
    for i in range(0,3):
        for j in range(0,3):
            if grid[y0+i][x0+j] == n:
                return False
    return True
 
def gcount(val):
    global grid
    c=0
    for i in range(len(grid)):
        c=c+grid[i].count(val)
    return c
 
def solve():
    global grid
    for y in range(9):
        for x in range(9):
            if grid[y][x] == 0:
                for n in range(1,10):
                    if n_valide(y, x, n):
                        grid[y][x] = n
                        solve()
                        if gcount(0)==0 : return
                        print("passage à 0")
                        grid[y][x] = 0
                return
 
 
# je "désactive" la partie affichage et sortie du code source 
#    for i in range(9):
#        for j in range(9):
#            print(grid[i][j], end="")
#        print()
#    print("fin")
#    exit(0)
 
solve() #appel de la fonction de résolution
#affichage
for i in range(9):
    for j in range(9):
        print(grid[i][j], end="")
    print()
print("fin")

Je te laisse faire la retranscription en C#

[wiztricks]

moi je te propose de vérifier le nombre de 0 dans la grille juste après l'appel à solve(), et si il n'y a pas de 0, de sortir de la fonction

Le nombre de zéros n'a aucune importance, ce qu'on cherche côté condition de fin est de savoir s'il n'y a plus de zéros.
Et s'il n'y a plus de zéro, le code ne prend pas la branche "if grid[y][x] == 0:" et ira dans le block qui affiche la grille et effectue l'exit.
On peut remplacer cet exit par un return True qu'on propagera au retour de l'appel récursif à solve dans la boucle (par exemple).
Ce qui donne un solve de la forme:

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():
    # global grid                 
    for y in range(9):
        for x in range(9):
            if grid[y][x] == 0:
                for n in range(1,10):
                    if n_valide(y, x, n):
                        grid[y][x] = n
                        if solve(): # propagate.
                           return True
                        grid[y][x] = 0
                return False
    return True

l'utilisation de l'exit(0) empêche la fonction d'être utilisée dans un autre contexte (graphique par exemple) vu que ça fait sortir du programme.

Avec Python, exit lève l'exception SystemExit qui se gère très bien:

Code :

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

1
2
3
4
5
6
7
8
9
>>> def f():
...     exit()
...
>>> try:
...     f()
... except SystemExit:
...     print ('exit caught')
...
exit caught

- W