Le Solveur de Sudoku !

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 :P ).

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 :

Code:

---

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; }

---

Et voilà solvedGrid :

Code:

---

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; }

---

Pour compléter, on a également ceci :

Code:

---

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)); }   }

---

Autant vous dire que malgré tout ça, j'ai du mal !

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.

Code:

---

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

---

Voici ce que j'ai fait pour le début :

Code:

---

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"); } }

---

Ce code correspond-t-il ?

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 :aie:

Bonne soirée ou journée ! :P

Tiens c'est marrant j'ai eu exactement le même sujet pendant ma première année d'info :)

Pour ce qui est de ton code, il n'est pas tout à fait correct (d'ailleurs il ne compile pas). Toi ce que tu veux c'est créer un tableau de booléen qui te permette de dire si une case est vide, ou si elle contient un chiffre déjà fixé.

Or quand tu écris

Code:

---

1 2 3 4 5 6

if (grid[i][j]==0) { return false; } else { return true; }

---

Le return va faire que ton programme va immédiatement sortir de ta méthode en retournant une valeur booléen. Ce qui ne correspond pas à la signature la la méthode qui elle stipule que tu vas retourner un tableau de booléen public static boolean [][] casesFixees(..).

Ce que tu dois faire c'est créer une variable locale à ta méthode boolean [][] tmp = new boolean[9][9] et affecter le résultat de ta comparaison dans ce tableau temporaire. Tu pourras ensuite renvoyer ce tableau quand tu auras analysé toutes les cases de ta grilles.

Au passage, l'instruction System.out.print("\n"); n'est pas très utile étant donnée que tu est dans une méthode de calcul et non pas d'affichage ;)