Solveur de Sudoku

09-02-09

Capture d'écran du solveur

Capture d'écran du solveur

Je mets en ligne « Axel’s Sudoku », un projet que j’ai réalisé entre fin 2008 et début 2009. Il s’agit d’un solveur de grilles de Sudoku écrit en langage Java, et que je distribue sous licence GPL.

Il est donc totalement gratuit. Le code source est par ailleurs intégralement fourni.

Ci-dessous figurent ses caractéristiques principales :

  • Utilisation des bibliothèques graphiques Swing et AWT de Java
  • Le programme est structuré en objets, et est très facilement réutilisable (par exemple pour l’ajout de fonctionnalités, ou l’écriture de nouvelles interfaces graphiques). Tout cela peut se faire très simplement, en écrivant des classes qui descendent des interfaces et classes abstraites que j’ai définies
  • Bâti suivant le patron de conception Modèle-Vue-Contrôleur (MVC).
  • Le code est extrêmement portable : le fichier JAR distribué est exécutable sans aucune modification sur toute plateforme disposant du Runtime Java 1.6
  • L’algorithme principal de résolution, tout en donnant de très bons résultats (de l’ordre de 20 à 50 millisecondes pour la résolution d’une grille du type de celles publiées dans les quotidiens, de niveau facile à diabolique) est simple et compréhensible. Il repose sur une récursivité au sein d’une structure itérative. C’est la pile d’appels de Java qui effectue la totalité du travail nécessaire à d’autres algorithmes basés sur une pile écrite à la main, et donc au code nettement moins lisible. Cet algorithme est parfois appelé « Algorithme de Backtracking »
  • Utilisation de mémoire constante et très peu importante. Le nombre d’objets crées est fixe, on travaille tout le temps sur la même grille, d’où un besoin moindre de création de variables.



Voici le lien de téléchargement du solveur.
Cette archive au format ZIP contient :

  • d’une part le JAR exécutable, c’est-à dire le fichier que vous devez lancer si vous souhaitez tester ou utiliser le programme ;
  • d’autre part, les sources, fichiers de NetBeans et tous les scripts nécessaires à la compilation.

Pour utiliser le solveur, vous devrez :

  • Décompresser l’archive ZIP quelque part sur votre disque dur
  • Lancer le fichier axel_s_sudoku.jar issu de la décompression, soit par double clic, soit en effectuant un clic droit et sélectionnant le Runtime Java dans le menu «Ouvrir avec…»
  • Vous n’avez plus qu’à rentrer votre grille et cliquer sur le bouton de résolution !
  • Vous pouvez ensuite vous intéresser au dossier source/ si vous êtes familier avec la programmation. Dans le cas contraire, vous n’avez pas à vous en occuper…

En guise d’extrait de code, voici l’algorithme de résolution par backtracking, commenté.

  1.  /**
  2.    * On applique l’algorithme de résolution.
  3.    * Si une solution est trouvée, elle est écrite dans this.solution,
  4.    * et le flag this.solutionTrouvee est placé à vrai.
  5.    */
  6.   public void resoudre() {
  7.     Case caseLibre = null;
  8.  
  9.  
  10.     /* Cas non terminal : la grille n’est pas pleine */
  11.     if(!solutionTrouvee && ((caseLibre = grille.caseLibre()) != null)){
  12.       // On récupère une case libre de la grille
  13.       int i = caseLibre.i;
  14.       int j = caseLibre.j;
  15.  
  16.  
  17.       for(int k = 1; k <= 9; k++) {
  18.         /* Dans la case libre, on va regarder pour chaque chiffre k
  19.          entre 1 et 9 s’il est déjà présent dans la même ligne,
  20.          la même colonne, ou le même carré.
  21.          Si c’est le cas, on passe au chiffre k suivant */
  22.         if( !grille.chiffreDansCarre(k, i, j)
  23.           && !grille.chiffreDansColonne(k, j)
  24.           && !grille.chiffreDansLigne(k, i) ) {
  25.           /* Si ce n’est pas le cas, alors on écrit k
  26.            dans la case libre */
  27.             grille.setValeur(i, j, k);
  28.             /* On vient de réduire de 1 le nombre
  29.              de cases libres, on refait un appel
  30.              à resoudre()
  31.              C’est ici que se situe toute la récursivité
  32.              de l’algorithme */
  33.             resoudre();
  34.         }
  35.       }
  36.  
  37.       /* Si on arrive ici, c’est que aucun de tous
  38.        les chiffres qu’on a essayé de mettre
  39.        dans la case libre n’a permis à l’algorithme
  40.        de trouver une solution.
  41.        On remet donc un zéro dans cette case, pour indiquer
  42.        qu’elle est libre pour un
  43.        éventuel essai ultérieur */
  44.       grille.setValeur(i, j, 0);
  45.  
  46.     }
  47.  
  48.  
  49.     /* Cas terminal: aucune case libre n’a été trouvée. */
  50.     if (caseLibre == null && grille.estCorrecte()) {
  51.       /* Si notre grille est correcte, on met à jour le flag
  52.         solutionTrouvee, et l’attribut solution.
  53.        Le travail est terminé */
  54.       solutionTrouvee = true;
  55.       solution = new int[9][9];
  56.       for (int i = 0; i < 9; i++) {
  57.         for(int j = 0; j < 9; j++) {
  58.           solution[i][j] = grille.getValeur(i, j);
  59.         }
  60.       }
  61.     }
  62.   }

Tags: , , ,

Cet article a été posté le Lundi 9 février 2009 à 19:54 dans la catégorie Informatique. Vous pouvez suivre les réponses grâce au flux RSS 2.0. Vous pouvez écrire une réponse, ou établir un trackback depuis votre propre site.

3 réponses à “Solveur de Sudoku”

  1. CHAZALON 29 juin 2009 à 14:13

    Bonjour,

    Félicitations pour votre algorithme de résolution
    des grilles de Sudoku.
    Puisque votre code est en freeware, quelle
    est la syntaxe requise pour mettre votre outil
    en ligne sur un site WEB ?

    Merci.

  2. admin 29 juin 2009 à 20:23

    Vous pouvez simplement placer le logiciel en téléchargement libre, avec un lien retour vers mon site. En effet je pourrais effectuer des ajouts au solveur, qu’il serait bon (mais pas indispensable) que vous répercutiez si vous décidez de le diffuser.
    :)

  3. CHAZALON 5 juillet 2009 à 14:16

    Merci !!!

Écrire une réponse