Bonjour a tous,
D'abord je voudrais m'excuser pour l'absence d'accents dans mon message, mais j'ai un probleme avec mon clavier en ce moment...
Je suis en train de programmer un solveur de grilles Sudoku. Il propose a l'utilisateur de remplir les elements de la grille a resoudre puis de la soumettre a la recherche de la solution.
Actuellement, je suis en train de reflechir a l'algorithme de resolution. Un ami specialiste m'a dit ceci:
J'ai donc traduit ses dires en ceci:Les cases vides du tableaux contiennent 0 par defaut. Le programme va parcourir le tableau et va essayer dans chaque case, de mettre un chiffre entre 1 et 9. Si 1 ne marche pas, il essaie 2 sur la meme case, ainsi de suite jusqu'a 9.
S'il arrive a mettre un chiffre dans la case, il passe a la suivante, jusqu'a arriver a la derniere.
S'il n'arrive a mettre aucun chiffre dans la case, il ajoute 1 au contenu de la case precedente, 2 si la valeur obtenue dans la case precedente ne marche pas, ainsi de suite jusqu'a ce que l'addition atteigne 9. S'il arrive a modifier le chiffre dans la case precedente, il essaie de nouveau d'en caser un dans la case sur laquelle il est, sinon il cherche a modifier le chiffre de 2 cases en arriere, ainsi de suite jusqu'a atteindre la premiere case. Ce jusqu'a ce qu'il arrive a trouver une valeur acceptable dans une case, a ce moment-la, il "repart en avant".
S'il n'arrive pas (plus) a mettre de chiffre dans la premiere case, le programme s'arrete en disant qu'il n'y a pas de solution.
Ici, les fonctions doublon_xxx servent a reperer si oui ou non il y a un doublon dans la colonne, la ligne ou la region (en Sudoku les carres 3x3 du tableau, dans lesquels il ne peut pas y avoir 2 fois le meme chiffre). Je suis sur et certain que ces fonctions remplissent correctement leur role, l'erreur etant dans la partie publiee.
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 public static void resolution (int x, int y, int n, int[][] matrice) { for (int i=n; n<10; i++) { if ((!doublon_ligne(x,n,0,9, matrice))&&(!doublon_colonne(y,n,0,9, matrice))&&(!doublon_carre(x,y,n,matrice))) { matrice[x][y]=n; } } } public static void resolution_totale (int[][] matrice) { for (int x=0; x<9; x++) { for (int y=0; y<9; y++) { resolution(x,y,1,matrice); if (matrice[x][y]==0) { if (x>0) { resolution(x-1,y,matrice[x-1][y]+1,matrice); while (!((x!=9)&&(y!=9)&&(matrice[x][y]!=0))) { resolution_totale(matrice); } } else { if (y>0) { resolution(8,y-1,matrice[8][y-1]+1,matrice); while (!((x!=9)&&(y!=9)&&(matrice[x][y]!=0))) { resolution_totale(matrice); } } else { System.out.println("Pas de solution"); } } } } } }
resolution sert a resoudre le contenu d'une seule case et resolution_totale, le tableau entier.
J'ai deja modifie pas mal de fois mon code, mais je n'arrive plus a trouver mon erreur.
Je m'en remets donc a vous chers specialistes du forum, afin de savoir si j'ai traduit correctement le francais ci-dessus en algo, et si d'ailleurs, ce principe est juste pour la resolution d'une grille de Sudoku.
Quand je fais tourner cet algo: Le PC mouline et rien ne s'affiche.
Mais je pense savoir que c'est parce que je lui demande de recommencer a resoudre le tableau depuis le debut a chaque fois qu'il modifie une valeur, ce qui est tres long.
Vrai?
Merci d'avance pour votre aide.
Partager