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]

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 ?

[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# :-))