Salut à tous,
Me revoilà ! Cette fois-ci, j'ai vu dans ma feuille de TP un exercice très difficile (selon moi bien sûr, qui suis débutante) mais je voudrais m'y lancer (il n'est pas demandé de le faire pour l'instant, mais vaut mieux arriver à le coder, et surtout il faut se préparer à l'examen qui approche ).
C'est un solveur automatique de Sudoku.
Je vous copie l'exact énoncé.
"Écrivez un programme qui résout les Sudokus automatiquement à votre place !
On rappelle qu’un Sudoku est une grille de 9×9 cases, chacune contenant un chiffre de 1 à 9. Cette grille est subdivisée en 9 « régions » de 3×3 cases chacune. La grille est correctement remplie lorsque chacune des 9 lignes, colonnes et régions contient chaque chiffre une et une seule fois.
Pour résoudre une telle grille, on procédera par « retour sur trace », aussi appelé « backtracking » en anglais. C’est une méthode générale de résolution de problèmes qui consiste à essayer des combinaisons en revenant légèrement en arrière si l’une d’entre elles mène à un blocage. Pour en apprendre plus sur cette stratégie, vous pouvez lire la page Wikipédia (anglophone) http://en.wikipedia.org/wiki/Backtracking.
Le principe de cette stratégie est le suivant pour une grille de Sudoku. On commence par déterminer, depuis la grille vierge, quelles sont les cases à remplir : ce sont celles qui ne sont pas fixées (elles ne contiennent pas encore de nombre). L’algorithme va ensuite parcourir toutes ces cases, en essayant le premier chiffre possible pour la première case, puis pour la deuxième, et ainsi de suite, jusqu'à rencontrer une case où plus aucun chiffre n’est possible. Il reviendra alors à la case précédente, et essayera le chiffre suivant. De même, si aucun chiffre n’est plus possible, il reviendra encore à la case d’avant, et ce jusqu'à trouver une case qu’il est possible de remplir. Une fois que toutes les cases ont été remplies, la grille est résolue.
En pratique, voilà donc comment ce principe est appliqué. L’algorithme travaille sur une case à remplir et effectue les actions suivantes :
1. On cherche le prochain chiffre que l’on peut placer dans cette case en respectant les règles.
2. Si ce chiffre existe, on le place dans la case et on passe à la case à remplir suivante.
3. S’il n’y a plus de chiffre supérieur au chiffre en cours plaçable dans la case, on remet cette case à 0 (pour repartir du départ aux prochains essais), et on passe à la case à remplir précédente.
Les cases à remplir sont initialisées à 0, et on répète ces actions tant que la case sur laquelle on passe est une case valide. Si on essaye de passer à la case suivante et qu’il n’en reste plus, la grille est résolue. Si on essaye de passer à la case précédente et qu’il n’en reste plus, la grille n’est pas résoluble.
Pour pouvoir trouver quelle est la case à remplir suivante ou précédente, on commence par calculer au début de l’algorithme une grille de booléens qui indique dans chaque case si elle est fixée ou non. Cette grille n’est pas modifiée au cours de l’algorithme, on peut donc s’en servir pour retrouver la case à remplir qui suit ou qui précède une case donnée.
Le problème a été découpé pour vous en plusieurs fonctions de taille réduite. Laissez-vous guider par le code pour le résoudre. Pour que vous puissiez tester vos fonctions, les fonctions grid et solvedGrid renvoient respectivement une grille d’exemple et cette grille résolue. Vous avez également à votre disposition une fonction qui formate une grille dans une chaîne de caractère pour pouvoir l’afficher de façon plus claire.
Bon courage !"
J'ai trouvé grid et solvedGrid dans les fichiers sources.
Voilà grid :
Et voilà solvedGrid :
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 public static int [] [] grid() { int [] [] grid = { {5, 3, 0, 0, 7, 0, 0, 0, 0}, {6, 0, 0, 1, 9, 5, 0, 0, 0}, {0, 9, 8, 0, 0, 0, 0, 6, 0}, {8, 0, 0, 0, 6, 0, 0, 0, 3}, {4, 0, 0, 8, 0, 3, 0, 0, 1}, {7, 0, 0, 0, 2, 0, 0, 0, 6}, {0, 6, 0, 0, 0, 0, 2, 8, 0}, {0, 0, 0, 4, 1, 9, 0, 0, 5}, {0, 0, 0, 0, 8, 0, 0, 7, 9} }; return grid; }
Pour compléter, on a également ceci :
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 public static int [] [] solvedGrid() { int [] [] res = { {5, 3, 4, 6, 7, 8, 9, 1, 2}, {6, 7, 2, 1, 9, 5, 3, 4, 8}, {1, 9, 8, 3, 4, 2, 5, 6, 7}, {8, 5, 9, 7, 6, 1, 4, 2, 3}, {4, 2, 6, 8, 5, 3, 7, 9, 1}, {7, 1, 3, 9, 2, 4, 8, 5, 6}, {9, 6, 1, 5, 3, 7, 2, 8, 4}, {2, 8, 7, 4, 1, 9, 6, 3, 5}, {3, 4, 5, 2, 8, 6, 1, 7, 9}, }; return res; }
Autant vous dire que malgré tout ça, j'ai du mal !
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 /** * Renvoie une chaîne de caractère représentant une grille * formatée pour l'affichage, par exemple : * 5 3 4 | 6 7 8 | 9 1 2 * 6 7 2 | 1 9 5 | 3 4 8 * 1 9 8 | 3 4 2 | 5 6 7 * -------+-------+------ * 8 5 9 | 7 6 1 | 4 2 3 * 4 2 6 | 8 5 3 | 7 9 1 * 7 1 3 | 9 2 4 | 8 5 6 * -------+-------+------ * 9 6 1 | 5 3 7 | 2 8 4 * 2 8 7 | 4 1 9 | 6 3 5 * 3 4 5 | 2 8 6 | 1 7 9 */ public static String strGrid(int [] [] grid) { String s = "\n"; String x; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (grid[i][j] == 0) { x = "_"; } else { x = "" + grid[i][j]; } s += x + " "; if (j % 3 == 2 && j < 8) { s += "| "; } } s += "\n"; if (i % 3 == 2 && i < 8) { s += "-------+-------+------\n"; } } return s; } public static void main(String [] args) { int [] [] grid = grid(); int [] [] res = solvedGrid(); solve(grid); System.out.println("Résultat obtenu :"); System.out.println(strGrid(grid)); System.out.println("Résultat attendu :"); System.out.println(strGrid(res)); } }
J'ai également un autre petit guide (c'est vraiment du pas-à-pas, c'est pour ça que je poste dans débuter ^^)... Je suis un peu allée fouiller sur internet, mais généralement les programmes trouvés sont beaucoup trop complexes pour mon niveau de débutante !), il faudrait renvoyer une grille de booléens de taille 9*9 dans laquelle est écrit false lorsque la case de gird est égale à 0 (donc quand la case est à compléter (vide)) et true dans le cas contraire (donc lorsque le chiffre est fixé). Pour commencer ! Ils nous font un guide express avec 9 questions (Q1 à Q9) à compléter nous-même.
Voici ce que j'ai fait pour le début :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 /** * Renvoie une grille de booléens de taille 9×9, qui contient true * dans chaque case dont la position correspond à celle d'une case * de grid qui n'est pas égale à 0 (et false dans les autres) */ // Ecrire ici la reponse à Q1
Ce code correspond-t-il ?
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12 public static boolean [] [] casesFixees(int [] [] grid) { for (int i=0 ; i<9 ; i++) { for (int j=0 ; j<9 ; j++) { if (grid[i][j]==0) { return false; } else { return true; } } System.out.print("\n"); } }
Je vous remercie d'avance !
PS : Je suis débutante, j'ai commencé la programmation Java en septembre ! Autant dire que j'en suis qu'au début
Bonne soirée ou journée !
Partager